Parallel evaluation of the determinant and of the inverse of a matrix (Q1115596)

We decrease (from \(o(n^{2.876})\) to \(o(n^{2.851}))\) the current record bound on the number of processors required in \(O(\log^ 2 n)\) step parallel arithmetic algorithms over rationals for the exact evaluation of the inverse and all coefficients of the characteristic polynomial of an \(n\times n\) rational, real, or complex matrix A. For an integer input matrix A, the evaluation involves only d-bit numbers where either \(d=O(\log p)\) if the computation is modulo a prime p or \(d=O(n \log \| A\|)\) in the general case; the Boolean cost of computing det A is further decreased in a randomized parallel algorithm.