Efficient parallel independent subsets and matrix factorizations
Wayne Eberly · 2002
A parallel algorithm is given for computation of a maximal linearly independent subset of a set of vectors over a field. The algorithm uses polylogarithmic time and uses a number of processors that differs by only a polylog factor from the number required for fast parallel matrix inversion. It is used to produce efficient parallel algorithms for orthogonalizations of arbitrary matrices over real fields, and for P-L-U factorizations of nonsingular matrices over arbitrary fields. These are the first processor-efficient highly parallel algorithms known for these problems.>