A Fully Algebraic Multigrid Method for Automated Solution
of Sparse Linear Systems on High Performance Computers


Principal Investigator: Jun Zhang
Co-Principal Investigator: Craig C. Douglas
Graduate Research Assistant: Kai Wang
Project Participant: Chi Shen


Funding Sources: National Science Foundation
Funding Division: Computer-Communications Reseach
Funding Program: Symbolic, Numeric, and Geometric Computation
Program Director: Kamal Abdali and William Randolph Franklin
Contract Number: CCR-9902022
Estimated Budget: $188,313
Duration: 08/01/1999 - 07/31/2002 (36 months)

Abstract:

This project is to design robust and efficient computational kernel software for solving large sparse unstructured linear systems on high performance computers. Such large scale problems can only be solved by iterative techniques. The iterative techniques under our consideration include multilevel preconditioning techniques and algebraic multigrid methods. Our goal is to unify these two groups of methods and to take the advantages from both and avoid the disadvantages of either methods. We will investigate, design, and test algebraic preconditioners that offer the scalability of multigrid techniques, the parallelism of domain decomposition methods, and the robustness of incomplete LU preconditioners.

We will also use a factored sparse approximate inverse technique to replace standard iterative schemes in algebraic multigrid methods. Such an approach may increase the robustness of our methods and improve their parallelism. Graph partitioning of submatrices is to be used to balance loads among processors. The proposed research will result in a software package that may be used by researchers and engineers as kernel software in large scale numerical simulations and computations.

The general purpose high performance iterative solvers from this research project are expected to make significant impact in the field of applied scientific computing. The results of the research will make a clear judgment concerning the relative advantages and disadvantages of algebraic multigrid methods and multilevel incomplete LU preconditioning methods. The outcome of this research will benefit U.S. industry as well as scientific research community by providing more efficient kernel software for large scale numerical simulations. Industries that will be impacted include aerospace, semiconductor, reservoir simulation, combustion, ocean/climate modeling, pollution tracking, and others.


This Project was finished successfully on July 31, 2002.
Technical Reports and Computer Software:
  1. A procedure for computing factored approximate inverse, M.S. Project Report of Jiqing Zhang (August, 1999).
  2. Parallel two level block ILU preconditioning techniques for solving large sparse linear systems, by Chi Shen and Jun Zhang (July, 2000).
  3. Multigrid treatment and robustness enhancement for factored sparse approximate inverse preconditioning, by Kai Wang and Jun Zhang (September, 2000).
  4. SOFTWARE: Parallel two level block ILU preconditioning techniques for solving large sparse linear systems, by Chi Shen and Jun Zhang (October, 2000).
  5. A multilevel block incomplete Cholesky preconditioner for solving rectangular sparse matrices from linear least squares problems, by Jun Zhang and Tong Xiao. (January, 2001).
  6. MSP: a class of parallel multistep successive sparse approximate inverse preconditioning strategies, by Kai Wang and Jun Zhang. (January, 2002).
  7. Global and localized parallel preconditioning techniques for large scale solid Earth simulations, by Kai Wang, Sang-Bae Kim, Jun Zhang, Kengo Nakajima, and Hiroshi Okuda. (May, 2002).
  8. SOFTWARE: Parallel multilevel block ILU preconditioning techniques for solving large sparse linear systems (with parallel independent block search), by Chi Shen and Jun Zhang (July, 2002).
  9. SOFTWARE: Parallel multilevel block ILU preconditioning techniques for solving large sparse linear systems (with sequential independent block search), by Chi Shen and Jun Zhang (July, 2002).
  10. Distributed block independent set algorithms and parallel multilevel ILU preconditioners, by Chi Shen, Jun Zhang, and Kai Wang (October, 2002).

  11. A class of parallel multilevel sparse approximate inverse preconditioners for sparse linear systems, by Kai Wang, Jun Zhang, and Chi Shen (November, 2002).

This page is supported by the U.S. National Science Foundation. However, any opinions, findings, and conclusions or recommendations expressed in this documents are those of the author and do not necessarily reflect the views of the U.S. National Science Foundation.


Go back to Funded Research Projects page.


This page was created on Friday, March 31, 2000, by
Jun Zhang
Last modified on Thursday, November 14, 2002.