HSL_MI20: an efficient AMG preconditioner for finite element problems in 3D. (English) Zbl 1183.76799
Summary: Algebraic multigrid (AMG) is one of the most effective iterative methods for the solution of large, sparse linear systems obtained from the discretization of second-order scalar elliptic self-adjoint partial differential equations. It can also be used as a preconditioner for Krylov subspace methods. In this communication, we report on the design and development of a robust, effective and portable Fortran 95 implementation of the classical Ruge-Stüben AMG, which is available as package HSL_MI20 within the HSL mathematical software library. The routine can be used as a ‘black-box’ preconditioner, but it also offers the user a range of options and parameters. Proper tuning of these parameters for a particular application can significantly enhance the performance of an AMG-preconditioned Krylov solver. This is illustrated using a number of examples arising in the unstructured finite element discretization of the diffusion, the convection-diffusion, and the Stokes equations, as well as transient thermal convection problems associated with the Boussinesq approximation of the Navier-Stokes equations in 3D.
MSC:
| 76M10 | Finite element methods applied to problems in fluid mechanics |
| 76R99 | Diffusion and convection |
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
Keywords:
large sparse linear systems; Krylov subspace methods; preconditioning; algebraic multigrid; Fortran 95References:
| [1] | Elman, Finite Elements and Fast Iterative Solvers (2005) · Zbl 1083.76001 |
| [2] | Duff, Direct Methods for Sparse Matrices (1986) |
| [3] | Saad, Iterative Methods for Sparse Linear Systems (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [4] | Dongarra, Numerical Linear Algebra for High-Performance Computers (1998) · Zbl 0914.65014 · doi:10.1137/1.9780898719611 |
| [5] | Mijalković, A component decomposition preconditioning for 3D stress analysis problems, Numerical Linear Algebra and its Applications 9 pp 567– (2002) · Zbl 1071.65548 |
| [6] | Silvester, A black-box multigrid preconditioner for the biharmonic equation, BIT 44 pp 151– (2004) · Zbl 1053.65092 |
| [7] | Powell, Optimal preconditioning for Raviart-Thomas mixed formulation of second-order elliptic problems, SIAM Journal on Matrix Analysis and Applications 25 pp 718– (2004) · Zbl 1073.65128 |
| [8] | Haase, Parallel multigrid 3D Maxwell solvers, Parallel Computing 27 pp 761– (2001) · Zbl 0969.65128 |
| [9] | Hu, Toward an h-independent algebraic multigrid for Maxwell’s equations, SIAM Journal on Scientific Computing 27 pp 1669– (2006) · Zbl 1136.76341 |
| [10] | Briggs, A Multigrid Tutorial (2000) · Zbl 0958.65128 · doi:10.1137/1.9780898719505 |
| [11] | Trottenberg, Multigrid (2001) |
| [12] | Brandt, Algebraic multigrid theory: the symmetric case, Applied Mathematics Computation 19 pp 23– (1986) · Zbl 0616.65037 |
| [13] | Ruge, Multigrid Methods pp 73– (1987) · doi:10.1137/1.9781611971057.ch4 |
| [14] | Vanek, Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing 56 pp 179– (1996) |
| [15] | Brezina, Algebraic multigrid based on element interpolation, SIAM Journal on Scientific Computing 22 (5) pp 1570– (2000) · Zbl 0991.65133 |
| [16] | Jones, AMGe based on element agglomeration, SIAM Journal on Scientific Computing 23 (1) pp 109– (2001) · Zbl 0992.65140 |
| [17] | Krechel, Parallel algebraic multigrid based on subdomain blocking, Parallel Computing 27 pp 1009– (2001) · Zbl 0971.68215 |
| [18] | HSL. A collection of Fortran codes for large-scale scientific computation, 2007. Available from: http://www.cse.clrc.ac.uk/nag/hsl/. |
| [19] | Henson, BoomerAMG: a parallel algebraic multigrid solver and preconditioner, Applied Numerical Mathematics 41 pp 155– (2002) · Zbl 0995.65128 |
| [20] | Falgout, Proceedings of the ICCS 2002 pp 632– (2002) |
| [21] | Heroux M, Hu J, Lehoucq R, Thornquist H, Tuminaro R, Willenbring J, Bartlett R, Howle V, Kolda T, Long K, Hoekstra R, Pawlowski R, Phipps E, Salinger A, Williams A. An Overview of Trilinos. Sandia Report, SAND2003-2927, 2003. · Zbl 1136.65354 |
| [22] | Stüben, Multigrid pp 413– (2001) |
| [23] | Brandt, Multi-level adaptive solutions to boundary-value problems, Mathematics of Computation 31 pp 333– (1977) · Zbl 0373.65054 |
| [24] | De Sterck, Reducing complexity in parallel algebraic multigrid preconditioners, SIAM Journal on Matrix Analysis and Applications 27 pp 1019– (2006) · Zbl 1102.65034 |
| [25] | Stüben, A review of algebraic multigrid, Journal of Computational and Applied Mathematics 128 pp 281– (2001) |
| [26] | Füllenbach T, Stüben K, Mijalković S. Application of algebraic multigrid solver to process simulation problems. Proceedings of the International Conference on Simulattion of Semiconductor Processes and Devices, Seattle, WA, U.S.A., 2000; 225-228. |
| [27] | Stüben K, Clees T. SAMG User’s Manual. Available from: http://www.scai.fhg.de/samg/. |
| [28] | Stüben K, Delaney P, Chmakov S. Algebraic multigrid (AMG) for ground water flow and oil reservoir simulation, 2003. |
| [29] | Clees, Proceedings of the 1st International Conference on Challenges, in Scientific Computing (2003) |
| [30] | Füllenbach, Proceedings of the 4th European Conference on Elliptic and Parabolic Problems pp 399– (2002) |
| [31] | Notay, Recursive Krylov-based multigrid cycles, Numerical Linear Algebra with Applications 15 pp 473– (2008) · Zbl 1212.65132 |
| [32] | Hackbusch, Multi-grid Methods and Applications (1985) · doi:10.1007/978-3-662-02427-0 |
| [33] | Duff IS, Reid JK. MA48 a Fortran code for direct solution of sparse unsymmetric linear systems of equations. Report RAL-93-072, Rutherford Appleton Laboratory, 1993. |
| [34] | Duff, The design of MA48, a code for the direct solution of sparse unsymmetric linear systems of equations, ACM Transactions on Mathematical Software 22 pp 187– (1996) · Zbl 0884.65019 |
| [35] | Anderson, LAPACK User’s Guide (1999) · Zbl 0934.65030 · doi:10.1137/1.9780898719604 |
| [36] | Boyle JW, Mihajlović MD, Scott JA. HSL_MI20: an efficient AMG preconditioner. Technical Report RAL-TR-2007-021, RAL, 2007. |
| [37] | Juel, Three-dimensional free convection in molten gallium, Journal of Fluid Mechanics 436 pp 267– (2001) · Zbl 0967.76519 |
| [38] | Chandrasekhar, Hydrodynamic and Hydromagnetic Stability (1981) |
| [39] | COMSOL, FEMLAB Version 2.3 Reference Manual. COMSOL, 2003. |
| [40] | Dohrmann, A stabilized finite element method for the Stokes problem based on polynomial pressure projections, International Journal for Numerical Methods in Fluids 46 pp 183– (2004) · Zbl 1060.76569 |
| [41] | Kay DA, Gresho PM, Griffiths DF, Silvester DJ. Adaptive time-stepping for incompressible flow Part II: Navier-Stokes equations. Available from: http://eprints.ma.man.ac.uk/1110/.Manchester Institute for Mathematical Sciences (MIMS), Preprint 2008.61, Manchester, U.K. |
| [42] | Arrow, Studies in Nonlinear Programming (1958) |
| [43] | Elman, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM Journal on Numerical Analysis 31 pp 1645– (1994) · Zbl 0815.65041 |
| [44] | Silvester, Fast iterative solution of stabilized Stokes systems. Part II: using general block preconditioners, SIAM Journal on Numerical Analysis 31 pp 1352– (1994) · Zbl 0810.76044 |
| [45] | Wathen, Realistic eigenvalue bounds for the Galerkin mass matrix, IMA Journal of Numerical Analysis 7 pp 449– (1987) · Zbl 0648.65076 |
| [46] | Mihajlović, Efficiency Study of the ’Black-box’ Component Decomposition Preconditioning for Discrete Stress Analysis Problems pp 97– (2004) · Zbl 1086.65519 |
| [47] | Flynn, Natural ventialtion in interconnected chambers, Jounal of Fluid Mechanics 564 pp 139– (2006) |
| [48] | King, A numerical journey to the Earth’s interior, IEEE Transactions on Computing in Science and Engineering 2 pp 12– (1995) |
| [49] | Lees, Convective roll dynamics in liquid 4He near the onset of convection, Physical Review Letters 93 pp 144502– (2004) |
| [50] | Kaddeche, Magnetic stabilization of the buoyant convection between infinite horizontal walls with a horizontal temperature gradient, Journal of Fluid Mechanics 480 pp 185– (2003) · Zbl 1063.76547 |
| [51] | Christon, Computational predictability of time-dependent natural convection flows in enclosures (including a benchmark solution), International Journal for Numerical Methods in Fluids 40 pp 953– (2002) · Zbl 1025.76042 |
| [52] | Govaerts, Numerical Methods for Bifurcations of Dynamic Equilibria (2000) · Zbl 0935.37054 · doi:10.1137/1.9780898719543 |
| [53] | Drazin, Introduction to Hydrodynamic Stability (2002) · Zbl 0997.76001 · doi:10.1017/CBO9780511809064 |
| [54] | Gelfgat, Stability of multiple steady states of convection in laterally heated cavities, Journal of Fluid Mechanics 388 pp 315– (1999) · Zbl 0958.76022 |
| [55] | Le Quere, From onset of unsteadiness to chaos in a differentially heated square cavity, Journal of Fluid Mechanics 359 pp 81– (1998) · Zbl 0916.76055 |
| [56] | Winters, Oscillatory convection in liquid metals in a horizontal temperature gradient, International Journal for Numerical Methods in Engineering 25 pp 401– (1988) · Zbl 0668.76111 |
| [57] | Smethurst CA. A finite element solution of the natural convection problem in 3D. Ph.D. Thesis, University of Manchester, 2008. |
| [58] | Cleary AJ, Falgout RD, Henson VE, Jones JE. Coarse grid selection for parallel algebraic multigrid. Proceedings of the 5th International Symposium on Solving Irregularly Structured Problems in Parallel. Lecture Notes in Computer Science, vol. 1457, 1998. |
| [59] | Heil M, Hazel A. oomph-lib-the object-oriented multi-physics finite element library. Available from: http://www.oomph-lib.org. · Zbl 1323.74085 |
| [60] | Notay Y. An aggregation-based algebraic multigrid method. Report GANMN 08-02, 2009. · Zbl 1206.65133 |
| [61] | Gresho, Incompressible Flow and the Finite Element Method (1998) · Zbl 0941.76002 |
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.
