Fast and efficient parallel solution of sparse linear systems


Journal Article

This paper presents a parallel algorithm for the solution of a linear system Ax = b with a sparse n × n symmetric positive definite matrix A, associated with the graph G(A) that has n vertices and has an edge for each nonzero entry of A. If G(A) has an s(n)-separator family and a known s(n)-separator tree, then the algorithm requires only O(log3 n) time and (|E| + M(s(n)))/log n processors for the evaluation of the solution vector x = A-1b, where |E| is the number of edges in G(A) and M(n) is the number of processors sufficient for multiplying two n × n rational matrices in time O(log n). Furthermore, for this computational cost the algorithm computes a recursive factorization of A such that the solution of any other linear system Ax = b′ with the same matrix A requires only O(log2n) time and (|E| log n) + s(n)2 processors.

Full Text

Duke Authors

Cited Authors

  • Pan, V; Reif, J

Published Date

  • January 1, 1993

Published In

Volume / Issue

  • 22 / 6

Start / End Page

  • 1227 - 1250

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/0222073

Citation Source

  • Scopus