Very Fast Parallel Matrix and Polynomial Arithmetic
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We present very efficient arithmetic circuits for the computation of the determinants and inverse of band matrices and for interpolation and polynomial arithmetic over arbitrary ground fields. For input size n the circuits for band matrix inversion (for constant band width) over infinite fields, and the circuits for polynomial arithmetic over arbitrary fields, have optimal depth 0(log n) and polynomial size. The algorithm for band matrix inversion is based on an extension of the method of modification (from numerical analysis) which includes a formula for the determinant of a modified matrix.Keywords
This publication has 15 references indexed in Scilit:
- Parallel Solution of Certain Toeplitz Linear SystemsSIAM Journal on Computing, 1984
- On computing the determinant in small parallel time using a small number of processorsInformation Processing Letters, 1984
- Logarithmic depth circuits for algebraic functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Fast parallel matrix and GCD computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A note on the parallel complexity of computing the rank of order n matricesInformation Processing Letters, 1980
- A Parallel Algorithm for Solving General Tridiagonal EquationsMathematics of Computation, 1979
- Solving Triangular Systems on a Parallel ComputerSIAM Journal on Numerical Analysis, 1977
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of EquationsJournal of the ACM, 1973
- Triangular factors of modified matricesNumerische Mathematik, 1965
- Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given MatrixThe Annals of Mathematical Statistics, 1950