Subdomain deflation combined with local AMG: a case study using AMGCL library. (English) Zbl 1451.65053

Summary: The paper proposes a combination of the subdomain deflation method and local algebraic multigrid as a scalable distributed memory preconditioner that is able to solve large linear systems of equations. The implementation of the algorithm is made available for the community as part of an open source AMGCL library. The solution targets both homogeneous (CPU-only) and heterogeneous (CPU/GPU) systems, employing hybrid MPI/OpenMP approach in the former and a combination of MPI, OpenMP, and CUDA in the latter cases. The use of OpenMP minimizes the number of MPI processes, thus reducing the communication overhead of the deflation method and improving both weak and strong scalability of the preconditioner. The examples of scalar (single degree of freedom per grid node), Poisson-like, systems as well as non-scalar problems, stemming out of the discretization of the Navier-Stokes equations, are considered in order to estimate performance of the implemented algorithm. A comparison with a traditional global AMG preconditioner based on a well-established Trilinos ML package is provided.


65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
65Y10 Numerical algorithms for specific classes of architectures
Full Text: DOI arXiv


[1] A. Alexandrescu, Modern \(C++\) Design: Generic Programming and Design Patterns Applied (Addison-Wesley, Reading, MA, 2001).
[2] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, Ch.; van der Vorst, H., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994), Philadelphia: SIAM, Philadelphia
[3] Brandt, A.; McCoruick, S.; Huge, J., Sparsity and its Applications (1985), Cambridge: Cambridge Univ. Press, Cambridge
[4] Bröker, O.; Grote, M. J., Sparse approximate inverse smoothers for geometric and algebraic multigrid, Appl. Numer. Math., 41, 61-80 (2002) · Zbl 0995.65129
[5] Cleary, A. J.; Falgout, R. D.; Van Emden, H.; Jones, J. E.; Manteuffel, Th. A.; McCormick, St. F.; Miranda, G. N.; Ruge, J. W., Robustness and scalability of algebraic multigrid, SIAM J. Sci. Comput., 21, 1886-1908 (2000) · Zbl 0959.65049
[6] Dadvand, P.; Rossi, R.; Gil, M.; Martorell, X.; Cotela, J.; Juanpere, E.; Idelsohn, S. R.; Oñate, E., Migration of a generic multi-physics framework to HPC environments, Comput. Fluids, 80, 301-309 (2013) · Zbl 1426.76644
[7] Dadvand, P.; Rossi, R.; Oñate, E., An object-oriented environment for developing finite element codes for multi-disciplinary applications, Arch. Comput. Methods Eng., 17, 253-297 (2010) · Zbl 1360.76130
[8] D. Demidov, ‘‘AMGCL: a C++ library for solution of large sparse linear systems with algebraic multigrid method’’ (2017).
[9] Demidov, D., AMGCL: An efficient, flexible, and extensible algebraic multigrid implementation, Lobachevskii J. Math., 40, 535-546 (2019) · Zbl 1452.65426
[10] Donéa, J.; Huerta, A., Finite Element Methods for Flow Problems (2003), New York: Wiley, New York
[11] Elman, H. C., Preconditioning strategies for models of incompressible flow, J. Sci. Comput., 25, 347-366 (2005) · Zbl 1203.76098
[12] Frank, J.; Vuik, C., On the construction of deflation-based preconditioners, SIAM J. Sci. Comput., 23, 442-462 (2001) · Zbl 0997.65072
[13] Erich Gamma, Design Patterns: Elements of Reusable Object-Oriented Software (Pearson Education, India, 1995). · Zbl 0814.68050
[14] 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. Rep. SAND2006-2649 (Sandia Natl. Labor., 2006).
[15] Gmeiner, B.; Huber, M.; John, L.; Rüde, U.; Wohlmuth, B., A quantitative performance study for stokes solvers at the extreme scale, J. Comput. Sci., 17, 509-521 (2016)
[16] Hénon, P.; Ramet, P.; Roman, J., PASTIX: a high-performance parallel direct solver for sparse symmetric positive definite systems, Parallel Comput., 28, 301-321 (2002) · Zbl 0984.68208
[17] Hogg, J.; Scott, J., New parallel sparse direct solvers for multicore architectures, Algorithms, 6, 702-725 (2013) · Zbl 1461.65063
[18] Lin, P.; Bettencourt, M.; Domino, S.; Fisher, T.; Hoemmen, M.; Hu, J.; Phipps, E.; Prokopenko, A.; Rajamanickam, S.; Siefert, Ch., Towards extreme-scale simulations for low mach fluids with second-generation trilinos, Parallel Proces. Lett., 24, 1442005 (2014)
[19] Mathews, J.; Walker, R. L., Mathematical Methods of Physics (1970), New York: W.A. Benjamin, New York
[20] Nabben, R.; Vuik, C., A comparison of deflation and the balancing preconditioner, SIAM J. Sci. Comput., 27, 1742-1759 (2006) · Zbl 1105.65049
[21] Ruge, J. W.; Stüben, K., Multigrid Methods (1987), Philadelphia: SIAM, Philadelphia
[22] Yousef Saad, Iterative Methods for Sparse Linear Systems (SIAM, Philadelphia, 2003). · Zbl 1031.65046
[23] B. Schäling, The Boost \(C++\) Libraries (XML Press, Aufl. Laguna Hills, CA, 2014).
[24] Sleijpen, G. L. G.; Fokkema, D. R., BiCGstab (l) for linear equations involving unsymmetric matrices with complex spectrum, Electron. Trans. Numer. Anal., 1, 11-32 (1993) · Zbl 0820.65016
[25] Smith, B.; Bjorstad, P.; Gropp, W., Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations (2004), Cambridge: Cambridge Univ. Press, Cambridge
[26] Stuben, K., “Algebraic multigrid (AMG): an introduction with applications,” GMD Report 70 (1999), Germany: GMD, St. Augustin, Germany
[27] Tang, J. M.; Nabben, R.; Vuik, C.; Erlangga, Y. A., Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods, SIAM J. Sci. Comput., 39, 340-370 (2009) · Zbl 1203.65073
[28] J. M. Tang and C. Vuik, New Variants of Deflation Techniques for Bubbly Flow Problems (Delft Univ. Technol., Delft, 2006). · Zbl 1235.76043
[29] Trottenberg, U.; Oosterlee, C.; Schüller, A., Multigrid (2001), London: Academic, London
[30] Stefan Turek, Efficient Solvers for Incompressible Flow Problems: An Algorithmic and Computational Approach (Springer, Berlin, Heidelberg, 1999). · Zbl 0930.76002
[31] Vuik, C.; Segal, A.; Meijerink, J. A., An efficient preconditioned CG method for the solution of a class of layered problems with extreme contrasts in the coefficients, J. Comput. Phys., 152, 385-403 (1999) · Zbl 0945.76048
[32] Meier Yang, U., BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math., 41, 155-177 (2002) · Zbl 0995.65128
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.