×

Fourier analysis of periodic stencils in multigrid methods. (English) Zbl 1402.65175

The authors study how to adapt multigrid methods to a given problem using local Fourier analysis. A standard procedure is to freeze the coefficients of the PDE in suitable points and, consequently, to deal with operators having a constant stencil. This approach may be reasonable for PDEs with smooth coefficients. The authors consider a more general approach using operators with periodic stencils. With the aid of such operators, for example, also PDEs with jumping coefficient can be analyzed. In the more general setting of periodic stencils the Fourier representation is block diagonal. It allows to compute the spectral radius and norm of the operator. And it can be seen how the operator acts on smooth/oscillatory input. The resulting information is useful to construct efficient smoothers and coarse grid corrections since frequency damping and emission becomes visible. As an application, a PDE in divergence form with a jumping coefficient in a two-dimensional domain is considered. As smoothing methods the damped Jacobi, the block Jacobi and the red-black block Jacobi method are compared. Also, the impact of aggressive coarsening (i.e., the next coarser grid uses more than double the step-size, as is usual) is studied for a two-grid method applied to the five-point finite difference discretization of the Poisson equation.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N06 Finite difference methods for boundary value problems involving PDEs

Software:

LFA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Alcouffe, A. Brandt, J. Dendy, Jr., and J. Painter, The multi-grid method for the diffusion equation with strongly discontinuous coefficients, SIAM J. Sci. Statist. Comput., 2 (1981), pp. 430–454. · Zbl 0474.76082
[2] H. Bin Zubair, C. W. Oosterlee, and R. Wienands, Multigrid for high-dimensional elliptic partial differential equations on non-equidistant grids, SIAM J. Sci. Comput., 29 (2007), pp. 1613–1636. · Zbl 1145.65109
[3] A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp., 31 (1977), pp. 333–390. · Zbl 0373.65054
[4] A. Brandt, Rigorous quantitative analysis of multigrid, I: Constant coefficients two-level cycle with \(L_2\)-norm, SIAM J. Numer. Anal., 31 (1994), pp. 1695–1730. · Zbl 0817.65126
[5] A. Brandt and O. E. Livne, Multigrid Techniques. 1984 Guide with Applications to Fluid Dynamics, Classics in Appl. Math. 67, SIAM, Philadelphia, 2011. · Zbl 1227.65121
[6] J. Brannick, X. Hu, C. Rodrigo, and L. Zikatanov, Local Fourier analysis of multigrid methods with polynomial smoothers and aggressive coarsening, Numer. Math. Theory Methods Appl., 8 (2015), pp. 1–21. · Zbl 1340.65290
[7] W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia, 2000.
[8] J. E. Dendy, Jr., Black box multigrid, J. Comput. Phys., 48 (1982), pp. 366–386. · Zbl 0495.65047
[9] S. Friedhoff and S. MacLachlan, A generalized predictive analysis tool for multigrid methods, Numer. Linear Algebra Appl., 22 (2015), pp. 618–647. · Zbl 1349.65427
[10] F. J. Gaspar, J. L. Gracia, and F. J. Lisbona, Fourier analysis for multigrid methods on triangular grids, SIAM J. Sci. Comput., 31 (2009), pp. 2081–2102. · Zbl 1190.65181
[11] F. J. Gaspar, J. L. Gracia, F. J. Lisbona, and C. Rodrigo, On geometric multigrid methods for triangular grids using three-coarsening strategy, Appl. Numer. Math., 59 (2009), pp. 1693–1708. · Zbl 1171.65448
[12] G. H. Golub and C. F. Van Loan, Matrix Computations, 2nd ed., Johns Hopkins University Press, Baltimore, MD, 1989. · Zbl 0733.65016
[13] W. Hackbusch, Multi-Grid Methods and Applications, Springer-Verlag, Berlin, 1985. · Zbl 0595.65106
[14] P. W. Hemker, W. Hoffmann, and M. H. van Raalte, Two-level Fourier analysis of a multigrid approach for discontinuous Galerkin discretization, SIAM J. Sci. Comput., 25 (2003), pp. 1018–1041. · Zbl 1048.65108
[15] P. W. Hemker, W. Hoffmann, and M. H. van Raalte, Fourier two-level analysis for discontinuous Galerkin discretization with linear elements, Numer. Linear Algebra Appl., 11 (2004), pp. 473–491. · Zbl 1164.65498
[16] P. W. Hemker and M. H. van Raalte, Fourier two-level analysis for higher dimensional discontinuous Galerkin discretisation, Comput. Vis. Sci., 7 (2004), pp. 159–172. · Zbl 1071.65154
[17] A. Holderrieth, Matrix multiplication operators generating one parameter semigroups, Semigroup Forum, 42 (1991), pp. 155–166. · Zbl 0744.47033
[18] C.-C. J. Kuo and B. C. Levy, Two-color Fourier analysis of the multigrid method with red-black Gauss-Seidel smoothing, Appl. Math. Comput., 29 (1989), pp. 69–87. · Zbl 0663.65104
[19] O. E. Livne and A. Brandt, Local mode analysis of multicolor and composite relaxation schemes, Comput. Math. Appl., 47 (2004), pp. 301–317. · Zbl 1054.65127
[20] S. P. MacLachlan and C. W. Oosterlee, Local Fourier analysis for multigrid with overlapping smoothers applied to systems of PDEs, Numer. Linear Algebra Appl., 18 (2011), pp. 751–774. · Zbl 1265.65256
[21] W. Rudin, Functional Analysis, McGraw-Hill Series in Higher Mathematics, McGraw-Hill, New York, 1973.
[22] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[23] E. Strohmaier, J. Dongarra, H. Simon, and M. Meuer, TOP500 November 2015, .
[24] K. Stüben and U. Trottenberg, Multigrid methods: Fundamental algorithms, model problem analysis and applications, in Multigrid Methods (Cologne, 1981), Lecture Notes in Math. 960, Springer-Verlag, Berlin, 1982, pp. 1–176.
[25] U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, New York, 2001.
[26] R. Wienands and W. Joppich, Practical Fourier Analysis for Multigrid Methods, Chapman & Hall/CRC Press, Boca Raton, FL, 2005. · Zbl 1062.65133
[27] R. Wienands and C. W. Oosterlee, On three-grid Fourier analysis for multigrid, SIAM J. Sci. Comput., 23 (2001), pp. 651–671. · Zbl 0992.65137
[28] J. Xu, The method of subspace corrections, J. Comput. Appl. Math., 128 (2001), pp. 335–362. · Zbl 0983.65133
[29] I. Yavneh, Multigrid smoothing factors for red-black Gauss–Seidel relaxation applied to a class of elliptic operators, SIAM J. Numer. Anal., 32 (1995), pp. 1126–1138. · Zbl 0834.65114
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.