AMGCL: an efficient, flexible, and extensible algebraic multigrid implementation. (English) Zbl 1452.65426
Summary: The paper presents AMGCL – an opensource C++ library implementing the algebraic multigrid method (AMG) for solution of large sparse linear systems of equations, usually arising from discretization of partial differential equations on an unstructured grid. The library supports both shared and distributed memory computation, allows to utilize modern massively parallel processors via OpenMP, OpenCL, or CUDA technologies, has minimal dependencies, and is easily extensible. The design principles behind AMGCL are discussed and it is shown that the code performance is on par with alternative implementations.
MSC:
| 65Y15 | Packaged methods for numerical algorithms |
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
| 65Y10 | Numerical algorithms for specific classes of architectures |
References:
| [1] | A. Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied (Addison-Wesley, Reading, MA, 2001). |
| [2] | A. H. Baker, E. R. Jessup, and Th. Manteuffel, “A technique for accelerating the convergence of restarted GMRES,” SIAM J. Matrix Anal. Appl. 26, 962-984 (2005). · Zbl 1086.65025 · doi:10.1137/S0895479803422014 |
| [3] | S. Balay, Sh. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, and Hong Zhang, “PETSc users manual,” Tech. Rep. ANL-95/11, Rev. 3.7 (Argonne Natl. Labor., 2016). |
| [4] | R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, Ch. Romine, and H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (SIAM, Philadelphia, 1994). · Zbl 0814.65030 · doi:10.1137/1.9781611971538 |
| [5] | N. Bell, S. Dalton, and L. N. Olson, “Exposing fine-grained parallelism in algebraic multigrid methods,” SIAM J. Sci. Comput. 34 (4), C123-C152 (2012). · Zbl 1253.65041 · doi:10.1137/110838844 |
| [6] | A. Brandt, S. McCoruick, and J. Huge, “Algebraic multigrid (AMG) for sparse matrix equations,” in Sparsity and its Applications, Ed. by D. J. Evans (Cambridge University Press, 1985), p. 257. |
| [7] | O. Bröker and M. J. Grote, “Sparse approximate inverse smoothers for geometric and algebraic multigrid,” Appl. Numer. Math. 41, 61-80 (2002). · Zbl 0995.65129 · doi:10.1016/S0168-9274(01)00110-6 |
| [8] | A. J. Cleary, R. D. Falgout, H. van Emden, J. E. Jones, Th. A. Manteuffel, S. F. McCormick, G. N. Miranda, and J. W. Ruge, “Robustness and scalability of algebraic multigrid,” SIAM J. Sci. Comput. 21, 1886-1908 (2000). · Zbl 0959.65049 · doi:10.1137/S1064827598339402 |
| [9] | P. Dadvand, R. Rossi, M. Gil, X. Martorell, J. Cotela, E. Juanpere, S. R. Idelsohn, and E. Oñate, “Migration of a generic multi-physics framework to HPC environments,” Comput. Fluids 80, 301-309 (2013). · Zbl 1426.76644 · doi:10.1016/j.compfluid.2012.02.004 |
| [10] | P. Dadvand, R. Rossi, and E. Oñate, “An object-oriented environment for developing finite element codes for multi-disciplinary applications,” Arch. Comput. Methods Eng. 17, 253-297 (2010). · Zbl 1360.76130 · doi:10.1007/s11831-010-9045-2 |
| [11] | L. Dagum and R. Menon, “OpenMP: an industry standard API for shared-memory programming,” IEEE Comput. Sci. Eng. 5, 46-55 (1998). · doi:10.1109/99.660313 |
| [12] | S. Dalton, N. Bell, L. Olson, and M. Garland, “Cusp: Generic parallel algorithms for sparse matrix and graph computations,” Version 0.5.0 (2014). http://cusplibrary.github.io. |
| [13] | D. E. Demidov and D. V. Shevchenko, “Modification of algebraic multigrid for effective GPGPU-based solution of nonstationary hydrodynamics problems,” J. Comput. Sci. 3, 460-462 (2012). · doi:10.1016/j.jocs.2012.08.008 |
| [14] | D. Demidov and R. Rossi, “Navier-Stokes problem for distributed memory AMGCL benchmarks,” (2018). https://doi.org/10.5281/zenodo.1231818 |
| [15] | D. Demidov and R. Rossi, “Navier-Stokes problem for shared memory AMGCL benchmarks,” (2018). https://doi.org/10.5281/zenodo.1231961 |
| [16] | J. (Jean) Donéa and A. Huerta, Finite Element Methods for Flow Problems (Wiley, 2003). |
| [17] | R. D. Falgout and U. M. Yang, “Hypre: a library of high performance preconditioners,” in Proceedings of the International Conference on Computational Science (Springer, 2002), pp. 632-641. · Zbl 1056.65046 |
| [18] | D. R. Fokkema, Enhanced Implementation of BiCGstab (l) for Solving Linear Systems of Equations (Univ. Utrecht, 1996). |
| [19] | M. W. Gee, C. M. Siefert, J. J. Hu, R. S. Tuminaro, and M. G. Sala, “ML 5.0 smoothed aggregation user’s guide,” Tech. Report SAND2006-2649 (Sandia Natl. Laboratories, 2006). |
| [20] | B. Gmeiner, M. Huber, L. John, U. Rüde, and B. Wohlmuth, “A quantitative performance study for stokes solvers at the extreme scale,” J. Comput. Sci. 17, 509-521 (2016). · doi:10.1016/j.jocs.2016.06.006 |
| [21] | S. Gries, K. Stüben, G. L. Brown, D. Chen, D. A. Collins, et al., “Preconditioning for efficiently applying algebraic multigrid in fully implicit reservoir simulations,” SPE J. 19, 726-736 (2014). · doi:10.2118/163608-PA |
| [22] | P. Hénon, P. Ramet, and J. Roman, “PASTIX: a high-performance parallel direct solver for sparse symmetric positive definite systems,” Parallel Comput. 28, 301-321 (2002). · Zbl 0984.68208 · doi:10.1016/S0167-8191(01)00141-7 |
| [23] | J. Hogg and J. Scott, “New parallel sparse direct solvers for multicore architectures,” Algorithms 6, 702-725 (2013). · Zbl 1461.65063 · doi:10.3390/a6040702 |
| [24] | K.-A. Lie, An Introduction to Reservoir Simulation Using MATLAB: User Guide for the Matlab Reservoir Simulation Toolbox (MRST) (SINTEF ICT, Norway, 2016). · Zbl 1425.76001 |
| [25] | J. W. Ruge and K. Stüben, “Algebraic multigrid,” in Multigrid Methods (SIAM, 1987), pp. 73-130. |
| [26] | K. Rupp, F. Rudolf, and J. Weinbub, “ViennaCL “— a high level linear algebra library for GPUs and multicore CPUs,” in Proceedings of the International Workshop on GPUs and Scientific Applications, 2010, pp. 51-56. |
| [27] | Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM, 2003). · Zbl 1031.65046 |
| [28] | M. Sala and R. S. Tuminaro, “A new Petrov-Galerkin smoothed aggregation preconditioner for nonsymmetric linear systems,” SIAM J. Sci. Comput. 31, 143-166 (2008). · Zbl 1183.76673 · doi:10.1137/060659545 |
| [29] | J. Sanders and E. Kandrot, CUDA by Example: An Introduction to General-Purpose GPU Programming (Addison-Wesley Professional, Reading, MA, 2010). |
| [30] | P. Sonneveld and M. B. van Gijzen, “IDR(s): a family of simple and fast algorithms for solving large nonsymmetric systems of linear equations,” SIAM J. Sci. Comput. 31, 1035-1062 (2008). · Zbl 1190.65053 · doi:10.1137/070685804 |
| [31] | J. E. Stone, D. Gohara, and G. Shi, “OpenCL: a parallel programming standard for heterogeneous computing systems,” Comput. Sci. Eng. 12 (3), 66-73 (2010). · doi:10.1109/MCSE.2010.69 |
| [32] | Stuben, K., Algebraic multigrid (AMG): an introduction with applications (1999), St. Augustin, Germany |
| [33] | U. Trottenberg, C. Oosterlee, and A. Schüller, Multigrid (Academic, London, 2001). · Zbl 0976.65106 |
| [34] | P. Vaněk, J. Mandel, and M. Brezina, “Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems,” Computing 56, 179-196 (1996). · Zbl 0851.65087 · doi:10.1007/BF02238511 |
| [35] | R. Verfurth, “A combined conjugate gradient-multi-grid algorithm for the numerical solution of the Stokes problem,” IMA J. Numer. Anal. 4, 441-455 (1984). · Zbl 0563.76028 · doi:10.1093/imanum/4.4.441 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
