This paper describes and tests a parallel message-passing code for constructing
sparse approximate inverse preconditioners using Frobenius norm minimization. The
sparsity patterns of the preconditioners are chosen as patterns of powers of
sparsified matrices. Sparsification is necessary when powers of a matrix have a
large number of nonzeros, making the approximate inverse computation expensive. For
our test problems, the minimum solution time is achieved with approximate inverses
with less than twice the number of nonzeros of the original matrix. Additional
accuracy is not compensated by the increased cost per iteration. The results lead to
further understanding of how to use these methods and how well these methods work in
practice. In addition, this paper describes programming techniques required for high
performance, including one-sided communication, local coordinate numbering, and load repartitioning.
Get full access to this article
View all access options for this article.
References
1.
Alléon, G.
,
Benzi, M.
, and
Giraud, L.1997.
Sparse approximate inverse preconditioning for dense linear systems arising
in computational electromagnetics
. Numerical Algorithms16:
1-15
.
2.
Barnard, S. T.
,
Bernardo, L. M.
, and
Simon, H. D.1999.
An MPI implementation of the SPAI preconditioner on the T3E
. Intl. J. High Perf. Comput. Appl.13:
107-128
.
3.
Barnard, S. T.
, and
Clay, R.
1997.
A portable MPI implementation of the SPAI preconditioner in ISIS++
. In Proceedings of the Eighth SIAM Conference on Parallel
Processing for Scientific Computing, Minneapolis, MN.
4.
Benson, M. W.
,
Krettmann, J.
, and
Wright, M.1984.
Parallel algorithms for the solution of certain large sparse linear systems
. Intl. J. Comput. Math.16:
245-260
.
5.
Benzi, M.
,
Cullum, J. K.
, and
Tuma, M.2000.
Robust approximate inverse preconditioning for the conjugate gradient method
. SIAM J. Sci. Comput.22:
1318-1332
.
6.
Benzi, M.
,
Kouhia, R.
, and
Tuma, M.1998.
An assessment of some preconditioning techniques in shell problems
. Communications in Numerical Methods in Engineering14:
897-906
.
7.
Carpentieri, B.
,
Duff, I. S.
, and
Giraud, L.2000.
Sparse pattern selection strategies for robust Frobenius-norm minimization
preconditioners in electromagnetism
. Num. Lin. Alg. Appl.7:
667-685
.
8.
Chen, K.1998.
On a class of preconditioning methods for dense linear systems from
boundary elements
. SIAM J. Sci. Comput.20:
684-698
.
9.
Chow, E.2000.
A priori sparsity patterns for parallel sparse approximate inverse preconditioners
. SIAM J. Sci. Comput.21:
1804-1822
.
10.
Chow, E.
, and
Saad, Y.1998.
Approximate inverse preconditioners via sparse-sparse iterations
. SIAM J. Sci. Comput.19:
995-1023
.
11.
Cormen, T. H.
,
Leiserson, C. E.
, and
Rivest, R. L.1991. Introduction to Algorithms.
Cambridge, MA: MIT Press
.
12.
Cosgrove, J.D.F.
,
Díaz, J. C.
, and
Griewank, A.1992.
Approximate inverse preconditioning for sparse linear systems
. Intl. J. Comput. Math.44:
91-110
.
13.
Cosnuau, A. 1996. Etude d’un préconditionneur pour
les matrices complexes dense issues des équations de Maxwell en
formulation intégrale. France: ONERA.
14.
Deshpande, V.
,
Grote, M. J.
,
Messmer, P.
, and
Sawyer, W.
1996.
Parallel implementation of a sparse approximate inverse preconditioner
. In Parallel Algorithms for Irregularly Structured Problems
(Irregular ’96), Santa Barbara, CA, 1996, eds.
A. Ferreira
,
J. Rolim
,
Y. Saad
, and
T. Yang
, vol. 3,
63-74
. Berlin: Springer-Verlag.
15.
Field, M. R.1997. An Efficient Parallel Preconditioner for the Conjugate
Gradient Algorithm (Tech. Rep. No. HDL-TR-97-175).
Dublin: Hitachi Dublin Laboratory, Trinity College
.
16.
Field, M. R.1998. Improving the Performance of Parallel Factorised Sparse
Approximate Inverse Preconditioners (Tech. Rep. No. HDL-TR-98-199).
Dublin: Hitachi Dublin Laboratory, Trinity College
.
17.
Field, M. R.1999. A Parallel Factorised Sparse Approximate Inverse
Preconditioner with Improved Choice of Sparsity Pattern (Tech. Rep. No.
HDL-TR-99-214).
Dublin: Hitachi Dublin Laboratory, Trinity College
.
18.
Gonnet, G. H.
, and
Baeza-Yates, R.1991. Handbook of Algorithms and Data Structures. 2nd ed.Reading, MA: Addison-Wesley
.
19.
Gropp, W.
,
Huss-Lederman, S.
,
Nitzberg, B.
, and
Lusk, E.1998. MPI the Complete Reference: The MPI-2 Extensions.
Cambridge, MA: MIT Press
.
20.
Gropp, W.
,
Kaushik, D.
,
Keyes, D.
, and
Smith, B.
1999.
Toward realistic performance bounds for implicit CFD codes
. In Proceedings of Parallel CFD99, Halifax,
Nova Scotia.
21.
Grote, M.
, and
Huckle, T.1997.
Parallel preconditioning with sparse approximate inverses
. SIAM J. Sci. Comput.18:
838-853
.
22.
Grote, M.
, and
Simon, H. D.
1993.
Parallel preconditioning and approximate inverses on the Connection Machine
. In Parallel Processing for Scientific Computing, eds.
R. F. Sincovec
,
D. E. Keyes
,
L. R. Petzold
, and
D. A. Reed
, vol. 2,
519-523
. Philadelphia: SIAM.
23.
Hendrickson, B.
, and
Devine, K.2000.
Dynamic load balancing in computational mechanics
. Comp. Meth. Applied Mechanics and Engineering184:
485-500
.
24.
Huckle, T.1996a. Efficient Computation of Sparse Approximate Inverses
(Tech. Rep. No. 342/04/96).
Munich: Technische University
.
25.
Huckle, T.
1996b.
PVM-implementation of sparse approximate inverse preconditioners for
solving large sparse linear equations
. In Lecture Notes in Comput. Sci., vol. 1156,
166-173
. New York: Springer-Verlag.
26.
Huckle, T.
1997.
Approximate sparsity patterns for the inverse of a matrix and preconditioning
. In Preliminary Proceedings IMACS World Congress on Scientific
Computation 1997, Berlin.
27.
Johnson, C.1987. Numerical Solution of Partial Differential Equations by the
Finite Element Method.
Cambridge, UK: Cambridge University Press
.
28.
Karypis, G.
, and
Kumar, V.
1998.
Multilevel algorithms for multi-constraint graph partitioning
. In Supercomputing 98, Orlando, FL.
29.
Knuth, D. E.1973. Sorting and Searching, vol. 3.
Reading, MA: Addison-Wesley
.
30.
Kolotilina, L. Y.1988.
Explicit preconditioning of systems of linear algebraic equations with
dense matrices
. J. Soviet Math.43:
2566-2573
.
31.
Kolotilina, L. Y.
,
Nikishin, A. A.
, and
Yeremin, A. Y.
1992.
Factorized sparse approximate inverse (FSAI) preconditionings for solving
3D FE systems on massively parallel computers: II. Iterative construction of
{FSAI} preconditioners
. In Proceedings IMACS Intl. Symp. Iterative Methods in Linear
Algebra, Brussels, Belgium.
32.
Kolotilina, L. Y.
,
Nikishin, A. A.
, and
Yeremin, A. Y.1999.
Factorized sparse approximate inverse preconditionings: IV. Simple
approaches to rising efficiency
. Num. Lin. Alg. Appl.6:
515-531
.
33.
Kolotilina, L. Y.
, and
Yeremin, A. Y.1993.
Factorized sparse approximate inverse preconditionings: I. Theory
. SIAM J. Matrix Anal. Appl.14:
45-58
.
34.
Nieplocha, J.
,
Littlefield, R.
, and
Rosing, M.
1995.
Beyond message passing: A case for one-sided communication in MPI
. In MPI Developers Conference 1995, University
of Notre Dame, IN.
35.
Saad, Y.
, and
Malevsky, A.
1995.
P_SPARSLIB: A portable library of distributed memory sparse iterative solvers
. In Proceedings of Parallel Computing Technologies (PaCT-95),
Third International Conference, St. Petersburg.
36.
Tang, W.-P.
, and
Wan, W. L.2000.
Sparse approximate inverse smoother for multigrid
. SIAM J. Matrix Anal. Appl.21:
1236-1252
.
37.
Tuminaro, R. S.
,
Shadid, J. N.
, and
Hutchinson, S. A.1998.
Parallel sparse matrix vector multiply software for matrices with data locality
. Concurrency: Practice and Experience10:
229-247
.
38.
Vavasis, S. A.1992.
Preconditioning for boundary integral equations
. SIAM J. Matrix Anal. Appl.13:
905-925
.
