Computing singular values of diagonally dominant matrices to high relative accuracy

Ye, Qiang

doi:10.1090/S0025-5718-08-02112-1

Computing singular values of diagonally dominant matrices to high relative accuracy
HTML articles powered by AMS MathViewer

by Qiang Ye PDF

Math. Comp. 77 (2008), 2195-2230 Request permission

Abstract:

For a (row) diagonally dominant matrix, if all of its off-diagonal entries and its diagonally dominant parts (which are defined for each row as the absolute value of the diagonal entry subtracted by the sum of the absolute values of off-diagonal entries in that row) are accurately known, we develop an algorithm that computes all the singular values, including zero ones if any, with relative errors in the order of the machine precision. When the matrix is also symmetric with positive diagonals (i.e. a symmetric positive semi-definite diagonally dominant matrix), our algorithm computes all eigenvalues to high relative accuracy. Rounding error analysis will be given and numerical examples will be presented to demonstrate the high relative accuracy of the algorithm.

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
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
Percy Deift, James Demmel, Luen Chau Li, and Carlos Tomei, The bidiagonal singular value decomposition and Hamiltonian mechanics, SIAM J. Numer. Anal. 28 (1991), no. 5, 1463–1516. MR 1119279, DOI 10.1137/0728076
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 W. Demmel and William Gragg, On computing accurate singular values and eigenvalues of matrices with acyclic graphs, Linear Algebra Appl. 185 (1993), 203–217. MR 1213179, DOI 10.1016/0024-3795(93)90213-8
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 Yozo Hida, Accurate and efficient floating point summation, SIAM J. Sci. Comput. 25 (2003/04), no. 4, 1214–1248. MR 2045054, DOI 10.1137/S1064827502407627
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 Plamen Koev, Accurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials, Linear Algebra Appl. 417 (2006), no. 2-3, 382–396. MR 2250320, DOI 10.1016/j.laa.2005.09.014
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
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
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
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
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
W. Kahan, A survey of error analysis, Information processing 71 (Proc. IFIP Congr., Ljubljana, 1971) North-Holland, Amsterdam, 1972, pp. 1214–1239. MR 0458845
Plamen Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl. 27 (2005), no. 1, 1–23. MR 2176803, DOI 10.1137/S0895479803438225
Plamen Koev and Froilán Dopico, Accurate eigenvalues of certain sign regular matrices, Linear Algebra Appl. 424 (2007), no. 2-3, 435–447. MR 2329485, DOI 10.1016/j.laa.2007.02.012
Roy Mathias, Accurate eigensystem computations by Jacobi methods, SIAM J. Matrix Anal. Appl. 16 (1995), no. 3, 977–1003. MR 1337657, DOI 10.1137/S089547989324820X
Colm Art O’Cinneide, Entrywise perturbation theory and error analysis for Markov chains, Numer. Math. 65 (1993), no. 1, 109–120. MR 1217442, DOI 10.1007/BF01385743
Colm Art O’Cinneide, Relative-error bounds for the $LU$ decomposition via the GTH algorithm, Numer. Math. 73 (1996), no. 4, 507–519. MR 1393178, DOI 10.1007/s002110050203
J. M. Peña, LDU decompositions with L and U well conditioned, Electron. Trans. Numer. Anal. 18 (2004), 198–208. MR 2150769
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
J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422
Q. Ye, Relative Perturbation Bounds for Eigenvalues of Symmetric Positive Definite Diagonally Dominant Matrices, SIAM J. Matrix Anal. Appl., to appear.