Fast Parallel Direct Solvers for Coarse Grid Problems

H. M. Tufo; P. F. Fischer

doi:10.1006/jpdc.2000.1676

Fast Parallel Direct Solvers for Coarse Grid Problems

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

Abstract

We have developed a fast direct solver for parallel solution of coarse grid problems, Ax=b, such as arise when domain decomposition or multigrid methods are applied to elliptic partial differential equations in d space dimensions. The approach is based on a (quasi-) sparse factorization of the inverse of A. If A is n×n and the number of processors is P, the algorithm requires O(n^γlogP) time for communication and O(n^1+γ/P) time for computation, where γ≡d-1d. The method is particularly suited to leading-edge multicomputer systems having thousands of processors. It achieves minimal message startup costs and substantially reduced message volume and arithmetic complexity compared with competing methods, which require O(nlogP) time for communication and O(n^1+γ) or O(n²/P) time for computation. Timings on the Intel Paragon and ASCI-Red machines reflect these complexity estimates.

Original language	English (US)
Pages (from-to)	151-177
Number of pages	27
Journal	Journal of Parallel and Distributed Computing
Volume	61
Issue number	2
DOIs	https://doi.org/10.1006/jpdc.2000.1676
State	Published - Feb 2001
Externally published	Yes

Keywords

Direct solver; sparse factorization; nested dissection; parallel computing; coarse grid problems

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Online availability

10.1006/jpdc.2000.1676

Library availability

Discover UIUC Full Text

Cite this

@article{d89d9c4ae1174b218b946569b1214d02,

title = "Fast Parallel Direct Solvers for Coarse Grid Problems",

abstract = "We have developed a fast direct solver for parallel solution of coarse grid problems, Ax=b, such as arise when domain decomposition or multigrid methods are applied to elliptic partial differential equations in d space dimensions. The approach is based on a (quasi-) sparse factorization of the inverse of A. If A is n×n and the number of processors is P, the algorithm requires O(nγlogP) time for communication and O(n1+γ/P) time for computation, where γ≡d-1d. The method is particularly suited to leading-edge multicomputer systems having thousands of processors. It achieves minimal message startup costs and substantially reduced message volume and arithmetic complexity compared with competing methods, which require O(nlogP) time for communication and O(n1+γ) or O(n2/P) time for computation. Timings on the Intel Paragon and ASCI-Red machines reflect these complexity estimates.",

keywords = "Direct solver; sparse factorization; nested dissection; parallel computing; coarse grid problems",

author = "Tufo, {H. M.} and Fischer, {P. F.}",

note = "Funding Information: This work was supported by the NSF under Grant ASC-9405403 and by the AFOSR under Grant F49620-95-1-0074; by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38; by the Department of Energy under Grant B341495 to the Center on Astrophysical Thermonuclear Flashes at the University of Chicago; and by the University of Chicago. Computer time was provided on the Intel Paragon and Delta at Caltech under NSF Cooperative Agreement CCR-8809615 and on the Intel Paragon at Wright Patterson Air Force Base by the AFOSR.",

year = "2001",

month = feb,

doi = "10.1006/jpdc.2000.1676",

language = "English (US)",

volume = "61",

pages = "151--177",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Fast Parallel Direct Solvers for Coarse Grid Problems

AU - Tufo, H. M.

AU - Fischer, P. F.

N1 - Funding Information: This work was supported by the NSF under Grant ASC-9405403 and by the AFOSR under Grant F49620-95-1-0074; by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38; by the Department of Energy under Grant B341495 to the Center on Astrophysical Thermonuclear Flashes at the University of Chicago; and by the University of Chicago. Computer time was provided on the Intel Paragon and Delta at Caltech under NSF Cooperative Agreement CCR-8809615 and on the Intel Paragon at Wright Patterson Air Force Base by the AFOSR.

PY - 2001/2

Y1 - 2001/2

N2 - We have developed a fast direct solver for parallel solution of coarse grid problems, Ax=b, such as arise when domain decomposition or multigrid methods are applied to elliptic partial differential equations in d space dimensions. The approach is based on a (quasi-) sparse factorization of the inverse of A. If A is n×n and the number of processors is P, the algorithm requires O(nγlogP) time for communication and O(n1+γ/P) time for computation, where γ≡d-1d. The method is particularly suited to leading-edge multicomputer systems having thousands of processors. It achieves minimal message startup costs and substantially reduced message volume and arithmetic complexity compared with competing methods, which require O(nlogP) time for communication and O(n1+γ) or O(n2/P) time for computation. Timings on the Intel Paragon and ASCI-Red machines reflect these complexity estimates.

AB - We have developed a fast direct solver for parallel solution of coarse grid problems, Ax=b, such as arise when domain decomposition or multigrid methods are applied to elliptic partial differential equations in d space dimensions. The approach is based on a (quasi-) sparse factorization of the inverse of A. If A is n×n and the number of processors is P, the algorithm requires O(nγlogP) time for communication and O(n1+γ/P) time for computation, where γ≡d-1d. The method is particularly suited to leading-edge multicomputer systems having thousands of processors. It achieves minimal message startup costs and substantially reduced message volume and arithmetic complexity compared with competing methods, which require O(nlogP) time for communication and O(n1+γ) or O(n2/P) time for computation. Timings on the Intel Paragon and ASCI-Red machines reflect these complexity estimates.

KW - Direct solver; sparse factorization; nested dissection; parallel computing; coarse grid problems

UR - http://www.scopus.com/inward/record.url?scp=0006606983&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0006606983&partnerID=8YFLogxK

U2 - 10.1006/jpdc.2000.1676

DO - 10.1006/jpdc.2000.1676

M3 - Article

AN - SCOPUS:0006606983

SN - 0743-7315

VL - 61

SP - 151

EP - 177

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 2

ER -

Fast Parallel Direct Solvers for Coarse Grid Problems

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this