# Fast and efficient parallel solution of sparse linear systems

Published

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