Processor efficient parallel solution of linear systems over an abstract field
Erich Kaltofen, Victor Ya. Pan · 1991
lems of computing the inverse, determinant, and rank of an n x 71 matrix.An individual step in our algorithms is an addition, subtraction, multiplication, division, or zero-test of elements in the field that the entries of the linear system generate.Gaussian elimination is a sequential method for all these computational problems over abstract fields, whose running time can be asymptotically related to the sequential complexity of n x n matrix multiplication (Bunch and Hopcroft 1974).We present processor efficient randomized parallel algorithms for solving non-singular systems and for inverting non-singular matrices.Csanky (1976) used Leverrier's approach to devise a parallel linear system solver, but the best processor count known for this approach exceeds by a factor of almost A the complexity of matrix multiplication (Preparata and Sarwate 1978), (Galil and Pan 1989).Leverrier's algorithm does not work for fields whose characteristic is positive and less than n, in which case the best known parallel algorithms needed by a factor of n more processors (Berkowitz 1984), (Chistov 1985).All previous parallel solutions compute the characteristic polynomial of the coefficient matrix without divisions.For this restricted algebraic model these algorithms are processor optimal, i.e., it appears not to be known how