Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Parallel solution of sparse linear systems
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 318/1988 |
| Book | SWAT 88 |
| DOI | 10.1007/3-540-19487-8 |
| Copyright | 1988 |
| ISBN | 978-3-540-19487-3 |
| DOI | 10.1007/3-540-19487-8_17 |
| Pages | 145-153 |
| Subject Collection | Computer Science |
| SpringerLink Date | Saturday, January 21, 2006 |
| |
|
Parallel solution of sparse linear systems John R. Gilbert1, 2, 3 and Hjálmtýr Hafsteinsson4
| (1) |
Dept. of Science and Technology, Christian Michelsen Institute, Fantoftveien 38, N-5036 Fantoft, Bergen, Norway |
| (2) |
University of Bergen, Norway |
| (3) |
Cornell University, USA |
| (4) |
Computer Science Department, Cornell University, 14853 Ithaca, New York, USA |
Abstract
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(log2
n). There follows a numerical computation phase, which runs in time proportional to the height of the elimination tree of A times a log factor.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|