Fast Parallel Matrix and GCD Computations

Abstract

We present parallel algorithms to compute the determinant and characteristic polynomial of n x n-matrices and the gcd of polynomials of degree $\leq$n. The algorithms use parallel time $O(\log^{2}n)$ and a polynomial number of processors. We also give a fast parallel Monte Carlo algorithm for the rank of matrices. All algorithms work over arbitrary fields.