Analysis of two-grid methods: The nonnormal case

Notay, Yvan

doi:10.1090/mcom/3460

Analysis of two-grid methods: The nonnormal case
HTML articles powered by AMS MathViewer

by Yvan Notay HTML | PDF

Math. Comp. 89 (2020), 807-827 Request permission

Abstract:

Core results about the algebraic analysis of two-grid methods are extended in relations bounding the field of values (or numerical range) of the iteration matrix. On this basis, bounds are obtained on its norm and numerical radius, leading to rigorous convergence estimates. Numerical illustrations show that the theoretical results deliver qualitatively good predictions, allowing one to anticipate success or failure of the two-grid method. They also indicate that the field of values and the associated numerical radius are much more reliable convergence indicators than the eigenvalue distribution and the associated spectral radius. On this basis, some discussion is developed about the role of local Fourier or local mode analysis for nonsymmetric problems.

References

C. A. Berger and J. G. Stampfli, Mapping theorems for the numerical range, Amer. J. Math. 89 (1967), 1047–1055. MR 222694, DOI 10.2307/2373416
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
Achi Brandt, Algebraic multigrid theory: the symmetric case, Appl. Math. Comput. 19 (1986), no. 1-4, 23–56. Second Copper Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR 849831, DOI 10.1016/0096-3003(86)90095-0
Achi Brandt, Rigorous quantitative analysis of multigrid. I. Constant coefficients two-level cycle with $L_2$-norm, SIAM J. Numer. Anal. 31 (1994), no. 6, 1695–1730. MR 1302681, DOI 10.1137/0731087
Achi Brandt and Oren E. Livne, Multigrid techniques—1984 guide with applications to fluid dynamics, Classics in Applied Mathematics, vol. 67, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011. Revised edition of the 1984 original [ MR0772748]. MR 3396211, DOI 10.1137/1.9781611970753
A. Brandt and I. Yavneh, On multigrid solution of high-Reynolds incompressible entering flows, J. Comput. Phys. 101 (1992), no. 1, 151–164. MR 1173343, DOI 10.1016/0021-9991(92)90049-5
M. Brezina, T. Manteuffel, S. McCormick, J. Ruge, and G. Sanders, Towards adaptive smoothed aggregation $(\alpha \textrm {SA})$ for nonsymmetric problems, SIAM J. Sci. Comput. 32 (2010), no. 1, 14–39. MR 2599765, DOI 10.1137/080727336
P. M. de Zeeuw, Matrix-dependent prolongations and restrictions in a blackbox multigrid solver, J. Comput. Appl. Math. 33 (1990), no. 1, 1–27. MR 1081238, DOI 10.1016/0377-0427(90)90252-U
J. E. Dendy Jr., Black box multigrid for nonsymmetric problems, Appl. Math. Comput. 13 (1983), no. 3-4, 261–283. MR 726637, DOI 10.1016/0096-3003(83)90016-4
V. A. Dobrev, Tz. Kolev, N. A. Petersson, and J. B. Schroder, Two-level convergence theory for multigrid reduction in time (MGRIT), SIAM J. Sci. Comput. 39 (2017), no. 5, S501–S527. MR 3716570, DOI 10.1137/16M1074096
Michael Eiermann, Fields of values and iterative methods, Linear Algebra Appl. 180 (1993), 167–197. MR 1206415, DOI 10.1016/0024-3795(93)90530-2
Stanley C. Eisenstat, Howard C. Elman, and Martin H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983), no. 2, 345–357. MR 694523, DOI 10.1137/0720023
R. D. Falgout, S. Friedhoff, Tz. V. Kolev, S. P. MacLachlan, and J. B. Schroder, Parallel time integration with multigrid, SIAM J. Sci. Comput. 36 (2014), no. 6, C635–C661. MR 3499068, DOI 10.1137/130944230
Robert D. Falgout and Panayot S. Vassilevski, On generalizing the algebraic multigrid framework, SIAM J. Numer. Anal. 42 (2004), no. 4, 1669–1693. MR 2114296, DOI 10.1137/S0036142903429742
Robert D. Falgout, Panayot S. Vassilevski, and Ludmil T. Zikatanov, On two-grid convergence estimates, Numer. Linear Algebra Appl. 12 (2005), no. 5-6, 471–494. MR 2150164, DOI 10.1002/nla.437
S. Friedhoff and S. MacLachlan, A generalized predictive analysis tool for multigrid methods, Numer. Linear Algebra Appl. 22 (2015), no. 4, 618–647. MR 3367826, DOI 10.1002/nla.1977
S. Friedhoff, S. MacLachlan, and C. Börgers, Local Fourier analysis of space-time relaxation and multigrid schemes, SIAM J. Sci. Comput. 35 (2013), no. 5, S250–S276. MR 3120772, DOI 10.1137/120881361
Moshe Goldberg and Eitan Tadmor, On the numerical radius and its applications, Linear Algebra Appl. 42 (1982), 263–284. MR 656430, DOI 10.1016/0024-3795(82)90155-0
Anne Greenbaum, Vlastimil Pták, and Zdeněk Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl. 17 (1996), no. 3, 465–469. MR 1397238, DOI 10.1137/S0895479894275030
Anne Greenbaum and Zdeněk Strakoš, Matrices that generate the same Krylov residual spaces, Recent advances in iterative methods, IMA Vol. Math. Appl., vol. 60, Springer, New York, 1994, pp. 95–118. MR 1332745, DOI 10.1007/978-1-4613-9353-5_{7}
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1991. MR 1091716, DOI 10.1017/CBO9780511840371
Jan Janssen and Stefan Vandewalle, Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case, SIAM J. Sci. Comput. 17 (1996), no. 1, 133–155. Special issue on iterative methods in numerical linear algebra (Breckenridge, CO, 1994). MR 1375271, DOI 10.1137/0917011
Andrew Lumsdaine and Deyun Wu, Spectra and pseudospectra of waveform relaxation operators, SIAM J. Sci. Comput. 18 (1997), no. 1, 286–304. Dedicated to C. William Gear on the occasion of his 60th birthday. MR 1433389, DOI 10.1137/S106482759528778X
Scott P. MacLachlan and Cornelis W. Oosterlee, Algebraic multigrid solvers for complex-valued matrices, SIAM J. Sci. Comput. 30 (2008), no. 3, 1548–1571. MR 2398878, DOI 10.1137/070687232
Artem Napov and Yvan Notay, Algebraic analysis of aggregation-based multigrid, Numer. Linear Algebra Appl. 18 (2011), no. 3, 539–564. MR 2760067, DOI 10.1002/nla.741
Yvan Notay, A robust algebraic multilevel preconditioner for non-symmetric $M$-matrices, Numer. Linear Algebra Appl. 7 (2000), no. 5, 243–267. MR 1766914, DOI 10.1002/1099-1506(200007/08)7:5<243::AID-NLA195>3.0.CO;2-Y
Yvan Notay, Algebraic analysis of two-grid methods: The nonsymmetric case, Numer. Linear Algebra Appl. 17 (2010), no. 1, 73–96. MR 2589584, DOI 10.1002/nla.649
Yvan Notay, Algebraic theory of two-grid methods, Numer. Math. Theory Methods Appl. 8 (2015), no. 2, 168–198. MR 3395388, DOI 10.4208/nmtma.2015.w04si
C. W. Oosterlee, F. J. Gaspar, T. Washio, and R. Wienands, Multigrid line smoothers for higher order upwind discretizations of convection-dominated problems, J. Comput. Phys. 139 (1998), no. 2, 274–307. MR 1614090, DOI 10.1006/jcph.1997.5854
Peter Oswald, Multilevel finite element approximation, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, Stuttgart, 1994. Theory and applications. MR 1312165, DOI 10.1007/978-3-322-91215-2
Carmen Rodrigo, Francisco J. Gaspar, and Ludmil T. Zikatanov, On the validity of the local Fourier analysis, J. Comput. Math. 37 (2019), no. 3, 340–348. MR 3866073, DOI 10.4208/jcm.1803-m2017-0294
Stephen F. McCormick (ed.), Multigrid methods, Frontiers in Applied Mathematics, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1987. MR 972752, DOI 10.1137/1.9781611971057
Yousef Saad, Further analysis of minimum residual iterations, Numer. Linear Algebra Appl. 7 (2000), no. 2, 67–93. MR 1755800, DOI 10.1002/(SICI)1099-1506(200003)7:2<67::AID-NLA186>3.3.CO;2-
Marzio Sala and Raymond S. Tuminaro, A new Petrov-Galerkin smoothed aggregation preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput. 31 (2008), no. 1, 143–166. MR 2460774, DOI 10.1137/060659545
R. Stevenson, On the validity of local mode analysis of multi-grid methods, dissertation, Utrecht University, Utrecht, the Netherlands, 1990.
Klaus Stüben and Ulrich Trottenberg, Multigrid methods: fundamental algorithms, model problem analysis and applications, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 1–176. MR 685773
Lloyd N. Trefethen and Mark Embree, Spectra and pseudospectra, Princeton University Press, Princeton, NJ, 2005. The behavior of nonnormal matrices and operators. MR 2155029
U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, Inc., San Diego, CA, 2001. With contributions by A. Brandt, P. Oswald and K. Stüben. MR 1807961
J. Van lent, Multigrid Methods for Time-Dependent Partial Differential Equations, dissertation, K.U.Leuven, Leuven, Belgium, 2006.
S. Vandewalle and G. Horton, Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods, Computing 54 (1995), no. 4, 317–330 (English, with English and German summaries). MR 1334614, DOI 10.1007/BF02238230
Roman Wienands and Wolfgang Joppich, Practical Fourier analysis for multigrid methods, Numerical Insights, vol. 4, Chapman & Hall/CRC, Boca Raton, FL, 2005. With 1 CD-ROM (Windows and UNIX). MR 2108045