|
Computing singular values of diagonally dominant matrices to high relative accuracy
Author(s):
Qiang
Ye.
Journal:
Math. Comp.
77
(2008),
2195-2230.
MSC (2000):
Primary 65F18, 65F05
Posted:
May 5, 2008
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
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:
-
- 1.
- S. ALFA, J. XUE AND Q. YE, Entrywise perturbation theory for diagonally dominant M-matrices with applications, Numer. Math. 90(2002):401-414. MR 1884223 (2002j:65049)
- 2.
- S. ALFA, J. XUE AND Q. YE, Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix, Math. Comp. 71(2002):217-236. MR 1862996 (2002h:65054)
- 3.
- J. BARLOW AND J. DEMMEL, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Num. Anal. 27(1990):762-791. MR 1041262 (91g:65071)
- 4.
- P. DEIFT, J. DEMMEL, L.-C. LI, C. TOMEI, The bidiagonal singular value decomposition and Hamiltonian mechanics, SIAM J. Num. Anal. 28(1991):1463-1516. MR 1119279 (92i:65071)
- 5.
- J. DEMMEL, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997. MR 1463942 (98m:65001)
- 6.
- J. DEMMEL, Accurate SVDs of structured matrices, SIAM J. Matrix Anal. Appl. 21(1999):562-580. MR 1742810 (2001h:65036)
- 7.
- J. DEMMEL AND W. GRAGG, On computing accurate singular values and eigenvalues of matrices with acyclic graphs, Linear Algebra Appl. 185 (1993):203-217. MR 1213179 (94h:65044)
- 8.
- J. DEMMEL, M. GU, S. EISENSTAT, I. SLAPNICAR, K. VESELIC AND Z. DRMAC, Computing the singular value decomposition with high relative accuracy, Linear Alg. Appl. 299(1999):21-80. MR 1723709 (2000j:65044)
- 9.
- J. DEMMEL AND Y. HIDA, Accurate and Efficient Floating Point Summation, SIAM J. Sci. Comput. 25(4):1214-1248, 2003. MR 2045054 (2005b:65055)
- 10.
- J. DEMMEL AND W. KAHAN, Accurate singular values of bidiagonaly matrices, SIAM J. Sci. Stat. Comput. 11(1990):873-912. MR 1057146 (91i:65072)
- 11.
- J. DEMMEL, P. KOEV, Accurate SVDs of weakly diagonally dominant M-matrices, Numer. Math. 98(2004):99-104. MR 2076055 (2005g:65069)
- 12.
- J. DEMMEL, P. KOEV, Accurate SVDs of polynomial Vandermonde matrices involving orthonormal polynomials, Linear Algebra Appl. 417(2006):382-396. MR 2250320 (2007e:65038)
- 13.
- J. DEMMEL AND K. VESELIC, Jacobi's method is more accurate than QR, SIAM J. Matrix Anal. Appl. 13(1992):1204-1246. MR 1182723 (93e:65057)
- 14.
- F. DOPICO AND P. KOEV, Accurate symmetric rank revealing and eigendecompositions of symmetric structured matrices, SIAM J. Matrix Anal. Appl., 28 (2006): 1126-1156. MR 2276557
- 15.
- K. FERNANDO, B. PARLETT, Accurate singular values and differential qd algorithms, Numerische Mathematik 67 (1994):191-229. MR 1262781 (95a:65071)
- 16.
- G. GOLUB AND C. VAN LOAN, Matrix Computations, 2nd ed., The Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570 (90d:65055)
- 17.
- W.K. GRASSMANN, M.J. TAKSAR AND D.P. HEYMAN, Regenerative analysis and steady-state distributions for Markov chains, Operations Research 33(1985):1107-1116. MR 806921 (86k:60125)
- 18.
- N.J. HIGHAM, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996. MR 1368629 (97a:65047)
- 19.
- W. KAHAN, A survey of error analysis, In Proc. IFIP Congress, Ljubljana, Information Processing 71, North-Holland, Amsterdam, 1972, pp 1214-1239. MR 0458845 (56:17045)
- 20.
- P. KOEV, Accurate Eigenvalues and SVDs of Totally Nonnegative Matrices, SIAM J. Matrix Anal. Appl. 27(2005):1-23. MR 2176803 (2006j:15067)
- 21.
- P. KOEV AND F. DOPICO, Accurate eigenvalues of certain sign regular matrices, Linear Algebra Appl. 424 (2007):435-447. MR 2329485
- 22.
- R. MATHIAS, Accurate eigensystem computations by Jacobi methods, SIAM J. Matrix Anal. Appl. 16 (1995):977-1003. MR 1337657 (96f:65045)
- 23.
- C. O'CINNEIDE, Entrywise perturbation theory and error analysis for Markov chains, Numer. Math. 65(1993):109-120. MR 1217442 (94k:60101)
- 24.
- C. O'CINNEIDE, Relative-error bounds for the LU decomposition via the GTH algorithm, Numer. Math. 73(1996):507-519. MR 1393178 (97h:65033)
- 25.
- J. M. PEÑA, LDU decompositions with L and U well conditioned, Electr. Trans. Numer. Anal. 18 (2004): 198-208. MR 2150769 (2006b:65039)
- 26.
- R.S. VARGA, Matrix Iterative Analysis, 2nd ed. Springer-Berlag, Berlin, 2000. MR 1753713 (2001g:65002)
- 27.
- J. WILKINSON, The algebraic eigenvalue problem, Oxford University Press, 1965. MR 0184422 (32:1894)
- 28.
- Q. YE, Relative Perturbation Bounds for Eigenvalues of Symmetric Positive Definite Diagonally Dominant Matrices, SIAM J. Matrix Anal. Appl., to appear.
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
65F18, 65F05
Retrieve articles in all Journals with MSC
(2000):
65F18, 65F05
Additional Information:
Qiang
Ye
Affiliation:
Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506-0027
Email:
qye@ms.uky.edu
DOI:
10.1090/S0025-5718-08-02112-1
PII:
S 0025-5718(08)02112-1
Received by editor(s):
April 9, 2007
Received by editor(s) in revised form:
October 4, 2007
Posted:
May 5, 2008
Additional Notes:
This research was supported in part by NSF under Grant DMS-0411502.
Copyright of article:
Copyright
2008,
American Mathematical Society
|
Comments: webmaster@ams.org