## Fast and efficient parallel solution of sparse linear systems

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.

### Duke Scholars

##### Altmetric Attention Stats

##### Dimensions Citation Stats

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics

### Citation

*SIAM Journal on Computing*,

*22*(6), 1227–1250. https://doi.org/10.1137/0222073

*SIAM Journal on Computing*22, no. 6 (January 1, 1993): 1227–50. https://doi.org/10.1137/0222073.

*SIAM Journal on Computing*, vol. 22, no. 6, Jan. 1993, pp. 1227–50.

*Scopus*, doi:10.1137/0222073.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics