Fast Parallel Matrix and GCD Computations
Allan Borodin, Joachim Von Zur Qathen, John E. Hopcroft · 1982
Parallel algorithms to compute the determinant and characteristic polynomial of matrices and the gcd of polynomials are presented. The rank of matrices and solutions of arbitrary systems of linear equations are computed by parallel Las Vegas algorithms. All algorithms work over arbitrary fields. They run in parallel time O(log ~ n) (where n is the number of inputs) and use a polynomial number of processors.