The generalized null space decomposition (GNSD) is a unitary reductionof a general matrix $A$ of order $n$ to a block upper triangular formthat reveals the structure of the Jordan blocks of $A$ correspondingto a zero eigenvalue. The reduction was introduced by Kublanovskaya.It was extended first by Ruhe and then by Golub and Wilkinson, whobased the reduction on the singular value decomposition.Unfortunately, if $A$ has large Jordan blocks, the complexity of thesealgorithms can approach the order of $n^4$. This paper presents analternative algorithm, based on repeated updates of a QR decompositionof $A$, that is guaranteed to be of order $n^{3}$. Numericalexperiments confirm the stability of this algorithm, which turns outto produce essentially the same form as that of Golub and Wilkinson.The effect of errors in $A$ on the ability to recover the originalstructure is investigated empirically. Several applications are discussed,including the computation of the Drazin inverse.

An efficient algorithm for computing the generalized null space decomposition

GUGLIELMI, NICOLA;
2015-01-01

Abstract

The generalized null space decomposition (GNSD) is a unitary reductionof a general matrix $A$ of order $n$ to a block upper triangular formthat reveals the structure of the Jordan blocks of $A$ correspondingto a zero eigenvalue. The reduction was introduced by Kublanovskaya.It was extended first by Ruhe and then by Golub and Wilkinson, whobased the reduction on the singular value decomposition.Unfortunately, if $A$ has large Jordan blocks, the complexity of thesealgorithms can approach the order of $n^4$. This paper presents analternative algorithm, based on repeated updates of a QR decompositionof $A$, that is guaranteed to be of order $n^{3}$. Numericalexperiments confirm the stability of this algorithm, which turns outto produce essentially the same form as that of Golub and Wilkinson.The effect of errors in $A$ on the ability to recover the originalstructure is investigated empirically. Several applications are discussed,including the computation of the Drazin inverse.
2015
generalized null space; Jordan form; staircase algorithms; Drazin inverse
File in questo prodotto:
File Dimensione Formato  
2015_SIAMJMatrixAnalAppl_36_Guglielmi.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 244.31 kB
Formato Adobe PDF
244.31 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

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