Fast parallel matrix and GCD computations
- 1 November 1982
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 65-71
- https://doi.org/10.1109/sfcs.1982.17
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- The complexity of partial derivativesTheoretical Computer Science, 1983
- On the Asymptotic Complexity of Matrix MultiplicationSIAM Journal on Computing, 1982
- The computational complexity of continued fractionsPublished by Association for Computing Machinery (ACM) ,1981
- A note on the parallel complexity of computing the rank of order n matricesInformation Processing Letters, 1980
- On simultaneous resource boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970
- Sylvester's Identity and Multistep Integer-Preserving Gaussian EliminationMathematics of Computation, 1968
- Systems of distinct representatives and linear algebraJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967