An Efficient Algorithm for Computing the Generalized Null Space Decomposition

The generalized null space decomposition (GNSD) is a unitary reduction of a general matrix $A$ of order $n$ to a block upper triangular form that reveals the structure of the Jordan blocks of $A$ corresponding to a zero eigenvalue. The reduction was introduced by Kublanovskaya. It was extended first...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 2015-01, Vol.36 (1), p.38-54
Main Authors: Guglielmi, Nicola, Overton, Michael L., Stewart, G. W.
Format: Article
Language:English
Subjects:
Algorithms
Blocking
Computation
Decomposition
Eigenvalues
Error analysis
Inverse
Reduction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The generalized null space decomposition (GNSD) is a unitary reduction of a general matrix $A$ of order $n$ to a block upper triangular form that reveals the structure of the Jordan blocks of $A$ corresponding to a zero eigenvalue. The reduction was introduced by Kublanovskaya. It was extended first by Ruhe and then by Golub and Wilkinson, who based the reduction on the singular value decomposition. Unfortunately, if $A$ has large Jordan blocks, the complexity of these algorithms can approach the order of $n pound sterling $. This paper presents an alternative algorithm, based on repeated updates of a QR decomposition of $A$, that is guaranteed to be of order $n3}$. Numerical experiments confirm the stability of this algorithm, which turns out to produce essentially the same form as that of Golub and Wilkinson. The effect of errors in $A$ on the ability to recover the original structure is investigated empirically. Several applications are discussed, including the computation of the Drazin inverse.
ISSN:0895-4798
1095-7162
DOI:10.1137/140956737