Fast Parallel Matrix and GCD Computations

摘要

We present parallel algorithms to compute the determinant and characteristics polynomial of nxn-matrices and the gcd of polynomials of degree less than or equal n. The algorithms use parallel time O(log to the 2nd power 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. (Author)