Efficient parallel factorization and solution of structured and unstructured linear systems

This paper gives improved parallel methods for several exact factorizations of some classes of symmetric positive definite (SPD) matrices. Our factorizations also provide us similarly efficient algorithms for exact computation of the solution of the corresponding linear systems (which need not be SPD), and for finding rank and determinant magnitude. We assume the input matrices have entries that are rational numbers expressed as a ratio of integers with at most a polynomial number of bits β. We assume a parallel random access machine (PRAM) model of parallel computation, with unit cost arithmetic operations, including division, over a finite field Zp, where p is a prime number whose binary representation is linear in the size of the input matrix and is randomly chosen by the algorithm. We require only bit precision O(n(β+logn)), which is the asymptotically optimal bit precision for β⩾logn. Our algorithms are randomized, giving the outputs with high likelihood ⩾1-1/nΩ(1). We compute LU and QR factorizations for dense matrices, and LU factorizations of sparse matrices which are s(n)-separable, reducing the known parallel time bounds for these factorizations from Ω(log3n) to O(log2n), without an increase in processors (matching the best known work bounds of known parallel algorithms with polylog time bounds). Using the same parallel algorithm specialized to structured matrices, we compute LU factorizations for Toeplitz matrices and matrices of bounded displacement rank in time O(log2n) with nloglogn processors, reducing by a nearly linear factor the best previous processor bounds for polylog times (however, these prior works did not generally require unit cost division over a finite field). We use this result to solve in the same bounds: polynomial resultant; and Padé approximants of rational functions; and in a factor O(logn) more time: polynomial greatest common divisors (GCD) and extended GCD; again reducing the best processor bounds by a nearly linear factor.