Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

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


Author: Qiang Ye
Journal: Math. Comp. 87 (2018), 237-259
MSC (2010): Primary 65F15, 65F35, 65N06, 65N25
DOI: https://doi.org/10.1090/mcom/3223
Published electronically: May 11, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1007/s002110100289
  • [2] 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, https://doi.org/10.1090/S0025-5718-01-01325-4
  • [3] I. Babuška and J. Osborn, Eigenvalue Problems, Handb. Numer. Anal., II, North-Holland, Amsterdam, 1991, pp. 641-787. MR 1115240
  • [4] 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, https://doi.org/10.1137/0727045
  • [5] 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 0312751
  • [6] 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, https://doi.org/10.1137/070694168
  • [7] 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, https://doi.org/10.1137/S1064827596298233
  • [8] 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, https://doi.org/10.1007/s006070050053
  • [9] T. Boggio, Sulle funzioni di Green d'ordine m, Rend. Circ. Mat. Palermo 20 (1905), 97-135.
  • [10] J. H. Bramble, A second order finite difference analog of the first biharmonic boundary value problem, Numer. Math. 9 (1966), 236-249. MR 0205478
  • [11] 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/.
  • [12] 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, https://doi.org/10.1098/rspa.2000.0573
  • [13] 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) Springer, Berlin, 1974, pp. 21-31. Lecture Notes in Math., Vol. 363. MR 0423832
  • [14] 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, https://doi.org/10.1002/num.20043
  • [15] 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, https://doi.org/10.1137/0151048
  • [16] 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, https://doi.org/10.1016/0196-8858(80)90018-4
  • [17] 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, https://doi.org/10.1007/s00211-008-0169-3
  • [18] 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, https://doi.org/10.1137/130943613
  • [19] 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, https://doi.org/10.1137/13093858X
  • [20] James W. Demmel, Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942
  • [21] James Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562-580. MR 1742810, https://doi.org/10.1137/S0895479897328716
  • [22] 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, https://doi.org/10.1016/S0024-3795(99)00134-2
  • [23] James Demmel and W. Kahan, Accurate singular values of bidiagonal matrices, SIAM J. Sci. Statist. Comput. 11 (1990), no. 5, 873-912. MR 1057146, https://doi.org/10.1137/0911052
  • [24] James Demmel and Plamen Koev, Accurate SVDs of weakly diagonally dominant $ M$-matrices, Numer. Math. 98 (2004), no. 1, 99-104. MR 2076055, https://doi.org/10.1007/s00211-004-0527-8
  • [25] 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, https://doi.org/10.1137/0613074
  • [26] 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 (electronic). MR 2276557, https://doi.org/10.1137/050633792
  • [27] 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, https://doi.org/10.1007/s00211-011-0382-3
  • [28] 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, https://doi.org/10.1007/s00211-009-0240-8
  • [29] 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, https://doi.org/10.1093/imanum/drr023
  • [30] Z. Drmac, Computing Eigenvalues and Singular Values to High Relative Accuracy, in Handbook of Linear Algebra, 2nd Ed., CRC Press, Boca Raton, Fl. 2014.
  • [31] Louis W. Ehrlich, Solving the biharmonic equation as coupled finite difference equations., SIAM J. Numer. Anal. 8 (1971), 278-287. MR 0288972
  • [32] M. Embree, private communication.
  • [33] K. Vince Fernando and Beresford N. Parlett, Accurate singular values and differential qd algorithms, Numer. Math. 67 (1994), no. 2, 191-229. MR 1262781, https://doi.org/10.1007/s002110050024
  • [34] 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, https://doi.org/10.1007/s10915-012-9611-x
  • [35] 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, https://doi.org/10.1287/opre.33.5.1107
  • [36] P. R. Garabedian, A partial differential equation arising in conformal mapping, Pacific J. Math. 1 (1951), 485-524. MR 0046440
  • [37] 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, https://doi.org/10.1007/s00205-009-0230-0
  • [38] 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
  • [39] 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. MR 619010, https://doi.org/10.1007/BF01594119
  • [40] 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, https://doi.org/10.1137/140955744
  • [41] 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 0189279
  • [42] James R. Kuttler, A finite-difference approximation for the eigenvalues of the clamped plate, Numer. Math. 17 (1971), 230-238. MR 0292290
  • [43] 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, https://doi.org/10.1137/S089547989629849X
  • [44] Andrew Ronald Mitchell and D. F. Griffiths, The finite difference method in partial differential equations, John Wiley & Sons, Ltd., Chichester, 1980. A Wiley-Interscience Publication. MR 562915
  • [45] 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, https://doi.org/10.1002/nla.733
  • [46] 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
  • [47] J. M. Peña, LDU decompositions with L and U well conditioned, Electron. Trans. Numer. Anal. 18 (2004), 198-208 (electronic). MR 2150769
  • [48] Rolf Rannacher, Nonconforming finite element methods for eigenvalue problems in linear plate theory, Numer. Math. 33 (1979), no. 1, 23-42. MR 545740, https://doi.org/10.1007/BF01396493
  • [49] Richard S. Varga, Matrix Iterative Analysis, Second revised and expanded edition, Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000. MR 1753713
  • [50] Hans F. Weinberger, Variational methods for eigenvalue approximation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1974. MR 0400004
  • [51] Qiang Ye, Computing singular values of diagonally dominant matrices to high relative accuracy, Math. Comp. 77 (2008), no. 264, 2195-2230. MR 2429881, https://doi.org/10.1090/S0025-5718-08-02112-1
  • [52] 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, https://doi.org/10.1137/060676349
  • [53] 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, https://doi.org/10.1137/120878148

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F15, 65F35, 65N06, 65N25

Retrieve articles in all journals with MSC (2010): 65F15, 65F35, 65N06, 65N25


Additional Information

Qiang Ye
Affiliation: Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506
Email: qye3@uky.edu

DOI: https://doi.org/10.1090/mcom/3223
Keywords: Eigenvalue, ill-conditioned matrix, accuracy, Lanczos method, differential eigenvalue problem, biharmonic operator
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
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society