ON THE COMPLEXITY OF INVERTING INTEGER AND POLYNOMIAL MATRICES

摘要

An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n x n integer matrix A using (n(3)(log parallel to A parallel to + log kappa(A)))(1+o(1)) bit operations. Here, parallel to A parallel to = max(ij) |A(ij)| denotes the largest entry in absolute value, kappa(A) := n parallel to A(-1)parallel to parallel to A parallel to is the condition number of the input matrix, and the "+ o(1)" in the exponent indicates a missing factor c(1)(log n)(c2)(loglog parallel to A parallel to)(c3) for positive real constants c(1), c(2), c(3). A variation of the algorithm is presented for polynomial matrices that computes the inverse of a nonsingular nxn matrix whose entries are polynomials of degree d over a field using (n(3)d)(1+o(1)) field operations. Both algorithms are randomized of the Las Vegas type: failure may be reported with probability at most 1/2, and if failure is not reported, then the output is certified to be correct in the same running time bound.