Quadratic time certificates in linear algebra

Speaker: Erich Kaltofen

We present certificates for the positive semi-definiteness
of an n by n matrix A, whose entries are integers of binary length L =
log||A||, that can be verified in O(n^{2+epsilon} L^{1+epsilon})$ binary
operations for any epsilon.

The question arises in Hilbert/Artin-based rational
sum-of-squares certificates, i.e., proofs, for polynomial inequalities with
rational coefficients.We allow
certificates that are validated by Monte Carlo randomized algorithms, as in Rusins
M. Freivalds's famous 1979 quadratic time certification for the matrix
product.Our certificates occupy
O(n^{3+epsilon}

L^{1+\epsilon}) bits, from which the verification
algorithm randomly samples a quadratic amount.

In addition, we give certificates of the same space and
randomized validation time complexity for the Frobenius form, which includes
the characteristic and minimal polynomial.For determinant and rank we have certificates of essentially binary
space and time complexity via Storjohann's algorithms.

This work is in collaboration with Michael Nehring and B.
David Saunders.