Parallel symbolic factorization of sparse linear systems

John R. Gilbert; Hjálmtýr Hafsteinsson

doi:10.1016/0167-8191(90)90104-H

Parallel symbolic factorization of sparse linear systems

John R. Gilbert, Hjálmtýr Hafsteinsson

Faculty of Industrial Engineering, Mechanical Engineering and Computer Science

University of Iceland

Research output: Contribution to journal › Article › peer-review

Abstract

The Cholesky factorization of a sparse matrix A can introduce new nonzeros into the factor matrix. We present an efficient CRCW parallel algorithm to find this fill. Our algorithm takes O(log²n) time using m* processors, where m* is the number of nonzeros in the Cholesky factor of A. The algorithm has two stages. First it finds A's elimination tree, and then uses it to compute the fill. The part of the algorithm that finds the elimination tree runs in O(log²n) time using m processors, where m is the number of nonzeros in A.

Original language	English
Pages (from-to)	151-162
Number of pages	12
Journal	Parallel Computing
Volume	14
Issue number	2
DOIs	https://doi.org/10.1016/0167-8191(90)90104-H
Publication status	Published - Jun 1990

Other keywords

Linear algebra
elimination trees
parallel algorithms
sparse matrix computation

Access to Document

10.1016/0167-8191(90)90104-H

Cite this

@article{6f092c62c1c442a0b727e6d7ac8f5198,

title = "Parallel symbolic factorization of sparse linear systems",

abstract = "The Cholesky factorization of a sparse matrix A can introduce new nonzeros into the factor matrix. We present an efficient CRCW parallel algorithm to find this fill. Our algorithm takes O(log2n) time using m* processors, where m* is the number of nonzeros in the Cholesky factor of A. The algorithm has two stages. First it finds A's elimination tree, and then uses it to compute the fill. The part of the algorithm that finds the elimination tree runs in O(log2n) time using m processors, where m is the number of nonzeros in A.",

keywords = "Linear algebra, elimination trees, parallel algorithms, sparse matrix computation",

author = "Gilbert, \{John R.\} and Hj{\'a}lmt{\'y}r Hafsteinsson",

year = "1990",

month = jun,

doi = "10.1016/0167-8191(90)90104-H",

language = "English",

volume = "14",

pages = "151--162",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Parallel symbolic factorization of sparse linear systems

AU - Gilbert, John R.

AU - Hafsteinsson, Hjálmtýr

PY - 1990/6

Y1 - 1990/6

N2 - The Cholesky factorization of a sparse matrix A can introduce new nonzeros into the factor matrix. We present an efficient CRCW parallel algorithm to find this fill. Our algorithm takes O(log2n) time using m* processors, where m* is the number of nonzeros in the Cholesky factor of A. The algorithm has two stages. First it finds A's elimination tree, and then uses it to compute the fill. The part of the algorithm that finds the elimination tree runs in O(log2n) time using m processors, where m is the number of nonzeros in A.

AB - The Cholesky factorization of a sparse matrix A can introduce new nonzeros into the factor matrix. We present an efficient CRCW parallel algorithm to find this fill. Our algorithm takes O(log2n) time using m* processors, where m* is the number of nonzeros in the Cholesky factor of A. The algorithm has two stages. First it finds A's elimination tree, and then uses it to compute the fill. The part of the algorithm that finds the elimination tree runs in O(log2n) time using m processors, where m is the number of nonzeros in A.

KW - Linear algebra

KW - elimination trees

KW - parallel algorithms

KW - sparse matrix computation

UR - https://www.scopus.com/pages/publications/0025449336

U2 - 10.1016/0167-8191(90)90104-H

DO - 10.1016/0167-8191(90)90104-H

M3 - Article

SN - 0167-8191

VL - 14

SP - 151

EP - 162

JO - Parallel Computing

JF - Parallel Computing

IS - 2

ER -

Parallel symbolic factorization of sparse linear systems

Abstract

Other keywords

Access to Document

Fingerprint

Cite this