The single-grid multilevel method  and its applications

Jinchao Xu

doi:10.3934/ipi.2013.7.987

Article Contents

2013, Volume 7, Issue 3: 987-1005. Doi: 10.3934/ipi.2013.7.987

This issue Previous Article Energy conserving local discontinuous Galerkin methods for wave propagation problems Next Article General convergent expectation maximization (EM)-type algorithms for image reconstruction

The single-grid multilevel method and its applications

Jinchao Xu^1,

1.
Department of Mathematics, The Pennsylvania State Univeristy, University Park, PA 16802

Received: September 30, 2012

Revised: January 31, 2013

Published: July 2013

Abstract Related Papers Cited by

Abstract

In this paper, we propose the single-grid multilevel (SGML) method for large-scale linear systems discretized from partial differential equations. The SGML method combines the methodologies of both the geometric and the algebraic multigrid methods. It uses the underlying geometric information from the finest grid. A simple and isotropic coarsening strategy is applied to explicitly control the complexity of the hierarchical structure, and smoothers are chosen based on the property of the model problem and the underlying grid information to complement the coarsening and maintain overall efficiency. Additionally, the underlying grid is used to design an efficient parallel algorithm in order to parallelize the SGML method. We apply the SGML method on the Poisson problem and the convection diffusion problem as examples, and we present the numerical results to demonstrate the performance of the SGML method.

Keywords:

Mathematics Subject Classification: Primary: 65N22, 65N55; Secondary: 65F10.

Citation:

Related Papers

Cited by

References

[1]	D. N. Arnold, R. S. Falk and R. Winther, Multigrid in H(div) and H(curl), Numer. Math., 85 (2000), 197-218.doi: 10.1007/PL00005386.
[2]	R. Blaheta, A multilevel method with correction by aggregation for solving discrete elliptic problems, Apl. Mat., 31 (1986), 365-378.
[3]	D. Braess, Towards algebraic multigrid for elliptic problems of second order, Computing, 55 (1995), 379-393.doi: 10.1007/BF02238488.
[4]	J. H. Bramble, "Multigrid Methods," Pitman Research Notes in Mathematical Sciences, 294, Longman Scientific & Technical, Essex, England, 1993.
[5]	A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp., 31 (1977), 333-390.doi: 10.1090/S0025-5718-1977-0431719-X.
[6]	A. Brandt, "Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics," GMD-Studien [GMD Studies], 85, Gesellschaft für Mathematik und Datenverarbeitung mbH, St. Augustin, 1984.
[7]	A. Brandt, General highly accurate algebraic coarsening, Elect. Trans. Numer. Anal., 10 (2000), 1-20.
[8]	A. Brandt, J. Brannick, K. Kahl and I. Livshits, Bootstrap AMG, SIAM J. Sci. Comput., 33 (2011), 612-632.doi: 10.1137/090752973.
[9]	A. Brandt, S. McCormick and J. Ruge, Algebraic multigrid (AMG) for sparse matrix equations, In "Sparsity and its Applications" (Loughborough, 1983), Cambridge Univ. Press, Cambridge, (1985), 257-284.
[10]	A. Brandt, S. F. McCormick and J. W. Ruge, Algebraic multigrid (AMG) for sparse matrix equations, in "Sparsity and its Applications" (ed. D. J. Evans), Cambridge University Press, Cambridge, 1984.
[11]	J. Brannick, Y. Chen, J. Krauss and L. Zikatanov, An algebraic multigrid method based on matching in graphs, in "Domain Decomposition Methods in Science and Engineering XX," Lecture Notes in Computational Science and Engineering, 91, Springer, (2013), 143-150.doi: 10.1007/978-3-642-35275-1_15.
[12]	J. Brannick, Y. Chen and L. Zikatanov, An algebraic multilevel method for anisotropic elliptic equations based on graph partitioning, Numer. Linear Algebra Appl., 19 (2012), 279-295.doi: 10.1002/nla.1804.
[13]	J. Brannick and L. Zikatanov, Algebraic multigrid methods based on compatible relaxation and energy minimization, in "Domain Decomposition Methods in Science and Engineering XVI," Lect. Notes Comput. Sci. Eng., 55, Springer, Berlin, (2007), 15-26.doi: 10.1007/978-3-540-34469-8_2.
[14]	M. Brezina, A. Cleary, R. Falgout, V. Henson, J. Jones, T. Manteuffel, S. McCormick and J. Ruge, Algebraic multigrid based on element interpolation (amge), SIAM Journal on Scientific Computing, 22 (2001), 1570-1592.doi: 10.1137/S1064827598344303.
[15]	M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick and J. Ruge, Adaptive smoothed aggregation $(\alpha SA)$ multigrid, SIAM Rev., 47 (2005), 317-346.doi: 10.1137/050626272.
[16]	W. L. Briggs, V. E. Henson and S. F. McCormick, "A Multigrid Tutorial," Second edition, SIAM, Philadelphia, PA, 2000.doi: 10.1137/1.9780898719505.
[17]	V. E. Bulgakov, Multi-level iterative technique and aggregation concept with semi-analytical preconditioning for solving boundary-value problems, Communications in Numerical Methods in Engineering, 9 (1993), 649-657.doi: 10.1002/cnm.1640090804.
[18]	T. Chartier, R. Falgout, V. E. Henson, J. E. Jones, T. A. Manteuffel, S. F. McCormick, J. W. Ruge and P. S. Vassilevski, Spectral element agglomerate AMGe, in "Domain Decomposition Methods in Science and Engineering XVI," Lect. Notes Comput. Sci. Eng., 55, Springer, Berlin, (2007), 513-521.doi: 10.1007/978-3-540-34469-8_64.
[19]	T. Chartier, R. D. Falgout, V. E. Henson, J. Jones, T. Manteuffel, S. McCormick, J. Ruge and P. S. Vassilevski, Spectral AMGe ($\rho$ AMGe), SIAM J. Sci. Comput., 25 (2003), 1-26.doi: 10.1137/S106482750139892X.
[20]	R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, The Computer Journal, 7 (1964), 149-154.doi: 10.1093/comjnl/7.2.149.
[21]	M. Garland and N. Bell, CUSP: Generic parallel algorithms for sparse matrix and graph computations, 2010.
[22]	L. Grasedyck, J. Xu and L. Wang, Algebraic multigrid methods based on auxiliary grids, preprint, 2013.
[23]	W. Hackbusch, "Multigrid Methods and Applications," Computational Mathematics, 4, Springer-Verlag, Berlin, 1985.
[24]	V. E. Henson and P. S. Vassilevski, Element-free AMGe: General algorithms for computing interpolation weights in AMG, Copper Mountain Conference (2000), SIAM J. Sci. Comput., 23 (2001), 629-650 (electronic).doi: 10.1137/S1064827500372997.
[25]	R. Hiptmair, Multigrid method for Maxwell's equations, SIAM J. Numer. Anal., 36 (1999), 204-225.doi: 10.1137/S0036142997326203.
[26]	X. Hu, P. S. Vasilevski and J. Xu, Comparative convergence analysis of nonlinear AMLI-cycle multigrid, Submitted to SIAM Journal on Numerical Analysis., 51 (2013), 1349-1369.doi: 10.1137/110850049.
[27]	J. E. Jones and P. S. Vassilevski, AMGe based on element agglomeration, SIAM J. Sci. Comput., 23 (2001), 109-133 (electronic).doi: 10.1137/S1064827599361047.
[28]	H. Kim, J. Xu and L. Zikatanov, A multigrid method based on graph matching for convection-diffusion equations, Numer. Linear Algebra Appl., 10 (2003), 181-195.doi: 10.1002/nla.317.
[29]	H. Kim, J. Xu and L. Zikatanov, Uniformly convergent multigrid methods for convection-diffusion problems without any constraint on coarse grids, Adv. Comput. Math., 20 (2004), 385-399.doi: 10.1023/A:1027378015262.
[30]	J. K. Kraus, An algebraic preconditioning method for $M$-matrices: Linear versus non-linear multilevel iteration, Numer. Linear Algebra Appl., 9 (2002), 599-618.doi: 10.1002/nla.281.
[31]	I. Lashuk and P. S. Vassilevski, On some versions of the element agglomeration AMGe method, Numer. Linear Algebra Appl., 15 (2008), 595-620.doi: 10.1002/nla.585.
[32]	O. Livne and A. Brandt, Lean algebraic multigrid (lamg): Fast graph laplacian linear solver, SIAM J. Sci. Comput., 34 (2012), 499-522.doi: 10.1137/110843563.
[33]	J. Mandel, M. Brezina and P. Vaněk, Energy optimization of algebraic multigrid bases, Computing, 62 (1999), 205-228.doi: 10.1007/s006070050022.
[34]	Y. Notay, An aggregation-based algebraic multigrid method, Electronic Transactions on Numerical Analysis, 37 (2010), 123-146.
[35]	Y. Notay and A. Napov, An aggregation-based algebraic multigrid method, Electronic Transactions on Numerical Analysis, 37 (2010), 123-146.
[36]	Y. Notay and P. S. Vassilevski, Recursive Krylov-based multigrid cycles, Numer. Linear Algebra Appl., 15 (2008), 473-487.doi: 10.1002/nla.542.
[37]	J. W. Ruge and K. Stüben, Algebraic multigrid, in "Multigrid Methods" (ed. S. F. McCormick), Frontiers in Applied Mathematics, 3, SIAM, Philadelphia, Pennsylvania, (1987), 73-130.
[38]	Y. Saad, A flexible inner-outer preconditioned gmres algorithm, SIAM Journal on Scientific Computing, 14 (1993), 461-469.doi: 10.1137/0914028.
[39]	K. Stüben, An introduction to algebraic multigrid, in "Multigrid" (eds. U. Trottenberg, C. Oosterlee and A. Schüller), Academic Press, San Diego, CA, (2001), 413-528.
[40]	U. Trottenberg, C. Oosterlee and A. Schüller, "Multigrid," Academic Press, Inc., San Diego, CA, 2001.
[41]	P. Vaněk, J. Mandel and M. Brezina, Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, International GAMM-Workshop on Multi-level Methods (Meisdorf, 1994), Computing, 56 (1996), 179-196.doi: 10.1007/BF02238511.
[42]	P. S. Vassilevski, "Multilevel Block Factorization Preconditioners. Matrix-based Analysis and Algorithms for Solving Finite Element Equations," Springer, New York, 2008.
[43]	W. L. Wan, T. F. Chan and B. Smith, An energy-minimizing interpolation for robust multigrid methods, SIAM J. Sci. Comput., 21 (2000), 1632-1649 (electronic).doi: 10.1137/S1064827598334277.
[44]	F. Wang and J. Xu, A crosswind block iterative method for convection-dominated problems, SIAM J. Sci. Comput., 21 (1999), 620-645 (electronic).doi: 10.1137/S106482759631192X.
[45]	L. Wang, X. Hu, J. Cohen and J. Xu, A parallel auxiliary grid AMG method for GPU, SIAM J. Sci. Comput., 35, C263-C283.
[46]	P. Wesseling, "An Introduction to Multigrid Methods," Reprint of the 1992 edition, Cos Cob, CT, 2001. Available from: http://www.MGNet.org.
[47]	J. Xu, Iterative methods by SPD and small subspace solvers for nonsymmetric or indefinite problems, in "Fifth International Symposium on Domain Decomposition Methods for Partial Differential Equations" (Norfolk, VA, 1991), SIAM, Philadelphia, PA, (1992), 106-118.
[48]	J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56 (1996), 215-235.doi: 10.1007/BF02238513.
[49]	J. Xu, Fast Poisson-based solvers for linear and nonlinear PDEs, in "Proceedings of the International Congress of Mathematicians. Volume IV," Hindustan Book Agency, New Delhi, (2010), 2886-2912.
[50]	J. Xu and L. Zikatanov, A monotone finite element scheme for convection-diffusion equations, Math. Comp., 68 (1999), 1429-1446.doi: 10.1090/S0025-5718-99-01148-5.
[51]	J. Xu and L. Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc., 15 (2002), 573-597.doi: 10.1090/S0894-0347-02-00398-3.
[52]	J. Xu and L. Zikatanov, On an energy minimizing basis for algebraic multigrid methods, Comput. Vis. Sci., 7 (2004), 121-127.doi: 10.1007/s00791-004-0147-y.
[53]	L. Zikatanov, Two-sided bounds on the convergence rate of two-level methods, Numer. Linear Alg. Appl., 15 (2008), 439-454.doi: 10.1002/nla.556.