Sparse linear
system solution costs can often dominate execution times of
large-scale modeling and simulation applications using implicit
or semi-implicit schemes.
There are a large number of basic sparse solution schemes
from classes such as direct, preconditioned-iterative (Krylov),
domain-decomposition, and multigrid/multilevel.
There is further multiplicative growth in the number of methods when Krylov
iterative methods are used as smoothers in multilevel methods, or the
latter are used as preconditioners for the former. The performance of
all these methods, including convergence, reliability, execution time,
parallel efficiency, and scalability, can vary dramatically depending on
the exact interaction of a specific method, the problem instance, and
the computer architecture. It is typically neither possible nor
practical to predict a priori which sparse linear solver
algorithm performs best for a given problem.
Our SuperSolvers project concerns algorithms and software for
automated method selection and composition to instantiate robust and
scalable solvers tailored to meet application demands. This project
includes the development of new sparse solution schemes, their analysis,
and applications to enable computational modeling and simulation.
Hybrid Solvers
using flexible incomplete sparse factorization
preconditioners with a range of fill-in from pure iterative to pure direct
(see publications 1 and 2 below).
Composite Solvers
that use a sequence of basic solution schemes on a single linear system
to enable highly reliable solution with limited memory requirements
(see publications 3 and 4 below).
Adaptive Solvers
that dynamically select a sparse solution scheme to match changing
numerical attributes of systems generated across iterations of a long
running simulation
(see publications 5 and 6 below).
Recent Publications
1. Effective Preconditioning through Ordering Interleaved with Incomplete Factorization
, I. Lee, P. Raghavan and E. G. Ng,
submitted to the SIAM Journal on Matrix Analysis and Applications
(special issue on preconditioning).
Click here to access a copy of the paper (pdf).
Proposes interleaving ordering (to reduce fill) with the process of
computing an incomplete factorization; results indicate that
explicitly ordering to reduce fill in the incomplete factor (as opposed
to the fill in the true factor) leads to better quality preconditioners.
2. A Latency Tolerant Hybrid Sparse Solver Using Incomplete Cholesky
Factorization,
P. Raghavan, K. Teranishi and E. G. Ng, Numerical Linear
Algebra, Volume 10, pp. 541-560, 2003.
Click here to access a copy of the paper (pdf).
Proposes the use of selective inversion to enable latency-tolerant
application of incomplete factor preconditioners on distributed memory
multi-processors. Results indicate that partial replacement distributed
substitution by sparse matrix-vector multiplication removes performance
degradations due to the relatively large latencies of inter-processor communication.
Click here to access related software.
3. A Combinatorial Scheme for Developing Efficient Composite Solvers,
S. Bhowmick, P. Raghavan, and K. Teranishi,
Lecture Notes in Computer Science, Editors P. M. A. Sloot,
C. J. K. Tan, J. J. Dongarra, and A. G. Hoekstra,
Computational Science- ICCS 2002,
Number 2330, Springer Verlag, pp. 325-334, May 2002.
Click here to access a copy of the paper (pdf).
Introduces the concept of a composite solver comprising a sequence of
limited memory base solution schemes to improve reliability.
Proves that the optimal composite is obtained when methods are selected
in increasing order of the ratios of their time per iteration and failure rate.
4. Faster PDE-Based Simulations Using Robust Composite Linear Solvers,
S. Bhowmick, P. Raghavan, L. C. McInnes and B. Norris,
Future Generation Computer Systems, Vol. 20, pp. 373-387, 2004.
Click here to access a copy of the paper (pdf).
Shows how robust linear solution using composites can lead to improved
application time.
5. Adaptive Sparse Linear Solvers for Implicit CFD Using Newton-Krylov
Algorithms,
B. Norris, L. McInnes, S. Bhowmick and P. Raghavan,
Proceedings of the
Second MIT Conference on Computational Fluid and Solid Mechanics,
Volume 2, pp. 1024-1028, June 2003.
Click here to access a copy of the paper (pdf).
Introduces several heuristics for adaptive method selection and reports
on their performance in driven-cavity flow applications.
6. Robust Algorithms and Software for Parallel PDE-Based Simulations,
S. Bhowmick, L. McInnes, B. Norris and P. Raghavan,
Proceedings of HPC 2004,
The Twelfth Special Symposium on High Performance Computing at the
2004 Advanced Simulation Technologies Conference, Arlington, VA,
pp. 37-42, April 2004.
Click here to access a copy of the paper (pdf).
Discusses a software component scheme for instantiating
composite and adaptive solvers and reports on their
parallel performance in modeling applications.
Click here to access more publications.
Participants
S. Bhowmick,
I. Lee
P. Raghavan and
K. Teranishi (Pennsylvania State University).
L. C. McInnes,
B. Norris
and
B. Smith
(Argonne National Laboratory).
E. G. Ng
(Lawrence Berkeley National Laboratory) .
Funding
National Science Foundation,
"Robust Limited Memory Hybrid Sparse Solvers"
, P. Raghavan, 8/01--08/05.
Lawrence Berkeley National Lab. (Department of Energy), "Terascale
Optimal PDE Simulation," subcontract to Penn State, P. Raghavan, 5/02--5/05.
Argonne National Laboratory and the University of Chicago,
The Maria Goeppert Mayer Distinguished Scholar Award,
P. Raghavan, 01/02--12/02.
Return to Padma Raghavan's Webpage
