Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T14:03:25.423Z Has data issue: false hasContentIssue false
  • English
  • Français

Local Fourier Analysis of Multigrid Methods with Polynomial Smoothers and Aggressive Coarsening

Published online by Cambridge University Press:  03 March 2015

James Brannick ,
Xiaozhe Hu ,
Carmen Rodrigo  and
Ludmil Zikatanov
James Brannick
Affiliation:
Department of Mathematics, The Pennsylvania State University, University Park, PA 16802, USA
Xiaozhe Hu*
Affiliation:
Department of Mathematics, Tufts University, 503 Boston Ave., Medford, MA 02155, USA
Carmen Rodrigo
Affiliation:
Department of Applied Mathematics, University of Zaragoza, C/ Maria de Luna 3, 50018, Zaragoza, Spain
Ludmil Zikatanov
Affiliation:
Department of Mathematics, The Pennsylvania State University, University Park, PA 16802, USA Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Acad. G. Bonchev Str., Bl. 8, 1113 Sofia, Bulgaria
*
*Email addresses: [email protected] (J. Brannick), [email protected] (X. Hu), [email protected] (C. Rodrigo), [email protected] (L. Zikatanov)
Get access

Abstract

We focus on the study of multigrid methods with aggressive coarsening and polynomial smoothers for the solution of the linear systems corresponding to finite difference/element discretizations of the Laplace equation. Using local Fourier analysis we determine automatically the optimal values for the parameters involved in defining the polynomial smoothers and achieve fast convergence of cycles with aggressive coarsening. We also present numerical tests supporting the theoretical results and the heuristic ideas. The methods we introduce are highly parallelizable and efficient multigrid algorithms on structured and semi-structured grids in two and three spatial dimensions.

Keywords

65F1065N2265N55Multigridlocal Fourier analysispolynomial smoothersaggressive coarsening
Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 8 , Issue 1 , February 2015 , pp. 1 - 21
Copyright
Copyright © Global-Science Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Mark, Adams, Brezina, MarianHu, Jonathan and Tuminaro, RayParallel multigrid smoothing: polynomial versus Gauss-Seidel. J. Comp. Phys, 188:593–610, 2003.Google Scholar
[2]Owe, Axelsson and Vassilevski, Panayot S.Algebraic multilevel preconditioning methods. I. Numer. Math., 56(2–3):157–177, 1989.Google Scholar
[3]Allison, H. Baker, Falgout, Robert D.Kolev, Tzanio V. and Yang, Ulrike M.Multigrid smoothers for ultraparallel computing. SIAM Journal on Scientific Computing, 33(5):2864–2887, 2011.Google Scholar
[4]Allison, H. Baker, Falgout, Robert D.Kolev, Tzanio V. and Yang, Ulrike M.Multigrid smoothers for ultraparallel computing: Additional theory and discussion. Technical report, Technical report LLNL-TR-489114, Lawrence Livermore National Laboratory, 2011.Google Scholar
[5]Achi, Brandt. Multi-level adaptive solutions to boundary-value problems. Math. Comp., 31(138):333–390, 1977.Google Scholar
[6]Marian, Brezina, Heberton, CarolineMandel, Jan and Vaněk, PetrAn iterative method with convergence rate chosen a priori. Technical report, Technical report: Center for Computational Mathematics, University of Colorado at Denver, 1999.Google Scholar
[7]Marian, Brezina, Vaněk, Petr and Vassilevski, Panayot S.An improved convergence analysis of smoothed aggregation algebraic multigrid. Numer. Linear Algebra Appl., 19(3):441–469, 2012.Google Scholar
[8]Marian, Brezina and Vassilevski, Panayot S.Smoothed aggregation spectral element agglomeration AMG: SA-ρAMGe. In Large-scale scientific computing, volume 7116 of Lecture Notes in Comput. Sci., pages 3–15. Springer, Heidelberg, 2012.Google Scholar
[9]Francisco, J. Gaspar, Gracia, José L. and Lisbona, Francisco J.Fourier analysis for multigrid methods on triangular grids. SIAM J. Sci. Comput., 31(3):2081–2102, 2009.Google Scholar
[10]Francisco, J. Gaspar, Gracia, José L.Lisbona, Francisco J. and Rodrigo, CarmenOn geometric multigrid methods for triangular grids using three-coarsening strategy. Appl. Numer. Math., 59(7):1693–1708, 2009.Google Scholar
[11]Tzanio, V. Kolev and Vassilevski, Panayot S.Parallel auxiliary space AMG for H (curl) problems. J. Comput. Math., 27(5):604–623, 2009.Google Scholar
[12]Johannes, K. Kraus, Vassilevski, Panayot S. and Zikatanov, Ludmil T.Polynomial of best uniform approximation to 1/x and smoothing in two-level methods. Computational Methods in Applied Mathematics, 12(4):448–468, 2012.Google Scholar
[13]Carmen, Rodrigo, Gaspar, Francisco J. and Lisbona, Francisco J.Geometric multigrid Methods on Triangular Grids: Application to semi-structured meshes. Lambert Academic Publishing, Saarbrüken, 2012.Google Scholar
[14]Klaus, Stüben and Trottenberg, UlrichMultigrid methods: fundamental algorithms, model problem analysis and applications. In Multigrid methods (Cologne, 1981), volume 960 of Lecture Notes in Math., pages 1–1761. Springer, Berlin, 1982.Google Scholar
[15]Ulrich, Trottenberg, Oosterlee, Cornelis W. and Schüller, AntonMultigrid. Academic Press Inc., San Diego, CA, 2001. With contributions by Brandt, A.Oswald, P. and Stüben, K.Google Scholar
[16]Petr, Vanek, Mandel, Jan and Brezina, MarianAlgebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing, 56(3):179–196, 1996.Google Scholar
[17]Petr, Vaněk and Brezina, MarianNearly optimal convergence result for multigrid with aggressive coarsening and polynomial smoothing. Applications ofMathematics, 58(4):369–388, 2013.Google Scholar
[18]Panayot, S. Vassilevski. Multilevel block factorization preconditioners. Springer, New York, 2008. Matrix-based analysis and algorithms for solving finite element equations.Google Scholar
[19]Roman, Wienands and Joppich, WolfgangPractical Fourier analysis for multigrid methods, volume 4 of Numerical Insights. Chapman & Hall/CRC, Boca Raton, FL, 2005. With 1 CD-ROM (Windows and UNIX).Google Scholar
[20]Hisham, Bin Zubair, Oosterlee, Cornelis W. and Wienands, RomanMultigrid for high-dimensional elliptic partial differential equations on non-equidistant grids. SIAM J. Sci. Comput., 29(4):1613–1636 (electronic), 2007.Google Scholar