An object-oriented framework for the development of scalable parallel multilevel preconditioners

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An object-oriented framework for the development of scalable parallel multilevel preconditioners

Full text

Pdf (214 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 32 , Issue 3 (September 2006) table of contents

Pages: 396 - 416

Year of Publication: 2006

ISSN:0098-3500

Author

Marzio Sala

Sandia National Laboratories, Albequerque, NM

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 49, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1163641.1163643 What is a DOI?

ABSTRACT

We present the design of a high-performance object-oriented framework that enables the rapid development and usage of efficient, scalable, and portable implementations of multilevel preconditioners for distributed sparse real matrices, in both serial and (massively) parallel environments. The main feature of the proposed framework is the use of several programming paradigms for the different implementation layers, with a strong emphasis on object-oriented classes and operator overloading for the top layer, and optimized FORTRAN and C code for the layers underneath. We describe an implementation of the proposed framework that is based on the ML library, the algebraic multilevel preconditioning package of Trilinos, which supports state-of-the-art parallel smoothed aggregation methods, and can be used to define general algebraic and geometric multilevel and multigrid preconditioners and solvers. The article demonstrates that we can take advantage of object-oriented programming and operator overloading to obtain intuitive, easy-to-read, and easy-to-develop codes that are at the same time efficient and scalable. Several numerical experiments obtained on serial and parallel computers show that the overhead required by the object-oriented layer is very modest, therefore allowing developers to focus on the new algorithms they are developing and testing, rather than on implementation details.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Allan, B. A., Clay, R. L., Mish, K. D., and Williams, A. B. 1999. ISIS++ reference guide: Iterative scalable implicit solvers in C++ version 1.1. Tech. Rep., Sandia National Laboratories.
	2	Owe Axelsson, Iterative solution methods, Cambridge University Press, New York, NY, 1995
	3	Balay, S., Gropp, G., McInnes, L. C., and Smith, B. 1995. PETSc user's manual. Tech. Rep. ANL-95/11, Argonne National Laboratory.
	4	Barlett, R. 2004. Teuchos::RefCountPtr beginner's guide: An introduction to the Trilinos smart reference-counted pointer class for (almost) automatic dynamic memory management in C++. Tech. Rep. SAND-3268, Sandia National Laboratories.
	5	Barrett, R., Berry, M., Chan, T., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and der Vorst, H. V. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edition. SIAM, Philadelphia, PA.
	6	Brandt, A. 1977. Multilevel adaptive solutions to boundary-value problems. Math. Comp. 31, 333--390.
	7	William L. Briggs , Van Emden Henson , Steve F. McCormick, A multigrid tutorial: second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	8	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]
	9	Edmond Chow , Michael A. Heroux, An object-oriented framework for block preconditioning, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.159-183, June 1998 [doi>10.1145/290200.287639]
	10	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.
	11	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]
	12	Robert D. Falgout , Ulrike Meier Yang, hypre: A Library of High Performance Preconditioners, Proceedings of the International Conference on Computational Science-Part III, p.632-641, April 21-24, 2002
	13	Salvatore Filippone , Michele Colajanni, PSBLAS: a library for parallel linear algebra computation on sparse matrices, ACM Transactions on Mathematical Software (TOMS), v.26 n.4, p.527-550, Dec. 2000 [doi>10.1145/365723.365732]
	14	Golub, G. and van der Vorst, H. 1997. Closer to the solution: Iterative linear solvers. In The State-of-the-Art in Numerical Analysis, I. Duff and G. Watson, Eds. Vol. 63. Oxford University, 63--92.
	15	Anne Greenbaum, Iterative methods for solving linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
	16	Hackbusch, W. 1985a. Multigrid Methods and Applications. Springer Verlag, Berlin.
	17	Hackbusch, W. 1985b. Multigrid Methods and Applications. Computational Mathematics, vol. 4. Springer Verlag, Berlin.
	18	Hackbusch, W. 1994. Iterative Solution of Large Sparse Linear Systems of Equations. Springer Verlag, Berlin.
	19	Van Emden Henson , Ulrike Meier Yang, BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Applied Numerical Mathematics, v.41 n.1, p.155-177, April 2002 [doi>10.1016/S0168-9274(01)00115-5]
	20	Heroux, M. A. 2002. Epetra Reference Manual, 2.0 ed. http://software.sandia.gov/trilinos/packages/epetra/doxygen/latex/EpetraReferenceManual.pdf.
	21	Hestenes, M. and Steifel, E. 1952. Method of conjugate gradients for solving linear systems. J. Res. 20, 409--436.
	22	Caroline Lasser , Andrea Toselli, An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems, Mathematics of Computation, v.72 n.243, p.1215-1238, July 2003 [doi>10.1090/S0025-5718-03-01484-4]
	23	Quarteroni, A., Sacco, R., and Saleri, F. 2000. Numerical Mathematics. Springer Verlag, New York.
	24	Quarteroni, A. and Valli, A. 1999. Domain Decomposition Methods for Partial Differential Equations. Oxford University Press, Oxford, UK.
	25	Ruge, J. and Stuben, K. 1987. Algebraic multigrid (AMG). In Multigrid Methods, S. McCormick, Ed. Frontiers in Applied Mathematics, SIAM, Philadelphia, PA.
	26	Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
	27	Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
	28	Saad, Y. and Sosonkina, M. 2003. PARMS: A package for the parallel iterative solution of general large sparse linear systems, user's guide. Tech. Rep., University of Minnesota.
	29	Sala, M. 2004a. Amesos 2.0 reference guide. Tech. Rep. SAND-4820, Sandia National Laboratories Albequerque, NM, 87185.
	30	Sala, M. 2004b. Analysis of two-level domain decomposition preconditioners based on aggregation. Math. Model. Numer. Anal. 38, 5, 765--780.
	31	Sala, M. and Heroux, M. 2005. Robust algebraic preconditioners with IFPACK 3.0. Tech. Rep. SAND-0662, Sandia National Laboratories Albequerque, NM, 87185.
	32	Sala, M., Hu, J., and Tuminaro, R. 2004. ML 3.1 smoothed aggregation user's guide. Tech. Rep. SAND-4819, Sandia National Laboratories Albequerque, NM, 87185.
	33	Sala, M., Spotz, W. F., and Heroux, M. A. 2006. PyTrilinos: Using high-performance parallel distributed memory libraries via Python. Submitted.
	34	Barry F. Smith , Petter E. Bjørstad , William D. Gropp, Domain decomposition: parallel multilevel methods for elliptic partial differential equations, Cambridge University Press, New York, NY, 1996
	35	Stuben, K. 2000. Algebraic multigrid (AMG): An introduction with applications. In Multigrid, A. Schuller et al., Eds. Academic Press, London.
	36	Tuminaro, R., Heroux, M., Hutchinson, S., and Shadid, J. 1999. Official Aztec user's guide: Version 2.1. Tech. Rep. Sand99-8801J, Sandia National Laboratories, Albuquerque NM, 87185.
	37	van der Vorst, H. 1995. Parallel iterative solution methods for linear systems arising from discretized PDE's. Tech. Rep., special course on Parallel Computing in CFD, no. R--807 in AGARD Reports, AGARD, Neuilly-sur-Seine, France, 1995, pp. 3--1--3--39.
	38	David Vandevoorde , Nicolai M. Josuttis, C++ Templates, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
	39	Vanek, P. 1992. Acceleration of convergence of a two-level algorithm by smooth transfer operators. Appl. Math. 37, 265--274.
	40	Vanek, P. 1995. Fast multigrid solvers. Appl. Math. 40, 1--20.
	41	Vanek, P., Mandel, J., and Brezina, M. 1996. Algebraic multigrid based on smoothed aggregation for second- and fourth-order problems. Comput. 56, 179--196.