An object-oriented framework for block preconditioning

ABSTRACT

General software for preconditioning the iterative solution of linear systems is greatly lagging behind the literature. This is partly because specific problems and specific matrix and preconditioner data structures in order to be solved efficiently, i.e., multiple implementations of a preconditioner with specialized data structures are required. This article presents a framework to support preconditioning with various, possibly user-defined, data structures for matrices that are partitioned into blocks. The main idea is to define data structures for the blocks, and an upper layer of software which uses these blocks transparently of their data structure. This transparency can be accomplished by using an object-oriented language. Thus, various preconditioners, such as block relaxations and block-incomplete factorizations, only need to be defined once and will work with any block type. In addition, it is possible to transparently interchange various approximate or exact techniques for inverting pivot blocks, or solving systems whose coefficient matrices are diagonal blocks. This leads to a rich variety of preconditioners that can be selected. Operations with the blocks are performed with optimized libraries or fundamental data types. Comparisons with an optimized Fortran 77 code on both workstations and Cray supercomputers show that this framework can approach the efficiency of Fortran 77, as long as suitable block sized and block types are chosen.

REFERENCES

• 1: Owe Axelsson, Iterative solution methods, Cambridge University Press, New York, NY, 1995
• 2: AXELSSON, O., BRINKKEMPER, S., AND IL'IN, V. P. 1984. On some versions of incomplete block-matrix factorization iterative methods. Lin. Alg. Appl. 58, 3-15.
• 3: BARRETT, R., BERRY, M., CHAN, T., DEMMEL, J., DONATO, J., DONGARRA, J., EIJKHOUT, V., POZO, R., ROMINE, C., AND VAN DER VORST, H. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, PA.
• 4: Are Magnus Bruaset , Hans Petter Langtangen, Object-oriented design of preconditioned iterative methods in diffpack, ACM Transactions on Mathematical Software (TOMS), v.23 n.1, p.50-80, March 1997 [doi>10.1145/244768.244776]
• 5: CARNEY, S., HEROUX, M. A., LI, G., AND Wv, K. 1994. A revised proposal for a sparse BLAS toolkit. Tech. Rep. 94-034. Army High Performance Computing Research Center, Minneapolis, MN.
• 6: CHOW, E. AND HEROUX, M.A. 1996. BPKIT block preconditioning toolkit. Tech. Rep. 96/183. Minnesota Supercomputer Institute, Univ. of Minnesota, Minneapolis, MN.
• 7: Edmond Chow , Yousef Saad, Approximate Inverse Techniques for Block-Partitioned Matrices, SIAM Journal on Scientific Computing, v.18 n.6, p.1657-1675, Nov. 1997 [doi>10.1137/S1064827595281575]
• 8: Edmond Chow , Yousef Saad, Approximate Inverse Preconditioners via Sparse-Sparse Iterations, SIAM Journal on Scientific Computing, v.19 n.3, p.995-1023, May 1998 [doi>10.1137/S1064827594270415]
• 9: CLAY, R. L. 1997. ISIS+: Iterative scalable implicit solver (in C++). Sandia National Laboratories, Livermore, CA.
• 10: CONCUS, P., GOLUB, G. H., AND MEURANT, G. 1985. Block preconditioning for the conjugate gradient method. SIAM J. Sci. Stat. Comput. 6, 309-332.
• 11: DEMMEL, J. 1989. LAPACK: A portable linear algebra library for supercomputers. In Proceedings of the 1989 IEEE Control Systems Society Workshop on Computer-Aided Control System Design. IEEE Press, Piscataway, NJ.
• 12: J. J. Dongarra , Jeremy Du Croz , Sven Hammarling , I. S. Duff, A set of level 3 basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.16 n.1, p.1-17, March 1990 [doi>10.1145/77626.79170]
• 13: DONGARRA, J. J., LUMSDAINE, A., NIU, X., Pozo, R., AND REMINGTON, K. 1994. A sparse matrix library in C + + for high performance architectures. In Proceedings of the Object Oriented Numerics Conference (Sun River, OR).
• 14: DONGARRA, J. J., Pozo, R., AND WALKER, D.W. 1993. An object oriented design for high performance linear algebra on distributed memory architectures. In Proceedings of the Object Oriented Numerics Conference (Snowbird, CO).
• 15: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 16: EIJKHOUT, V. 1996. ParPre: A parallel preconditioners package. Manuscript.
• 17: EISENSTAT, S. C. 1981. Efficient implementation of a class of preconditioned conjugate gradient methods. SIAM J. Sci. Stat. Comput. 2, 1-4.
• 18: Qing Fan , P. A. Forsyth , J. R. F. McMacken , Wei-Pai Tang, Performance issues for iterative solvers in device simulation, SIAM Journal on Scientific Computing, v.17 n.1, p.100-117, Jan. 1996 [doi>10.1137/0917009]
• 19: JIANG, H. AND FORSYTH, P.A. 1995. Robust linear and nonlinear strategies for solution of the transonic Euler equations. Comput. Fluids 24, 753-770.
• 20: JONES, M. T. AND PLASSMANN, P. E. 1995. BlockSolve95 users manual: Scalable library software for the parallel solution of sparse linear systems. Tech. Rep. ANL-95/48. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
• 21: KOLOTILINA, L. Y. AND YEREMIN, A. Yu. 1986. On a family of two-level preconditioning of the incomplete block factorization type. Soy. J. Numer. Anal. Model. 1,293-320.
• 22: KOLOTILINA, L. Y., KAPORIN, I. E., AND YEREMIN, A. Yu. 1991. Block SSOR preconditionings for high-order 3D FE systems. Incomplete BSSOR preconditionings. Lin. Alg. Appl. 154-156, 647-674.
• 23: L. Machiels , M. O. Deville, Fortran 90: an entry to object-oriented programming for the solution of partial differential equations, ACM Transactions on Mathematical Software (TOMS), v.23 n.1, p.32-49, March 1997 [doi>10.1145/244768.244774]
• 24: REMINGTON, K. A. AND POZO, R. 1996. NIST sparse BLAS user's guide. Tech. Rep. National Institute of Standards & Tech., Gaithersburg, MD.
• 25: SAAD, Y. 1990. SPARSKIT: A basic tool for sparse matrix computations. Tech. Rep. 90-20. RIACS, NASA Ames Research Center, Moffett Field, CA.
• 26: Youcef Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM Journal on Scientific Computing, v.14 n.2, p.461-469, March 1993 [doi>10.1137/0914028]
• 27: SAAD, Y. 1994. ILUT: A dual threshold incomplete ILU factorization. Num. Lin. Alg. Appl. 1, 4, 387-402.
• 28: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 29: SMITH, B., GROPP, W., AND MCINNES, L. C. 1995. PETSc 2.0 user' manual. Tech. Rep. ANL-95/ll. Argonne National Laboratory, Argonne, IL.
• 30: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 31: UNDERWOOD, R. R. 1976. An approximate factorization procedure based on the block Cholesky decomposition and its use with the conjugate gradient method. Tech. Rep. NEDO-11386. Nuclear Energy Division, General Electric, San Jose, CA.
• 32: Wv, K. AND LI, G. 1995. BKAT: An object-oriented block Krylov accelerator toolkit. Presentation at Cray Research, Inc. Cray Supercomputers, Chippewa Falls, MN. Available from [e-mail].

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Design

Keywords:
block matrices, preconditioners