Computing singular values of diagonally dominant matrices to high relative accuracy
Author:
Open Access
- 5 May 2008
- journal article
- research article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 77 (264) , 2195-2230
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.Keywords
This publication has 25 references indexed in Scilit:
- Accurate and Efficient Floating Point SummationSIAM Journal on Scientific Computing, 2004
- Entrywise perturbation theory for diagonally dominant M-matrices with applicationsNumerische Mathematik, 2002
- Accurate computation of the smallest eigenvalue of a diagonally dominant $M$-matrixMathematics of Computation, 2001
- Accurate Singular Value Decompositions of Structured MatricesSIAM Journal on Matrix Analysis and Applications, 2000
- Computing the singular value decomposition with high relative accuracyLinear Algebra and its Applications, 1999
- Applied Numerical Linear Algebra1997
- On computing accurate singular values and eigenvalues of matrices with acyclic graphsLinear Algebra and its Applications, 1993
- The Bidiagonal Singular Value Decomposition and Hamiltonian MechanicsSIAM Journal on Numerical Analysis, 1991
- Accurate Singular Values of Bidiagonal MatricesSIAM Journal on Scientific and Statistical Computing, 1990
- Computing Accurate Eigensystems of Scaled Diagonally Dominant MatricesSIAM Journal on Numerical Analysis, 1990