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.

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.
BIT
36
206
220
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.
I., BAR ON; B., Codenotti; Leoncini, Mauro
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/454048
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact