Cited By
View all- Yang ZHuang RZhu WLiu J(2021)Accurate solutions of structured generalized Kronecker product linear systemsNumerical Algorithms10.1007/s11075-020-00988-587:2(797-818)Online publication date: 1-Jun-2021
Accurate solutions of diagonally dominant tridiagonal linear systems
Authors: 
Rong Huang, Jianzhou Liu, Li ZhuAuthors Info & Claims
Abstract
In this paper, we settle Higham’s conjecture for the LU factorization of diagonally dominant tridiagonal matrices. We establish a strong componentwise perturbation bound for the solution of a diagonally dominant tridiagonal linear system, independent of the traditional condition number of the coefficient matrix. We then accurately and efficiently solve the linear system by the GTH-like algorithm without pivoting, as suggested by the perturbation result.
References
[1]
Alfa, A.S., Xue, J., Ye, Q.: Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix. Math. Comp. 71, 217–236 (2002)
[2]
Alfa, A.S., Xue, J., Ye, Q.: Entrywise perturbation theory for diagonally dominant M-matrices with applications. Numer. Math. 90, 401–414 (2002)
[3]
Banoczi, J.M., Chiu, N.C., Cho, G.E., Ipsen, I.C.F.: The lack of influence of the right-hand side on the accuracy of linear system solutions. SIAM J. Sci. Comput. 20, 203–227 (1998)
[4]
Bar-On, I., Leoncini, M.: Reliable solution of tridiagonal systems of linear equations. SIAM J. Numer. Anal. 38, 1134–1153 (2000)
[5]
Barlow, J., Demmel, J.: Computing accurate eigensystems of scaled diagonally dominant matrices. SIAM J. Numer. Anal. 27, 762–791 (1990)
[6]
Barreras, A., Peña, J.M.: Accurate and efficient LDU decompositions of diagonally dominant M-matrices. Electron. J. Linear Algebra 24, 152–167 (2012/2013)
[7]
Boisvert, R.F.: Algorithms for special tridiagonal systems. SIAM J. Sci. and Stat. Comput. 12, 423–442 (1991)
[8]
Bueno, M., Dopico, F.: Stability and sensitivity of tridiagonal LU factorization without pivoting. BIT 44, 651–673 (2004)
[9]
Demmel, J., Koev, P.: Accurate SVDs of weakly diagonally dominant M-matrices. Numer. Math. 98, 99–104 (2004)
[10]
Dorr, F.W.: An example of ill-conditioning in the numerical solution of singular perturbation problems. Math. Comp. 25, 271–293 (1971)
[11]
Dopico, F., Koev, P.: Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices. Numer. Math. 119, 337–371 (2011)
[12]
Dopico, F., Molera, J.M.: Accurate solution of structured linear systems via rank-revealing decompositions. IMA J. Numer. Anal. 32, 1096–1116 (2012)
[13]
da Fonseca, C.M., Petronilho, J.: Explicit inverse of a tridiagonal k-Toeplitz matrix. Numer. Math. 100, 457–482 (2005)
[14]
El-Shehawey, M.A.: On inverses of tridiagonal matrices arising from Markov chain-random walk I. SIAM J. Matrix Anal. Appl. 30, 497–508 (2008)
[15]
Fischer, C.F., Usmani, R.A.: Properties of some tridiagonal matrices and their application to boundary value problems. SIAM J. Numer. Anal. 6, 127–142 (1969)
[16]
Higham, N.J.: Bounding the error in Gaussian elimination for tridiagonal systems. SIAM J. Matrix Anal. Appl. 11, 521–530 (1990)
[17]
Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002)
[18]
Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991)
[19]
Matejas, J., Hari, V.: Accuracy of the Kogbetliantz method for scaled diagonally dominant triangular matrices. Appl. Math. Comput. 217, 3726–3746 (2010)
[20]
Meurant, G.: A review on the inverse of symmetric tridiagonal and block tridiagonal matrices. SIAM J. Matrix Anal. Appl. 13, 707–728 (1992)
[21]
Nabben, R.: Two-sided bounds on the inverses of diagonally dominant tridiagonal matrices. Linear Algebra Appl. 287, 289–305 (1999)
[22]
Nabben, R.: Decay rates of the inverse of nonsymmetric tridiagonal and band matrices. SIAM J. Numer. Anal. 20, 820–837 (1999)
[23]
Walshaw, C.H.: Diagonal dominance in the parallel partition method for tridiagonal systems. SIAM J. Matrix Anal. Appl. 16, 1086–1099 (1995)
[24]
Xue, J., Jiang, E.: Entrywise relative perturbation theory for nonsingular M-matrices and its applications. BIT 35, 417–427 (1995)
[25]
Ye, Q.: Computing singular values of diagonally dominant matrices to high relative accuracy. Math. Comp. 77, 2195–2230 (2008)
[26]
Ye, Q.: Relative perturbation bounds for eigenvalues of symmetric positive definite diagonally dominant matrices. SIAM J. Matrix Anal. Appl. 31, 11–17 (2009)
Index Terms
- Accurate solutions of diagonally dominant tridiagonal linear systems
Index terms have been assigned to the content through auto-classification.
Recommendations
Stochastic Preconditioning for Diagonally Dominant Matrices
This paper presents a new stochastic preconditioning approach for large sparse matrices. For the class of matrices that are rowwise and columnwise irreducibly diagonally dominant, we prove that an incomplete $\rm{LDL^T}$ factorization in a symmetric ...
A Stable Parallel Algorithm for Diagonally Dominant Tridiagonal Linear Systems
HIPC '15: Proceedings of the 2015 IEEE 22nd International Conference on High Performance Computing (HiPC)In this work, we present a stable parallel algorithm based on WZ factorization for solving diagonally dominant tridiagonal linear system of algebraic equations, using divide and conquer approach. Existence results are given and the backward error ...
On diagonal-Schur complements of block diagonally dominant matrices
It is known that the diagonal-Schur complements of strictly diagonally dominant matrices are strictly diagonally dominant matrices [J.Z. Liu, Y.Q. Huang, Some properties on Schur complements of H-matrices and diagonally dominant matrices, Linear Algebra ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2014 Springer Science+Business Media Dordrecht.
Publisher
BIT Computer Science and Numerical Mathematics
United States
Publication History
Published: 01 September 2014
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025
Other Metrics
Citations
Cited By
View all- Yang ZHuang RZhu WLiu J(2021)Accurate solutions of structured generalized Kronecker product linear systemsNumerical Algorithms10.1007/s11075-020-00988-587:2(797-818)Online publication date: 1-Jun-2021