Fast Parallel Matrix and GCD Computations

We present parallel algorithms to compute the determinant and characteristic polynomial of n×n-matrices and the gcd of polynomials of degree ≤n. The algorithms use parallel time O(log2n) and a polynomial number of processors. We also give a fast parallel Las Vegas algorithm for the rank of matrices. All algorithms work over arbitrary fields.

Authors

• Allan Borodin
• Joachim von zur Gathen
• John E. Hopcroft

Keywords

• Concurrent computing
• Polynomials
• Equations
• Parallel algorithms
• Galois fields
• Phase change random access memory
• Testing
• Monte Carlo methods
• Parallel programming
• Vectors
• Rank Of Matrix
• Parallel Algorithm
• Characteristic Polynomial
• Arbitrary Field
• Number Of Processors
• Linear Equation
• Parallelization
• Fast Algorithm
• Nonsingular
• Maximum Flow
• System Of Linear Equations
• Monte Carlo Algorithm
• Parallel Method
• Sequential Algorithm
• Finite Field
• Maximum Matching
• Computational Sequence
• Gaussian Elimination
• Algebraic Calculations
• Solutions Of Linear Equations
• Proof Let
• Ground Field
• Ranking Problem
• Field Of Characteristic Zero