Processor-efficient parallel matrix inversion over abstract fields
Wayne Eberly · 1997
Kaltofen and Pan’s processor-efficient parallel algorithm for the solution of a general n x n system of linear equations over an abstract field is extended in two ways. First, it is shown that dense, unstructured systems of linear equations over small fields can be solved using the time established by Kaltofen and Pan for this case, and with the time-processor product established by Kaltofen and Pan for computations over iarge fields — reducing the work required for the small field case by slightly more than a logarithmic factor. Second, a processor-efficient parallel algorithm ia given for computation of the inverse of a matrix over an abstract field. This algorithm has essentially the same complexity as Kaltofen and Pan’s algorithm for thw problem, but it does not rely on any program transformation of the type given by Baur and Straaaen, and used by Kaltofen and Pan to obtain an algorithm for matrix inversion. Thus, thii is the first “explicitly given” processor-efficient parallel algorithm for matrix inversion over an abstract field.