×

A novel algebraic multigrid approach based on adaptive smoothing and prolongation for ill-conditioned systems. (English) Zbl 1433.65069

The authors propose a novel algebraic multigrid approach based on adaptive smoothing and prolongation. First they follow the perspective of adaptive and bootstrap algebraic multigrids, which assumes no information about the near-null space, and construct the space of smooth vectors by testing an initial set of candidates. The second part of the work consists in the use of adaptive pattern factorized sparse approximate inverses as a smoothers. Numerical experiments and comparisons with other solvers for some real-world test cases are also presented.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] M. Adams, {\it Evaluation of three unstructured multigrid methods on 3D finite element problems in solid mechanics}, Internat. J. Numeri. Methods Engrg., 55 (2002), pp. 519-534, . · Zbl 1076.74547
[3] S. Badia, A. F. Mart�n, and J. Principe, {\it Multilevel balancing domain decomposition at extreme scales}, SIAM J. Sci. Comput., 38 (2016), pp. C22-C52, . · Zbl 1334.65217
[4] R. Baggio, A. Franceschini, N. Spiezia, and C. Janna, {\it Rigid body modes deflation of the preconditioned conjugate gradient in the solution of discretized structural problems}, Comput. & Structures, 185 (2017), pp. 15-26, .
[5] M. Benzi, {\it Preconditioning techniques for large linear systems: A survey}, J. Comput. Phys., 182 (2002), pp. 418-477, . · Zbl 1015.65018
[6] M. Benzi, C. D. Meyer, and M. Tuma, {\it A sparse approximate inverse preconditioner for the conjugate gradient method}, SIAM J. Sci. Comput., 17 (1996), pp. 1135-1149, . · Zbl 0856.65019
[7] M. Bernaschi, M. Bisson, C. Fantozzi, and C. Janna, {\it A factored sparse approximate inverse preconditioned conjugate gradient solver on graphics processing units}, SIAM J. Sci. Comput., 38 (2016), pp. C53-C72, . · Zbl 1336.65036
[8] A. Brandt, {\it Algebraic multigrid theory: The symmetric case}, Appl. Math. Comput., 19 (1986), pp. 23-56, . · Zbl 0616.65037
[9] A. Brandt, J. Brannick, K. Kahl, and I Livshits, {\it An Algebraic Distances Measure of AMG Strength of Connection}, arXiv:1106.5990, 2012.
[10] A. Brandt, J. Brannick, K. Kahl, and I. Livshits, {\it Bootstrap AMG}, SIAM J. Sci. Comput., 33 (2011), pp. 612-632, . · Zbl 1227.65120
[11] A. Brandt, J. Brannick, K. Kahl, and I. Livshits, {\it Bootstrap algebraic multigrid: Status report, open problems, and outlook}, Numer. Math. Theory Methods Appl., 8 (2015), 112-135, . · Zbl 1340.65289
[12] A. Brandt, S. McCormick, and J. Ruge, {\it Algebraic multigrid AMG for sparse matrix \nobreak equations}, in Sparsity and Its Applications, D. J. Evans, ed., Cambridge University Press, Cambridge, UK, 1984, pp. 257-284, . · Zbl 0548.65014
[13] A. Brandt and D. Ron, {\it Multigrid solvers and multilevel optimization strategies}, in Multilevel Optimization in VLSICAD, Combin. Optim. 14, Springer, Boston, MA, 2003, pp. 1-69, . · Zbl 1046.65043
[14] J. Brannick, F. Cao, K. Kahl, R. Falgout, and X. Hu, {\it Optimal interpolation and compatible relaxation in classical algebraic multigrid}, SIAM J. Sci. Comput., 40 (2018), pp. A1473-A1493, . · Zbl 1448.65258
[15] M. Brezina, A. J. Cleary, R. D. Falgout, V. E. Henson, J. E. Jones, T. A. Manteuffel, S. F. McCormick, and J. W. Ruge, {\it Algebraic multigrid based on element interpolation (AMGe)}, SIAM J. Sci. Comput., 22 (2001), pp. 1570-1592, . · Zbl 0991.65133
[16] M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick, and J. Ruge, {\it Adaptive smoothed aggregation \((α\) SA) multigrid}, SIAM Rev., 47 (2005), pp. 317-346, . · Zbl 1075.65042
[17] M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick, and J. Ruge, {\it Adaptive algebraic multigrid}, SIAM J. Sci. Comput., 27 (2006), pp. 1261-1286, . · Zbl 1100.65025
[18] M. Brezina, C. Ketelsen, T. Manteuffel, S. McCormick, M. Park, and J. Ruge, {\it Relaxation-corrected bootstrap algebraic multigrid (rBAMG)}, Numer. Linear Algebra Appl., 19 (2012), pp. 178-193, . · Zbl 1274.65269
[19] T. Chartier, R. D. Falgout, V. E. Henson, J. Jones, T. Manteuffel, S. McCormick, J. Ruge, and P. S. Vassilevski, {\it Spectral AMGe \((ρ\) AMGe)}, SIAM J. Sci. Comput., 25 (2003), pp. 1-26, . · Zbl 1057.65096
[20] M. Christie, et al., {\it Tenth SPE comparative solution project: A comparison of upscaling techniques}, in Proceedings of the SPE Reservoir Simulation Symposium, Society of Petroleum Engineers, 2001, .
[21] P. D’ambra, S. Filippone, and P. S. Vassilevski, {\it BootCMatch: A software package for bootstrap AMG based on graph weighted matching}, ACM Trans. Math. Software, 44 (2018), pp. 39:1-39:25, . · Zbl 1484.65059
[22] T. A. Davis and Y. Hu, {\it The University of Florida Sparse Matrix Collection}, ACM Trans. Math. Software, 38 (2011), pp. 1:1-1:25, . · Zbl 1365.65123
[23] V. Dolean, P. Jolivet, and F. Nataf, {\it An Introduction to Domain Decomposition Methods: Algorithms, Theory and Parallel Implementation}, SIAM, Philadelphia, 2015. · Zbl 1364.65277
[24] R. D. Falgout and P. S. Vassilevski, {\it On generalizing the algebraic multigrid framework}, SIAM J. Numer. Anal., 42 (2004), pp. 1669-1693, . · Zbl 1077.65129
[25] R. D. Falgout and U. M. Yang, {\it Hypre: A library of high performance preconditioners}, in Proceedings of the International Conference on Computational Science-Part III, ICCS ’02, Springer-Verlag, Berlin, 2002, pp. 632-641, . · Zbl 1056.65046
[26] A. Franceschini, V. A. Paludetto Magri, M. Ferronato, and C. Janna, {\it A robust multilevel approximate inverse preconditioner for symmetric positive definite matrices}, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 123-147, . · Zbl 1383.65019
[27] C. Geuzaine and J.-F. Remacle, {\it Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities}, Internat. J. Numer. Methods Engrg., 79 (2009), pp. 1309-1331, . · Zbl 1176.74181
[28] M. J. Grote and T. Huckle, {\it Parallel preconditioning with sparse approximate inverses}, SIAM J. Sci. Comput., 18 (1997), pp. 838-853, . · Zbl 0872.65031
[29] V. E. Henson and P. S. Vassilevski, {\it Element-free AMGe: General algorithms for computing interpolation weights in AMG}, SIAM J. Sci. Comput., 23 (2001), pp. 629-650, . · Zbl 0992.65141
[30] V. E. Henson and U. M. Yang, {\it BoomerAMG: A parallel algebraic multigrid solver and preconditioner}, Appl. Numer. Math., 41 (2002), pp. 155-177, . · Zbl 0995.65128
[31] T. Huckle, {\it Factorized sparse approximate inverses for preconditioning}, J. Supercomputing, 25 (2003), pp. 109-117, . · Zbl 1027.65056
[32] C. Janna and M. Ferronato, {\it Adaptive pattern research for block FSAI preconditioning}, SIAM J. Sci. Comput., 33 (2011), pp. 3357-3380, . · Zbl 1273.65045
[33] C. Janna, M. Ferronato, and G. Gambolati, {\it The use of supernodes in factored sparse approximate inverse preconditioning}, SIAM J. Sci. Comput., 37 (2015), pp. C72-C94, . · Zbl 1327.65062
[34] C. Janna, M. Ferronato, F. Sartoretto, and G. Gambolati, {\it FSAIPACK: A software package for high-performance factored sparse approximate inverse preconditioning}, ACM Trans. Math. Software, 41 (2015), pp. 10:1-10:26, . · Zbl 1369.65052
[35] T. Jonsthovel, M. B. van Gijzen, C. Vuik, and A. Scarpas, {\it On the use of rigid body modes in the deflated preconditioned conjugate gradient method}, SIAM J. Sci. Comput., 35 (2013), pp. B207-B225, . · Zbl 1372.74017
[36] I. E. Kaporin, {\it A preconditioned conjugate-gradient method for solving discrete analogs of differential problems}, Differential Equations, 26 (1990), pp. 897-906. · Zbl 0712.65022
[37] I. E. Kaporin, {\it New convergence results and preconditioning strategies for the conjugate gradient method}, Numer. Linear Algebra Appl., 1 (1994), pp. 179-210, . · Zbl 0837.65027
[38] L. Kolotilina and A. Yeremin, {\it Factorized sparse approximate inverse preconditionings I. Theory}, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 45-58, . · Zbl 0767.65037
[39] R. Li and Y. Saad, {\it Low-rank correction methods for algebraic domain decomposition preconditioners}, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 807-828, . · Zbl 1371.65029
[40] R. Li, Y. Xi, L. Erlandson, and Y. Saad, {\it The Eigenvalues Slicing Library (EVSL): Algorithms, implementation, and software}, SIAM J. Sci. Comput., submitted, . · Zbl 1420.65050
[41] R. Li, Y. Xi, E. Vecharynski, C. Yang, and Y. Saad, {\it A thick-restart lanczos algorithm with polynomial filtering for hermitian eigenvalue problems}, SIAM J. Sci. Comput., 38 (2016), pp. A2512-A2534, . · Zbl 1348.65071
[42] C. Lin and J. Mor�, {\it Incomplete Cholesky factorizations with limited memory}, SIAM J. Sci. Comput., 21 (1999), pp. 24-45, . · Zbl 0941.65033
[43] O. E. Livne and A. Brandt, {\it Lean algebraic multigrid (LAMG): Fast graph laplacian linear solver}, SIAM J. Sci. Comput., 34 (2012), pp. B499-B522, . · Zbl 1253.65045
[44] T. A. Manteuffel, L. N. Olson, J. B. Schroder, and B. S. Southworth, {\it A root-node-based algebraic multigrid method}, SIAM J. Sci. Comput., 39 (2017), pp. S723-S756, . · Zbl 1392.65064
[45] S. F. McCormick and J. W. Ruge, {\it Multigrid methods for variational problems}, SIAM J. Numer. Anal., 19 (1982), pp. 924-929, . · Zbl 0499.65032
[46] Y. Notay, {\it Aggregation-based algebraic multigrid for convection-diffusion equations}, SIAM J. Sci. Comput., 34 (2012), pp. A2288-A2316, . · Zbl 1250.76139
[47] L. N. Olson and J. B. Schroder, {\it PyAMG: Algebraic Multigrid Solvers in Python v}4.0, release 4.0, (2018).
[48] L. N. Olson, J. B. Schroder, and R. S. Tuminaro, {\it A general interpolation strategy for algebraic multigrid using energy minimization}, SIAM J. Sci. Comput., 33 (2011), pp. 966-991, . · Zbl 1233.65096
[49] Y. Saad, {\it ILUT: A dual threshold incomplete LU factorization}, Numer. Linear Algebra Appl., 1 (1994), pp. 387-402, . · Zbl 0838.65026
[50] Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, Classics in Appl. Math. 66, SIAM, Philadelphia, 2011, . · Zbl 1242.65068
[51] J. B. Schroder, {\it Smoothed aggregation solvers for anisotropic diffusion}, Numer. Linear Algebra Appl., 19 (2012), pp. 296-312, . · Zbl 1274.65325
[52] K. Stüben, {\it A review of algebraic multigrid}, J. Comput. Appl. Math., 128 (2001), pp. 281-309, . · Zbl 0979.65111
[53] K. Stüben, {\it Algebraic multigrid (AMG): Experiences and comparisons}, Appl. Math. Comput., 13 (1983), pp. 419-451, . · Zbl 0533.65064
[54] W. Tang, {\it Toward an effective sparse approximate inverse preconditioner}, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 970-986, . · Zbl 0937.65056
[55] U. Trottenberg, C. Oosterlee, and A. Schüller, {\it Multigrid}, Academic Press, New York, 2001, .
[56] P. Vaněk, {\it Acceleration of convergence of a two-level algorithm by smoothing transfer operator}, Appl. Math., 37 (1992), pp. 265-274, . · Zbl 0773.65021
[57] P. Vaněk, J. Mandel, and M. Brezina, {\it Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems}, Computing, 56 (1996), pp. 179-196, . · Zbl 0851.65087
[58] P. S. Vassilevski, {\it Multilevel Block Factorization Preconditioners}, Springer, New York, 2008, . · Zbl 1170.65001
[59] J. Xu and L. Zikatanov, {\it Algebraic multigrid methods}, Acta Numer., 26 (2017), 591�721, . · Zbl 1378.65182
[60] U. M. Yang, {\it Parallel Algebraic Multigrid Methods–High Performance Preconditioners}, Springer, Berlin, 2006, pp. 209-236, . · Zbl 1097.65125
[61] S. Zampini, {\it PCBDDC: A class of robust dual-primal methods in PETSc}, SIAM J. Sci. Comput., 38 (2016), pp. S282-S306, . · Zbl 1352.65632
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.