Accurate inverses for computing eigenvalues of extremely ill-conditioned matrices and differential operators

Ye, Qiang

doi:10.1090/mcom/3223

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