×

Accurate inverses for computing eigenvalues of extremely ill-conditioned matrices and differential operators. (English) Zbl 1376.65057

Summary: 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.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
65N06 Finite difference methods for boundary value problems involving PDEs
65N25 Numerical methods for eigenvalue problems for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alfa, Attahiru Sule; Xue, Jungong; Ye, Qiang, Entrywise perturbation theory for diagonally dominant \(M\)-matrices with applications, Numer. Math., 90, 3, 401-414 (2002) · Zbl 1022.15020 · doi:10.1007/s002110100289
[2] Alfa, Attahiru Sule; Xue, Jungong; Ye, Qiang, Accurate computation of the smallest eigenvalue of a diagonally dominant \(M\)-matrix, Math. Comp., 71, 237, 217-236 (2002) · Zbl 0984.65033 · doi:10.1090/S0025-5718-01-01325-4
[3] Babu{\v{s}}ka, I.; Osborn, J., Eigenvalue Problems, Handb. Numer. Anal., II, 641-787 (1991), North-Holland, Amsterdam · Zbl 0875.65087
[4] Barlow, Jesse; Demmel, James, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Numer. Anal., 27, 3, 762-791 (1990) · Zbl 0725.65043 · doi:10.1137/0727045
[5] Bauer, Louis; Reiss, Edward L., Block five diagonal matrices and the fast numerical solution of the biharmonic equation, Math. Comp., 26, 311-326 (1972) · Zbl 0257.65034
[6] Ben-Artzi, Matania; Croisille, Jean-Pierre; Fishelov, Dalia, A fast direct solver for the biharmonic problem in a rectangular grid, SIAM J. Sci. Comput., 31, 1, 303-333 (2008) · Zbl 1184.35126 · doi:10.1137/070694168
[7] Bj{\o }rstad, Petter E.; Tj{\o }stheim, Bj{\o }rn Peter, Efficient algorithms for solving a fourth-order equation with the spectral-Galerkin method, SIAM J. Sci. Comput., 18, 2, 621-632 (1997) · Zbl 0939.65129 · doi:10.1137/S1064827596298233
[8] Bj{\o }rstad, P. E.; Tj{\o }stheim, B. P., High precision solutions of two fourth order eigenvalue problems, Computing, 63, 2, 97-107 (1999) · Zbl 0940.65119 · doi:10.1007/s006070050053
[9] bogg05 T. Boggio, Sulle funzioni di Green d’ordine m, Rend. Circ. Mat. Palermo 20 (1905), 97-135. · JFM 36.0827.01
[10] Bramble, J. H., A second order finite difference analog of the first biharmonic boundary value problem, Numer. Math., 9, 236-249 (1966) · Zbl 0154.41105
[11] brms 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/. · Zbl 1349.65439
[12] Brown, B. M.; Davies, E. B.; Jimack, P. K.; Mihajlovi{\'c}, M. D., 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, 1998, 1505-1521 (2000) · Zbl 0977.65101 · doi:10.1098/rspa.2000.0573
[13] Ciarlet, P. G., Conforming and nonconforming finite element methods for solving the plate problem. Conference on the Numerical Solution of Differential Equations, Univ. of Dundee, Dundee, 1973, 21-31. Lecture Notes in Math., Vol. 363 (1974), Springer, Berlin · Zbl 0285.65072
[14] Chen, Wei, Eigenvalue approximation of the biharmonic eigenvalue problem by Ciarlet-Raviart scheme, Numer. Methods Partial Differential Equations, 21, 3, 512-520 (2005) · Zbl 1073.65124 · doi:10.1002/num.20043
[15] Chen, Goong; Coleman, Matthew P.; Zhou, Jianxin, 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, 4, 967-983 (1991) · Zbl 0733.73045 · doi:10.1137/0151048
[16] Coffman, C. V.; Duffin, R. J., On the structure of biharmonic functions satisfying the clamped plate conditions on a right angle, Adv. in Appl. Math., 1, 4, 373-389 (1980) · Zbl 0452.35002 · doi:10.1016/0196-8858(80)90018-4
[17] Dai, Xiaoying; Xu, Jinchao; Zhou, Aihui, Convergence and optimal complexity of adaptive finite element eigenvalue computations, Numer. Math., 110, 3, 313-355 (2008) · Zbl 1159.65090 · doi:10.1007/s00211-008-0169-3
[18] Dailey, Megan; Dopico, Froil{\'a}n M.; Ye, Qiang, Relative perturbation theory for diagonally dominant matrices, SIAM J. Matrix Anal. Appl., 35, 4, 1303-1328 (2014) · Zbl 1317.15019 · doi:10.1137/130943613
[19] Dailey, Megan; Dopico, Froil{\'a}n M.; Ye, Qiang, A new perturbation bound for the LDU factorization of diagonally dominant matrices, SIAM J. Matrix Anal. Appl., 35, 3, 904-930 (2014) · Zbl 1306.65179 · doi:10.1137/13093858X
[20] Demmel, James W., Applied Numerical Linear Algebra, xii+419 pp. (1997), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0879.65017 · doi:10.1137/1.9781611971446
[21] Demmel, James, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl., 21, 2, 562-580 (1999) · Zbl 0951.65036 · doi:10.1137/S0895479897328716
[22] Demmel, James; Gu, Ming; Eisenstat, Stanley; Slapni{\v{c}}ar, Ivan; Veseli{\'c}, Kre{\v{s}}imir; Drma{\v{c}}, Zlatko, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl., 299, 1-3, 21-80 (1999) · Zbl 0952.65032 · doi:10.1016/S0024-3795(99)00134-2
[23] Demmel, James; Kahan, W., Accurate singular values of bidiagonal matrices, SIAM J. Sci. Statist. Comput., 11, 5, 873-912 (1990) · Zbl 0705.65027 · doi:10.1137/0911052
[24] Demmel, James; Koev, Plamen, Accurate SVDs of weakly diagonally dominant \(M\)-matrices, Numer. Math., 98, 1, 99-104 (2004) · Zbl 1054.65037 · doi:10.1007/s00211-004-0527-8
[25] Demmel, James; Veseli{\'c}, Kre{\v{s}}imir, Jacobi’s method is more accurate than \(QR\), SIAM J. Matrix Anal. Appl., 13, 4, 1204-1245 (1992) · Zbl 0759.65011 · doi:10.1137/0613074
[26] Dopico, Froil{\'a}n M.; Koev, Plamen, Accurate symmetric rank revealing and eigendecompositions of symmetric structured matrices, SIAM J. Matrix Anal. Appl., 28, 4, 1126-1156 (electronic) (2006) · Zbl 1124.65039 · doi:10.1137/050633792
[27] Dopico, Froil{\'a}n M.; Koev, Plamen, Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices, Numer. Math., 119, 2, 337-371 (2011) · Zbl 1254.65042 · doi:10.1007/s00211-011-0382-3
[28] Dopico, Froil{\'a}n M.; Koev, Plamen; Molera, Juan M., Implicit standard Jacobi gives high relative accuracy, Numer. Math., 113, 4, 519-553 (2009) · Zbl 1223.65025 · doi:10.1007/s00211-009-0240-8
[29] Dopico, Froil{\'a}n M.; Molera, Juan M., Accurate solution of structured linear systems via rank-revealing decompositions, IMA J. Numer. Anal., 32, 3, 1096-1116 (2012) · Zbl 1251.65040 · doi:10.1093/imanum/drr023
[30] drma14 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] Ehrlich, Louis W., Solving the biharmonic equation as coupled finite difference equations., SIAM J. Numer. Anal., 8, 278-287 (1971) · Zbl 0198.21501
[32] embry M. Embree, private communication.
[33] Fernando, K. Vince; Parlett, Beresford N., Accurate singular values and differential qd algorithms, Numer. Math., 67, 2, 191-229 (1994) · Zbl 0814.65036 · doi:10.1007/s002110050024
[34] Fishelov, D.; Ben-Artzi, M.; Croisille, J.-P., Recent advances in the study of a fourth-order compact scheme for the one-dimensional biharmonic equation, J. Sci. Comput., 53, 1, 55-79 (2012) · Zbl 1254.65117 · doi:10.1007/s10915-012-9611-x
[35] Grassmann, Winfried K.; Taksar, Michael I.; Heyman, Daniel P., Regenerative analysis and steady state distributions for Markov chains, Oper. Res., 33, 5, 1107-1116 (1985) · Zbl 0576.60083 · doi:10.1287/opre.33.5.1107
[36] Garabedian, P. R., A partial differential equation arising in conformal mapping, Pacific J. Math., 1, 485-524 (1951) · Zbl 0045.05102
[37] Grunau, Hans-Christoph; Robert, Fr{\'e}d{\'e}ric, Positivity and almost positivity of biharmonic Green’s functions under Dirichlet boundary conditions, Arch. Ration. Mech. Anal., 195, 3, 865-898 (2010) · Zbl 1200.35090 · doi:10.1007/s00205-009-0230-0
[38] Golub, Gene H.; Van Loan, Charles F., Matrix Computations, Johns Hopkins Series in the Mathematical Sciences 3, xxii+642 pp. (1989), Johns Hopkins University Press, Baltimore, MD · Zbl 0733.65016
[39] Hackbusch, Wolfgang; Hofmann, G{\"o}tz, Results of the eigenvalue problem for the plate equation, Z. Angew. Math. Phys., 31, 6, 730-739 (1980) · Zbl 0458.73065 · doi:10.1007/BF01594119
[40] Jiang, Ying; Wang, Bo; Xu, Yuesheng, A fast Fourier-Galerkin method solving a boundary integral equation for the biharmonic equation, SIAM J. Numer. Anal., 52, 5, 2530-2554 (2014) · Zbl 1307.31008 · doi:10.1137/140955744
[41] Keller, Herbert B., On the accuracy of finite difference approximations to the eigenvalues of differential and integral operators, Numer. Math., 7, 412-419 (1965) · Zbl 0135.37702
[42] Kuttler, James R., A finite-difference approximation for the eigenvalues of the clamped plate, Numer. Math., 17, 230-238 (1971) · Zbl 0205.10001
[43] Li, Ren-Cang, Relative perturbation theory. I. Eigenvalue and singular value variations, SIAM J. Matrix Anal. Appl., 19, 4, 956-982 (1998) · Zbl 0917.15009 · doi:10.1137/S089547989629849X
[44] Mitchell, Andrew Ronald; Griffiths, D. F., The finite difference method in partial differential equations, xii+272 pp. (1980), John Wiley & Sons, Ltd., Chichester · Zbl 0417.65048
[45] Mehrmann, Volker; Miedlar, Agnieszka, Adaptive computation of smallest eigenvalues of self-adjoint elliptic partial differential equations, Numer. Linear Algebra Appl., 18, 3, 387-409 (2011) · Zbl 1249.65226 · doi:10.1002/nla.733
[46] Parlett, Beresford N., The Symmetric Eigenvalue Problem, Classics in Applied Mathematics 20, xxiv+398 pp. (1998), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0885.65039 · doi:10.1137/1.9781611971163
[47] Pe{\~n}a, J. M., LDU decompositions with L and U well conditioned, Electron. Trans. Numer. Anal., 18, 198-208 (electronic) (2004) · Zbl 1083.65033
[48] Rannacher, Rolf, Nonconforming finite element methods for eigenvalue problems in linear plate theory, Numer. Math., 33, 1, 23-42 (1979) · Zbl 0394.65035 · doi:10.1007/BF01396493
[49] Varga, Richard S., Matrix Iterative Analysis, Springer Series in Computational Mathematics 27, x+358 pp. (2000), Springer-Verlag, Berlin · Zbl 1216.65042 · doi:10.1007/978-3-642-05156-2
[50] Weinberger, Hans F., Variational methods for eigenvalue approximation, v+160 pp. (1974), Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 0296.49033
[51] Ye, Qiang, Computing singular values of diagonally dominant matrices to high relative accuracy, Math. Comp., 77, 264, 2195-2230 (2008) · Zbl 1198.65077 · doi:10.1090/S0025-5718-08-02112-1
[52] Ye, Qiang, Relative perturbation bounds for eigenvalues of symmetric positive definite diagonally dominant matrices, SIAM J. Matrix Anal. Appl., 31, 1, 11-17 (2009) · Zbl 1189.15026 · doi:10.1137/060676349
[53] Zhang, Shuo; Xu, Jinchao, Optimal solvers for fourth-order PDEs discretized on unstructured grids, SIAM J. Numer. Anal., 52, 1, 282-307 (2014) · Zbl 1293.65160 · doi:10.1137/120878148
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.