Fast Parallel Direct Solvers for Coarse Grid Problems

H. M. Tufo, P. F. Fischer

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)151-177
Number of pages27
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - Feb 2001
Externally publishedYes


  • 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


Dive into the research topics of 'Fast Parallel Direct Solvers for Coarse Grid Problems'. Together they form a unique fingerprint.

Cite this