×

Laplacian preconditioning of elliptic PDEs: localization of the eigenvalues of the discretized operator. (English) Zbl 1495.65212

Summary: In [IMA J. Numer. Anal. 29, No. 1, 24–42 (2009; Zbl 1167.65066)], B. F. Nielsen, A. Tveito, and W. Hackbusch study the operator generated by using the inverse of the Laplacian as the preconditioner for second order elliptic PDEs \(-\nabla\cdot(k(x)\nabla u)=f\). They prove that the range of \(k(x)\) is contained in the spectrum of the preconditioned operator, provided that \(k(x)\) is continuous. Their rigorous analysis only addresses mappings defined on infinite dimensional spaces, but the numerical experiments in the paper suggest that a similar property holds in the discrete case. Motivated by this investigation, we analyze the eigenvalues of the matrix \(\mathbf{L}^{\boldsymbol{-1}}\mathbf{A}\), where \(\mathbf{L}\) and \(\mathbf{A}\) are the stiffness matrices associated with the Laplace operator and second order elliptic operators with a scalar coefficient function, respectively. Using only technical assumptions on \(k(x)\), we prove the existence of a one-to-one pairing between the eigenvalues of \(\mathbf{L}^{\boldsymbol{-1}}\mathbf{A}\) and the intervals determined by the images under \(k(x)\) of the supports of the finite element nodal basis functions. As a consequence, we can show that the nodal values of \(k(x)\) yield accurate approximations of the eigenvalues of \(\mathbf{L}^{\boldsymbol{-1}}\mathbf{A}\). Our theoretical results, including their relevance for understanding how the convergence of the conjugate gradient method may depend on the whole spectrum of the preconditioned matrix, are illuminated by several numerical experiments.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N25 Numerical methods for eigenvalue problems for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations

Citations:

Zbl 1167.65066

Software:

FEniCS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, UK, 1994, https://doi.org/10.1017/cbo9780511624100. · Zbl 0795.65014
[2] O. Axelsson and G. Lindskog, On the eigenvalue distribution of a class of preconditioning methods, Numer. Math., 48 (1986), pp. 479-498, https://doi.org/10.1007/bf01389447. · Zbl 0564.65016
[3] O. Axelsson and G. Lindskog, On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 48 (1986), pp. 499-523, https://doi.org/10.1007/bf01389448. · Zbl 0564.65017
[4] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Elsevier, New York, 1976. · Zbl 1226.05083
[5] P. G. Ciarlet, The Finite Element Method for Elliptic Problems, Classics Appl. Math. 40, SIAM, Philadelphia, 2002, https://doi.org/10.1137/1.9780898719208, reprint of the 1978 original [North-Holland, Amsterdam; MR0520174 (58 25001)]. · Zbl 0999.65129
[6] J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal., 4 (1967), pp. 10-26, https://doi.org/10.1137/0704002. · Zbl 0154.40302
[7] A. L. Dulmage and N. S. Mendelsohn, Coverings of bipartite graphs, Canad. J. Math., 10 (1958), pp. 517-534, https://doi.org/10.4153/CJM-1958-052-0. · Zbl 0091.37404
[8] M. Engeli, T. Ginsburg, H. Rutishauser, and E. Stiefel, Refined Iterative Methods for Computation of the Solution and the Eigenvalues of Self-Adjoint Boundary Value Problems, Mitt. Inst. Angew. Math. Zürich 8, Birkhäuser, Basel, 1959, https://doi.org/10.1007/978-3-0348-7224-9. · Zbl 0089.12103
[9] V. Faber, T. A. Manteuffel, and S. V. Parter, On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations, Adv. in Appl. Math., 11 (1990), pp. 109-163, https://doi.org/10.1016/0196-8858(90)90007-L. · Zbl 0718.65043
[10] T. Gergelits and Z. Strakoš, Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations, Numer. Algorithms, 65 (2014), pp. 759-782, https://doi.org/10.1007/s11075-013-9713-z. · Zbl 1298.65054
[11] A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7-63, https://doi.org/10.1016/0024-3795(89)90285-1. · Zbl 0662.65032
[12] A. Greenbaum, V. Pták, and Z. Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 465-469, https://doi.org/10.1137/s0895479894275030. · Zbl 0857.65029
[13] A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121-137, https://doi.org/10.1137/0613011. · Zbl 0755.65037
[14] A. Greenbaum and Z. Strakoš, Matrices that generate the same Krylov residual spaces, in Recent Advances in Iterative Methods, IMA Vol. Math. Appl. 60, Springer, New York, 1994, pp. 95-118, https://doi.org/10.1007/978-1-4613-9353-5_7. · Zbl 0803.65029
[15] A. Günnel, R. Herzog, and E. Sachs, A note on preconditioners and scalar products in Krylov subspace methods for self-adjoint problems in Hilbert space, Electron. Trans. Numer. Anal., 41 (2014), pp. 13-20. · Zbl 1295.65062
[16] W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag, New York, 1994, https://doi.org/10.1007/978-3-319-28483-5. · Zbl 0789.65017
[17] P. Hall, On representatives of subsets, J. Lond. Math. Soc., s1-10 (1935), pp. 26-30, https://doi.org/10.1112/jlms/s1-10.37.26. · JFM 61.0067.01
[18] R. Herzog and E. Sachs, Superlinear convergence of Krylov subspace methods for self-adjoint problems in Hilbert space, SIAM J. Numer. Anal., 53 (2015), pp. 1304-1324, https://doi.org/10.1137/140973050. · Zbl 1312.65044
[19] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49 (1952), pp. 409-436, https://doi.org/10.6028/jres.049.044. · Zbl 0048.09901
[20] R. Hiptmair, Operator preconditioning, Comput. Math. Appl., 52 (2006), pp. 699-706, https://doi.org/10.1016/j.camwa.2006.10.008. · Zbl 1125.65037
[21] A. Jennings, Influence of the eigenvalue spectrum on the convergence rate of the conjugate gradient method, J. Inst. Math. Appl., 20 (1977), pp. 61-72, https://doi.org/10.1093/imamat/20.1.61. · Zbl 0364.65028
[22] A. Jennings and G. M. Malik, The solution of sparse linear equations by the conjugate gradient method, Internat. J. Numer. Methods Engrg., 12 (1978), pp. 141-158, https://doi.org/10.1002/nme.1620120114. · Zbl 0367.65020
[23] C. Lanczos, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards, 49 (1952), pp. 33-53, https://doi.org/10.6028/jres.049.006.
[24] J. Liesen and Z. Strakoš, Krylov Subspace Methods: Principles and Analysis, Numer. Math. Sci. Comput., Oxford University Press, Oxford, UK, 2012, https://doi.org/10.1093/acprof:oso/9780199655410.001.0001. · Zbl 1263.65034
[25] A. Logg, K.-A. Mardal, and G. N. Wells, eds., Automated Solution of Differential Equations by the Finite Element Method, Springer, Berlin, Heidelberg, 2012, https://doi.org/10.1007/978-3-642-23099-8. · Zbl 1247.65105
[26] J. Málek and Z. Strakoš, Preconditioning and the Conjugate Gradient Method in the Context of Solving PDEs, SIAM Spotlights 1, SIAM, Philadelphia, 2015, https://doi.org/10.1137/1.9781611973846. · Zbl 1396.65002
[27] K. A. Mardal and R. Winther, Preconditioning discretizations of systems of partial differential equations, Numer. Linear Algebra Appl., 18 (2011), pp. 1-40, https://doi.org/10.1002/nla.716. · Zbl 1249.65246
[28] G. Meurant, The Lanczos and Conjugate Gradient Algorithms. From Theory to Finite Precision Computations, Software Environ. Tools 19, SIAM, Philadelphia, 2006, https://doi.org/10.1137/1.9780898718140. · Zbl 1110.65029
[29] G. Meurant and Z. Strakoš, The Lanczos and conjugate gradient algorithms in finite precision arithmetic, Acta Numer., 15 (2006), pp. 471-542, https://doi.org/10.1017/S096249290626001X. · Zbl 1113.65032
[30] P. Morin, R. H. Nochetto, and K. G. Siebert, Convergence of adaptive finite element methods, SIAM Rev., 44 (2002), pp. 631-658, https://doi.org/10.1137/S0036144502409093. · Zbl 1016.65074
[31] B. F. Nielsen and K.-A. Mardal, Analysis of the minimal residual method applied to ill posed optimality systems, SIAM J. Sci. Comput., 35 (2013), pp. A785-A814, https://doi.org/10.1137/120871547. · Zbl 1266.49038
[32] B. F. Nielsen, A. Tveito, and W. Hackbusch, Preconditioning by inverting the Laplacian: An analysis of the eigenvalues, IMA J. Numer. Anal., 29 (2009), pp. 24-42, https://doi.org/10.1093/imanum/drm018. · Zbl 1167.65066
[33] C. C. Paige, The Computation of Eigenvalues and Eigenvectors of Very Large and Sparse Matrices, Ph.D. thesis, London University, London, England, 1971.
[34] C. C. Paige, Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl., 34 (1980), pp. 235-258, https://doi.org/10.1016/0024-3795(80)90167-6. · Zbl 0471.65017
[35] G. W. Stewart and J. G. Sun, Matrix Perturbation Theory, Comput. Sci. Sci. Comput., Academic Press, Boston, 1990. · Zbl 0706.65013
[36] Z. Strakoš, On the real convergence rate of the conjugate gradient method, Linear Algebra Appl., 154/156 (1991), pp. 535-549, https://doi.org/10.1016/0024-3795(91)90393-B. · Zbl 0732.65021
[37] A. van der Sluis and H. A. van der Vorst, The rate of convergence of conjugate gradients, Numer. Math., 48 (1986), pp. 543-560, https://doi.org/10.1007/BF01389450. · Zbl 0596.65015
[38] J. von Neumann, Mathematical Foundations of Quantum Mechanics, Princeton Landmarks Math., Princeton University Press, Princeton, NJ, 1996, https://doi.org/10.2307/j.ctt1wq8zhp, translated from the German print published in 1932 and with a preface by Robert T. Beyer, Twelfth printing, Princeton Paperbacks.
[39] Yu. V. Vorobyev, Methods of Moments in Applied Mathematics, translated from the Russian by Bernard Seckler, Gordon and Breach Science Publishers, New York, 1965, https://doi.org/10.2307/2004791. · Zbl 0196.47601
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.