Parallel solution of sparse linear systems

John R. Gilbert, Hjálmtýr Hafsteinsson

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)


Consider a system of linear equations Ax=b, where A is a symmetric positive definite matrix with arbitrary nonzero structure. We present an efficient CREW parallel algorithm to solve such a system by Cholesky factorization with M* processors, where m* is the number of nonzeros in the Cholesky factor of A. The algorithm has two stages. First is a graph-theoretic structure prediction phase, which runs in time O(log2n). There follows a numerical computation phase, which runs in time proportional to the height of the elimination tree of A times a log factor.

Original languageEnglish
Title of host publicationSWAT 88 - 1st Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsRolf Karlsson, Andrzej Lingas
PublisherSpringer Verlag
Number of pages9
ISBN (Print)9783540194873
Publication statusPublished - 1988
Event1st Scandinavian Workshop on Algorithm Theory, SWAT 1988 - Halmstad, Sweden
Duration: 5 Jul 19888 Jul 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume318 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference1st Scandinavian Workshop on Algorithm Theory, SWAT 1988

Bibliographical note

Publisher Copyright:
© 1988, Springer-Verlag.


Dive into the research topics of 'Parallel solution of sparse linear systems'. Together they form a unique fingerprint.

Cite this