Accurate inverses for computing eigenvalues of extremely ill-conditioned matrices and differential operators
HTML articles powered by AMS MathViewer
- by Qiang Ye PDF
- Math. Comp. 87 (2018), 237-259 Request permission
Abstract:
This paper is concerned with computations of a few smallest eigenvalues (in absolute value) of a large extremely ill-conditioned matrix. It is shown that a few smallest eigenvalues can be accurately computed for a diagonally dominant matrix or a product of diagonally dominant matrices by combining a standard iterative method with the accurate inversion algorithms that have been developed for such matrices. Applications to the finite difference discretization of differential operators are discussed. In particular, a new discretization is derived for the 1-dimensional biharmonic operator that can be written as a product of diagonally dominant matrices. Numerical examples are presented to demonstrate the accuracy achieved by the new algorithms.References
- Attahiru Sule Alfa, Jungong Xue, and Qiang Ye, Entrywise perturbation theory for diagonally dominant $M$-matrices with applications, Numer. Math. 90 (2002), no. 3, 401–414. MR 1884223, DOI 10.1007/s002110100289
- Attahiru Sule Alfa, Jungong Xue, and Qiang Ye, Accurate computation of the smallest eigenvalue of a diagonally dominant $M$-matrix, Math. Comp. 71 (2002), no. 237, 217–236. MR 1862996, DOI 10.1090/S0025-5718-01-01325-4
- I. Babuška and J. Osborn, Eigenvalue problems, Handbook of numerical analysis, Vol. II, Handb. Numer. Anal., II, North-Holland, Amsterdam, 1991, pp. 641–787. MR 1115240
- Jesse Barlow and James Demmel, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Numer. Anal. 27 (1990), no. 3, 762–791. MR 1041262, DOI 10.1137/0727045
- Louis Bauer and Edward L. Reiss, Block five diagonal matrices and the fast numerical solution of the biharmonic equation, Math. Comp. 26 (1972), 311–326. MR 312751, DOI 10.1090/S0025-5718-1972-0312751-9
- Matania Ben-Artzi, Jean-Pierre Croisille, and Dalia Fishelov, A fast direct solver for the biharmonic problem in a rectangular grid, SIAM J. Sci. Comput. 31 (2008), no. 1, 303–333. MR 2460780, DOI 10.1137/070694168
- Petter E. Bjørstad and Bjørn Peter Tjøstheim, Efficient algorithms for solving a fourth-order equation with the spectral-Galerkin method, SIAM J. Sci. Comput. 18 (1997), no. 2, 621–632. MR 1433799, DOI 10.1137/S1064827596298233
- P. E. Bjørstad and B. P. Tjøstheim, High precision solutions of two fourth order eigenvalue problems, Computing 63 (1999), no. 2, 97–107. MR 1736662, DOI 10.1007/s006070050053
- T. Boggio, Sulle funzioni di Green d’ordine m, Rend. Circ. Mat. Palermo 20 (1905), 97-135.
- J. H. Bramble, A second order finite difference analog of the first biharmonic boundary value problem, Numer. Math. 9 (1966), 236–249. MR 205478, DOI 10.1007/BF02162087
- S. C. Brenner, P. Monk, and J. Sun, C0 interior penalty Galerkin method for biharmonic eigenvalue problems, preprint available at http://www.math.mtu.edu/˜jiguangs/.
- B. M. Brown, E. B. Davies, P. K. Jimack, and M. D. Mihajlović, A numerical investigation of the solution of a class of fourth-order eigenvalue problems, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 456 (2000), no. 1998, 1505–1521. MR 1808762, DOI 10.1098/rspa.2000.0573
- P. G. Ciarlet, Conforming and nonconforming finite element methods for solving the plate problem, Conference on the Numerical Solution of Differential Equations (Univ. of Dundee, Dundee, 1973) Lecture Notes in Math., Vol. 363, Springer, Berlin, 1974, pp. 21–31. MR 0423832
- Wei Chen, Eigenvalue approximation of the biharmonic eigenvalue problem by Ciarlet-Raviart scheme, Numer. Methods Partial Differential Equations 21 (2005), no. 3, 512–520. MR 2128593, DOI 10.1002/num.20043
- Goong Chen, Matthew P. Coleman, and Jianxin Zhou, Analysis of vibration eigenfrequencies of a thin plate by the Keller-Rubinow wave method. I. Clamped boundary conditions with rectangular or circular geometry, SIAM J. Appl. Math. 51 (1991), no. 4, 967–983. MR 1117427, DOI 10.1137/0151048
- C. V. Coffman and R. J. Duffin, On the structure of biharmonic functions satisfying the clamped plate conditions on a right angle, Adv. in Appl. Math. 1 (1980), no. 4, 373–389. MR 603137, DOI 10.1016/0196-8858(80)90018-4
- Xiaoying Dai, Jinchao Xu, and Aihui Zhou, Convergence and optimal complexity of adaptive finite element eigenvalue computations, Numer. Math. 110 (2008), no. 3, 313–355. MR 2430983, DOI 10.1007/s00211-008-0169-3
- Megan Dailey, Froilán M. Dopico, and Qiang Ye, Relative perturbation theory for diagonally dominant matrices, SIAM J. Matrix Anal. Appl. 35 (2014), no. 4, 1303–1328. MR 3272625, DOI 10.1137/130943613
- Megan Dailey, Froilán M. Dopico, and Qiang Ye, A new perturbation bound for the LDU factorization of diagonally dominant matrices, SIAM J. Matrix Anal. Appl. 35 (2014), no. 3, 904–930. MR 3228468, DOI 10.1137/13093858X
- James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
- James Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562–580. MR 1742810, DOI 10.1137/S0895479897328716
- James Demmel, Ming Gu, Stanley Eisenstat, Ivan Slapničar, Krešimir Veselić, and Zlatko Drmač, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299 (1999), no. 1-3, 21–80. MR 1723709, DOI 10.1016/S0024-3795(99)00134-2
- James Demmel and W. Kahan, Accurate singular values of bidiagonal matrices, SIAM J. Sci. Statist. Comput. 11 (1990), no. 5, 873–912. MR 1057146, DOI 10.1137/0911052
- James Demmel and Plamen Koev, Accurate SVDs of weakly diagonally dominant $M$-matrices, Numer. Math. 98 (2004), no. 1, 99–104. MR 2076055, DOI 10.1007/s00211-004-0527-8
- James Demmel and Krešimir Veselić, Jacobi’s method is more accurate than $QR$, SIAM J. Matrix Anal. Appl. 13 (1992), no. 4, 1204–1245. MR 1182723, DOI 10.1137/0613074
- Froilán M. Dopico and Plamen Koev, Accurate symmetric rank revealing and eigendecompositions of symmetric structured matrices, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 1126–1156. MR 2276557, DOI 10.1137/050633792
- Froilán M. Dopico and Plamen Koev, Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices, Numer. Math. 119 (2011), no. 2, 337–371. MR 2836090, DOI 10.1007/s00211-011-0382-3
- Froilán M. Dopico, Plamen Koev, and Juan M. Molera, Implicit standard Jacobi gives high relative accuracy, Numer. Math. 113 (2009), no. 4, 519–553. MR 2545493, DOI 10.1007/s00211-009-0240-8
- Froilán M. Dopico and Juan M. Molera, Accurate solution of structured linear systems via rank-revealing decompositions, IMA J. Numer. Anal. 32 (2012), no. 3, 1096–1116. MR 2954742, DOI 10.1093/imanum/drr023
- Z. Drmac, Computing Eigenvalues and Singular Values to High Relative Accuracy, in Handbook of Linear Algebra, 2nd Ed., CRC Press, Boca Raton, Fl. 2014.
- Louis W. Ehrlich, Solving the biharmonic equation as coupled finite difference equations, SIAM J. Numer. Anal. 8 (1971), 278–287. MR 288972, DOI 10.1137/0708029
- M. Embree, private communication.
- K. Vince Fernando and Beresford N. Parlett, Accurate singular values and differential qd algorithms, Numer. Math. 67 (1994), no. 2, 191–229. MR 1262781, DOI 10.1007/s002110050024
- D. Fishelov, M. Ben-Artzi, and J.-P. Croisille, Recent advances in the study of a fourth-order compact scheme for the one-dimensional biharmonic equation, J. Sci. Comput. 53 (2012), no. 1, 55–79. MR 2965305, DOI 10.1007/s10915-012-9611-x
- Winfried K. Grassmann, Michael I. Taksar, and Daniel P. Heyman, Regenerative analysis and steady state distributions for Markov chains, Oper. Res. 33 (1985), no. 5, 1107–1116. MR 806921, DOI 10.1287/opre.33.5.1107
- P. R. Garabedian, A partial differential equation arising in conformal mapping, Pacific J. Math. 1 (1951), 485–524. MR 46440
- Hans-Christoph Grunau and Frédéric Robert, Positivity and almost positivity of biharmonic Green’s functions under Dirichlet boundary conditions, Arch. Ration. Mech. Anal. 195 (2010), no. 3, 865–898. MR 2591975, DOI 10.1007/s00205-009-0230-0
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
- Wolfgang Hackbusch and Götz Hofmann, Results of the eigenvalue problem for the plate equation, Z. Angew. Math. Phys. 31 (1980), no. 6, 730–739 (English, with German summary). MR 619010, DOI 10.1007/BF01594119
- Ying Jiang, Bo Wang, and Yuesheng Xu, A fast Fourier-Galerkin method solving a boundary integral equation for the biharmonic equation, SIAM J. Numer. Anal. 52 (2014), no. 5, 2530–2554. MR 3270029, DOI 10.1137/140955744
- Herbert B. Keller, On the accuracy of finite difference approximations to the eigenvalues of differential and integral operators, Numer. Math. 7 (1965), 412–419. MR 189279, DOI 10.1007/BF01436255
- James R. Kuttler, A finite-difference approximation for the eigenvalues of the clamped plate, Numer. Math. 17 (1971), 230–238. MR 292290, DOI 10.1007/BF01436379
- Ren-Cang Li, Relative perturbation theory. I. Eigenvalue and singular value variations, SIAM J. Matrix Anal. Appl. 19 (1998), no. 4, 956–982. MR 1632560, DOI 10.1137/S089547989629849X
- Andrew Ronald Mitchell and D. F. Griffiths, The finite difference method in partial differential equations, A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1980. MR 562915
- Volker Mehrmann and Agnieszka Miedlar, Adaptive computation of smallest eigenvalues of self-adjoint elliptic partial differential equations, Numer. Linear Algebra Appl. 18 (2011), no. 3, 387–409. MR 2760060, DOI 10.1002/nla.733
- Beresford N. Parlett, The symmetric eigenvalue problem, Classics in Applied Mathematics, vol. 20, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. MR 1490034, DOI 10.1137/1.9781611971163
- J. M. Peña, LDU decompositions with L and U well conditioned, Electron. Trans. Numer. Anal. 18 (2004), 198–208. MR 2150769
- Rolf Rannacher, Nonconforming finite element methods for eigenvalue problems in linear plate theory, Numer. Math. 33 (1979), no. 1, 23–42. MR 545740, DOI 10.1007/BF01396493
- Richard S. Varga, Matrix iterative analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713, DOI 10.1007/978-3-642-05156-2
- Hans F. Weinberger, Variational methods for eigenvalue approximation, Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 15, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1974. Based on a series of lectures presented at the NSF-CBMS Regional Conference on Approximation of Eigenvalues of Differential Operators, Vanderbilt University, Nashville, Tenn., June 26–30, 1972. MR 0400004
- Qiang Ye, Computing singular values of diagonally dominant matrices to high relative accuracy, Math. Comp. 77 (2008), no. 264, 2195–2230. MR 2429881, DOI 10.1090/S0025-5718-08-02112-1
- Qiang Ye, Relative perturbation bounds for eigenvalues of symmetric positive definite diagonally dominant matrices, SIAM J. Matrix Anal. Appl. 31 (2009), no. 1, 11–17. MR 2487046, DOI 10.1137/060676349
- Shuo Zhang and Jinchao Xu, Optimal solvers for fourth-order PDEs discretized on unstructured grids, SIAM J. Numer. Anal. 52 (2014), no. 1, 282–307. MR 3162408, DOI 10.1137/120878148
Additional Information
- Qiang Ye
- Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506
- MR Author ID: 237891
- Email: qye3@uky.edu
- Received by editor(s): December 28, 2015
- Received by editor(s) in revised form: June 14, 2016, and August 24, 2016
- Published electronically: May 11, 2017
- Additional Notes: This research was supported in part by NSF Grants DMS-1317424, DMS-1318633 and DMS-1620082
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 237-259
- MSC (2010): Primary 65F15, 65F35, 65N06, 65N25
- DOI: https://doi.org/10.1090/mcom/3223
- MathSciNet review: 3716195