In this paper we present a linear time algorithm for checking whether a tridiagonal matrix will become singular under certain perturbations of its coefficients. The problem is known to be NP-hard for general matrices. Our algorithm can be used to get perturbation bounds on the solutions to tridiagonal systems.
CHECKING ROBUST NONSINGULARITY OF TRIDIAGONAL MATRICES IN LINEAR TIME / I., Bar On; B., Codenotti; Leoncini, Mauro. - In: BIT. - ISSN 0006-3835. - STAMPA. - 36:(1996), pp. 206-220. [10.1007/BF01731979]
CHECKING ROBUST NONSINGULARITY OF TRIDIAGONAL MATRICES IN LINEAR TIME
LEONCINI, Mauro
1996
Abstract
In this paper we present a linear time algorithm for checking whether a tridiagonal matrix will become singular under certain perturbations of its coefficients. The problem is known to be NP-hard for general matrices. Our algorithm can be used to get perturbation bounds on the solutions to tridiagonal systems.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
