More Web Proxy on the site http://driver.im/

research-article

MLD2P4: A Package of Parallel Algebraic Multilevel Domain Decomposition Preconditioners in Fortran 95

Authors:

Pasqua D’Ambra,

Daniela Di Serafino,

Salvatore FilipponeAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 3

Article No.: 30, Pages 7 - 23

https://doi.org/10.1145/1824801.1824808

Published: 01 September 2010 Publication History

Abstract

Domain decomposition ideas have long been an essential tool for the solution of PDEs on parallel computers. In recent years many research efforts have been focused on recursively employing domain decomposition methods to obtain multilevel preconditioners to be used with Krylov solvers. In this context, we developed MLD2P4 (MultiLevel Domain Decomposition Parallel Preconditioners Package based on PSBLAS), a package of parallel multilevel preconditioners that combines additive Schwarz domain decomposition methods with a smoothed aggregation technique to build a hierarchy of coarse-level corrections in an algebraic way. The design of MLD2P4 was guided by objectives such as extensibility, flexibility, performance, portability, and ease of use. They were achieved by following an object-based approach while using the Fortran 95 language, as well as by employing the PSBLAS library as a basic framework. In this article, we present MLD2P4 focusing on its design principles, software architecture, and use.

References

[1]

}}Aprovitola, A., D’Ambra, P., Denaro, F., di Serafino, D., and Filippone, S. 2010. Scalable algebraic multilevel preconditioners with application to CFD. In Proceedings of the 20th International Conference on Parallel Computational Fluid Dynamics. Lecture Notes in Computational Science and Engineering, vol. 14, Springer-Verlag, Berlin. To appear.

[2]

}}Balay, S., Buschelman, K., Eijkhout, V., Gropp, W. D., Kaushik, D., Knepley, M. G., Curfman McInnes, L., Smith, B. F., and Zhang, H. 2007. PETSc users manual. Tech. rep. ANL-95/11 - revision 2.3.3, Argonne National Laboratory, Argonne, II. (See also http://www.mcs.anl.gov/petsc/petsc-as/.)

[3]

}}Bank, R. E. and Douglas, C. C. 1993. Sparse matrix multiplication package (SMMP). Adv. Comput. Math. 1, 1, 127--137.

[4]

}}Brandt, A. 1977. Multi-Level adaptive solutions to boundary value problems. Math. Comput. 31, 333--390.

[5]

}}Brandt, A. 2002. Multiscale scientific computation: Review 2001. In Multiscale and Multiresolution Methods: Theory and Applications, T. J. Barth, T. Chan, and R. Haimes, Eds., Lecture Notes in Computational Science and Engineering. vol. 20, Springer-Verlag, Berlin, 1--96.

[6]

}}Brezina, M. and Vaněk, P. 1999. A black-box iterative solver based on a two-level Schwarz method. Comput. 63, 3, 233--263.

Digital Library

[7]

}}Buttari, A., D’Ambra, P., di Serafino, D., and Filippone, S. 2006. Extending PSBLAS to build parallel Schwarz preconditioners. In Applied Parallel Computing, J. Dongarra, K. Madsen, and J. Wasniewski, Eds. Lecture Notes in Computer Science, vol. 3732. Springer-Verlag, Berlin, Germany, 593--602.

Digital Library

[8]

}}Buttari, A., D’Ambra, P., di Serafino, D., and Filippone, S. 2007a. 2LEV-D2P4: A package of high-performance preconditioners for scientific and engineering applications. Appl. Algebra Engin. Comm. Comput. 18, 3, 223--239.

[9]

}}Buttari, A., Eijkhout, V., Langou, J., and Filippone, S. 2007b. Performance optimization and modeling of blocked sparse kernels. Int. J. High Perf. Comput. Appl. 21, 4, 467--484.

Digital Library

[10]

}}Cai, X.-C. and Saad, Y. 1996. Overlapping domain decomposition algorithms for general sparse matrices. Numer. Linear Algebra Appl. 3, 3, 221--237.

[11]

}}Cai, X.-C. and Sarkis, M. 1999. A restricted additive Schwarz preconditioner for general sparse linear systems. SIAM J. Sci. Comput. 21, 2, 792--797.

Digital Library

[12]

}}Chan, T. F. and Mathew, T. P. 1994. Domain decomposition algorithms. In Acta numerica, 1994. Acta Numer. Cambridge University Press, Cambridge, UK, 61--143.

[13]

}}D’Ambra, P., di Serafino, D., and Filippone, S. 2007. On the development of PSBLAS-based parallel two-level Schwarz preconditioners. Appl. Numer. Math. 57, 11-12, 1181--1196.

Digital Library

[14]

}}D’Ambra, P., di Serafino, D., and Filippone, S. 2009. MLD2P4 User’s and Reference Guide. http://www.mld2p4.it.

[15]

}}Davis, T. A. 2004. Algorithm 832: UMFPACK V4.3---An unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30, 2, 196--199.

Digital Library

[16]

}}Demmel, J. W., Eisenstat, S. C., Gilbert, J. R., Li, X. S., and Liu, J. W. H. 1999a. A supernodal approach to sparse partial pivoting. SIAM J. Matrix Anal. Appl. 20, 3, 720--755.

Digital Library

[17]

}}Demmel, J. W., Gilbert, J. R., and Li, X. S. 1999b. An asynchronous parallel supernodal algorithm for sparse Gaussian elimination. SIAM J. Matrix Anal. Appl. 20, 4, 915--952.

Digital Library

[18]

}}Dongarra, J. J. and Whaley, R. C. 1997. A user’s guide to the blacs v1.1. Tech. rep., LAPACK working note 94. http://www.netlib.org/blacs/lawn94.ps.

[19]

}}Duff, I. S., Heroux, M. A., and Pozo, R. 2002. An overview of the sparse basic linear algebra subprograms: The new standard from the BLAS technical forum. ACM Trans. Math. Softw. 28, 2, 239--267.

Digital Library

[20]

}}Duff, I. S., Marrone, M., Radicati, G., and Vittoli, C. 1997. Level 3 basic linear algebra subprograms for sparse matrices: A user-level interface. ACM Trans. Math. Softw. 23, 3, 379--401.

Digital Library

[21]

}}Efstathiou, E. and Gander, M. J. 2003. Why restricted additive Schwarz converges faster than additive Schwarz. BIT 43, 945--959.

[22]

}}Falgout, R. D. 2006. An introduction to algebraic multigrid. Comput. Sci. Engin. 8, 3, 24--33.

Digital Library

[23]

}}Falgout, R. D., Jones, J. E., and Yang, U. M. 2006. The design and implementation of hypre, a library of parallel high performance preconditioners. In Numerical Solution of Partial Differential Equations on Parallel Computers. Lecture Notes Computer Science Engineering, vol. 51. Springer-Verlag, Berlin, Germany, 267--294. (See also https://computation.llnl.gov/casc/linear_solvers/sls_hypre.html.)

[24]

}}Filippone, S. and Buttari, A. 2008. PSBLAS: User’s and Reference Guide. http://www.ce.uniroma2.it/psblas/.

[25]

}}Filippone, S. and Colajanni, M. 2000. PSBLAS: A library for parallel linear algebra computation on sparse matrices. ACM Trans. Math. Softw. 26, 4, 527--550. (See also http://www.ce.uniroma2.it/psblas/.)

Digital Library

[26]

}}Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns. Addison-Wesley.

[27]

}}Gee, M. W., Siefert, C. M., Hu, J. J., Tuminaro, R. S., and Sala, M. G. 2006. ML 5.0 smoothed aggregation user’s guide. Tech. rep. SAND2006-2649, Sandia National Laboratories, Albuquerque, NM, and Livermore, CA.

[28]

}}Göddeke, D., Strzodka, R., Jamaludin, M.-Y., M ^c Cormick, P., Wobker, H., Becker, C., and Turek, S. 2008. Using GPUs to improve multigrid solver performance on a cluster. Int. J. Comput. Sci. Engin. 4, 36--55.

Digital Library

[29]

}}Henson, V. E. and Yang, U. M. 2000. BoomerAMG: A parallel algebraic multigrid solver and preconditioner. Appl. Numer. Math. 41, 155--177.

Digital Library

[30]

}}Heroux, M. A., Bartlett, R. A., Howle, V. E., Hoekstra, R. J., Hu, J. J., Kolda, T. G., Lehoucq, R. B., Long, K. R., Pawlowski, R. P., Phipps, E. T., Salinger, A. G., Thornquist, H. K., Tuminaro, R. S., Willenbring, J. M., Williams, A., and Stanley, K. S. 2005. An overview of the Trilinos project. ACM Trans. Math. Softw. 31, 3, 397--423.

Digital Library

[31]

}}Keyes, D. 2003. Domain decomposition methods in the mainstream of computational science. In Proceedings of the 14th International Conference on Domain Decomposition Methods. UNAM Press, 79--93.

[32]

}}Keyes, D. E., Saad, Y., and Truhlar, D. G. 1995. Think globally, act locally: An introduction to domain-based parallelism and problem decomposition methods. In Domain-Based Parallelism and Problem Decomposition Methods in Computational Science and Engineering, D. E. Keyes, Y. Saad, and D. G. Truhlar, Eds. SIAM, Philadelphia, PA.

[33]

}}Mandel, J., Brezina, M., and Vaněk, P. 1999. Energy optimization of algebraic multigrid bases. Comput. 62, 3, 205--228.

Digital Library

[34]

}}Saad, Y. 2003. Iterative Methods for Sparse Linear Systems, 2nd Ed. Society for Industrial and Applied Mathematics, Philadelphia, PA.

Digital Library

[35]

}}Saad, Y. and Sosonkina, M. 2004. pARMS: A package for the parallel iterative solution of general large sparse linear systems user’s guide. Tech. rep. UMSI2004-8, Minnesota Supercomputing Institute, Minneapolis, MN.

[36]

}}Sala, M. and Tuminaro, R. S. 2008. A new Petrov-Galerkin smoothed aggregation precondiioner for nonsymmetric linear systems. SIAM J. Sci. Comput. 31, 1, 143--166.

Digital Library

[37]

}}Simpson, A. D., Bull, M., and Hill, J. 2008. Identification and categorisation of applications and initial benchmarks suite. http://www.prace-project.eu/documents/Identification_and_ Categorisatio_of_Applications_and_Initial_Benchmark_ Suite_final.pdf.

[38]

}}Smith, B. F., Bjørstad, P. E., and Gropp, W. D. 1996. Domain Decomposition. Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, Cambridge, UK.

Digital Library

[39]

}}Snir, M., Otto, S., Huss-Lederman, S., Walker, D. W., and Dongarra, J. J. 1998. MPI: The Complete Reference. Vol. 1 -- The MPI Core, 2nd Ed. Scientific and Engineering Computation. The MIT Press, Cambridge, MA.

Digital Library

[40]

}}Stitt, T. and Robinson, T. 2008. A survey on training and education needs for petascale computing. http://www.prace-project.eu/documents/D3.3.1_document_final.pdf.

[41]

}}Stüben, K. 1999. Algebraic multigrid (AMG): An introduction with applications. Tech. rep. 70, GMD, Schloss Birlinghoven, Sankt Augustin, Germany.

[42]

}}Tuminaro, R. S., Heroux, M. A., Hutchinson, S. A., and Shadid, J. N. 1999. Official Aztec user’s guide - version 2.1. (See also http://www.cs.sandia.gov/CRF/aztec1.html.)

[43]

}}Tuminaro, R. S. and Tong, C. 2000. Parallel smoothed aggregation multigrid: Aggregation strategies on massively parallel machines. In Proceedings of the ACM/IEEE Conference on Supercomputing. CDROM, Dallas, TX.

Digital Library

[44]

}}Vaněk, P., Mandel, J., and Brezina, M. 1996. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Comput. 56, 3, 179--196.

Cited By

Owen HLehmkuhl OD’Ambra PDurastante FFilippone S(2024)Alya toward exascale: algorithmic scalability using PSCToolkitThe Journal of Supercomputing10.1007/s11227-024-05989-y80:10(13533-13556)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-05989-y
Bernaschi MCelestini AVella FD'Ambra P(2023)A Multi-GPU Aggregation-Based AMG Preconditioner for Iterative Linear SolversIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.328723834:8(2365-2376)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3287238
D’Ambra PDurastante FFilippone S(2023)Parallel Sparse Computation ToolkitSoftware Impacts10.1016/j.simpa.2022.100463(100463)Online publication date: Jan-2023
https://doi.org/10.1016/j.simpa.2022.100463
Show More Cited By

Index Terms

MLD2P4: A Package of Parallel Algebraic Multilevel Domain Decomposition Preconditioners in Fortran 95

Recommendations

A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids

In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), ...
Parallel subdomain solver strategies for the algebraic additive Schwarz preconditioner

Hybrid domain-decomposition method with two levels of domain partitioning.Solution of the local problem by ShyLU or other parallel approximation techniques.Proposal of an inexact QR factorization to be used within ShyLU.Comparisons of parallel ...
Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in Hypre and PETSc
^* Copper Mountain Special Issue on Iterative Methods

We describe our software package Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) recently publicly released. BLOPEX is available as a stand-alone serial library, as an external package to PETSc (Portable, Extensible Toolkit for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 37, Issue 3

September 2010

296 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1824801

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2010

Accepted: 01 May 2010

Revised: 01 January 2010

Received: 01 March 2009

Published in TOMS Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Ministero dell'Istruzione, dell'Università e della Ricerca

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Owen HLehmkuhl OD’Ambra PDurastante FFilippone S(2024)Alya toward exascale: algorithmic scalability using PSCToolkitThe Journal of Supercomputing10.1007/s11227-024-05989-y80:10(13533-13556)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-05989-y
Bernaschi MCelestini AVella FD'Ambra P(2023)A Multi-GPU Aggregation-Based AMG Preconditioner for Iterative Linear SolversIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.328723834:8(2365-2376)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3287238
D’Ambra PDurastante FFilippone S(2023)Parallel Sparse Computation ToolkitSoftware Impacts10.1016/j.simpa.2022.100463(100463)Online publication date: Jan-2023
https://doi.org/10.1016/j.simpa.2022.100463
Bernaschi MD’Ambra PPasquini D(2020)BootCMatchG: An adaptive Algebraic MultiGrid linear solver for GPUsSoftware Impacts10.1016/j.simpa.2020.100041(100041)Online publication date: Nov-2020
https://doi.org/10.1016/j.simpa.2020.100041
Abdullahi Hassan ACardellini VD’Ambra Pdi Serafino DFilippone S(2019)Efficient Algebraic Multigrid Preconditioners on Clusters of GPUsParallel Processing Letters10.1142/S012962641950001429:01(1950001)Online publication date: 10-May-2019
https://doi.org/10.1142/S0129626419500014
Bertaccini DDurastante F(2017)Solving mixed classical and fractional partial differential equations using short---memory principle and approximate inversesNumerical Algorithms10.1007/s11075-016-0186-874:4(1061-1082)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s11075-016-0186-8
(2016)Sparse approximate inverse preconditioners on high performance GPU platformsComputers & Mathematics with Applications10.1016/j.camwa.2015.12.00871:3(693-711)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.camwa.2015.12.008
D'Ambra PFilippone S(2016)A parallel generalized relaxation method for high-performance image segmentation on GPUsJournal of Computational and Applied Mathematics10.1016/j.cam.2015.04.035293:C(35-44)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.cam.2015.04.035
D’Ambra PTartaglione G(2015)Reprint of Solution of Ambrosio–Tortorelli model for image segmentation by generalized relaxation methodCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2014.10.01821:1-3(225-237)Online publication date: Apr-2015
https://doi.org/10.1016/j.cnsns.2014.10.018
D’Ambra PTartaglione G(2015)Solution of Ambrosio–Tortorelli model for image segmentation by generalized relaxation methodCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2014.06.03620:3(819-831)Online publication date: Mar-2015
https://doi.org/10.1016/j.cnsns.2014.06.036
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents