Some fast algorithms for computing the eigenvalues of a block companion matrix A=U+XYH, where U∈Cn×n is unitary block circulant and X,Y∈Cn×k, have recently appeared in the literature. Most of these algorithms rely on the decomposition of A as product of scalar companion matrices which turns into a factored representation of the Hessenberg reduction of A. In this paper we generalize the approach to encompass Hessenberg matrices of the form A=U+XYH where U is a general unitary matrix. A remarkable case is U unitary diagonal which makes possible to deal with interpolation techniques for rootfinding problems and nonlinear eigenvalue problems. Our extension exploits the properties of a larger matrix A^ obtained by a certain embedding of the Hessenberg reduction of A suitable to maintain its structural properties. We show that A^ can be factored as product of lower and upper unitary Hessenberg matrices possibly perturbed in the first k rows, and, moreover, such a data-sparse representation is well suited for the design of fast eigensolvers based on the QR/QZ iteration. The resulting algorithm is fast and backward stable.
Fast QR iterations for unitary plus low rank matrices
Roberto Bevilacqua;Gianna M. Del Corso
;Luca Gemignani
2020-01-01
Abstract
Some fast algorithms for computing the eigenvalues of a block companion matrix A=U+XYH, where U∈Cn×n is unitary block circulant and X,Y∈Cn×k, have recently appeared in the literature. Most of these algorithms rely on the decomposition of A as product of scalar companion matrices which turns into a factored representation of the Hessenberg reduction of A. In this paper we generalize the approach to encompass Hessenberg matrices of the form A=U+XYH where U is a general unitary matrix. A remarkable case is U unitary diagonal which makes possible to deal with interpolation techniques for rootfinding problems and nonlinear eigenvalue problems. Our extension exploits the properties of a larger matrix A^ obtained by a certain embedding of the Hessenberg reduction of A suitable to maintain its structural properties. We show that A^ can be factored as product of lower and upper unitary Hessenberg matrices possibly perturbed in the first k rows, and, moreover, such a data-sparse representation is well suited for the design of fast eigensolvers based on the QR/QZ iteration. The resulting algorithm is fast and backward stable.File | Dimensione | Formato | |
---|---|---|---|
Bevilacqua2019_Article_FastQRIterationsForUnitaryPlus.pdf
solo utenti autorizzati
Tipologia:
Versione finale editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
620.86 kB
Formato
Adobe PDF
|
620.86 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Preprint.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
863.44 kB
Formato
Adobe PDF
|
863.44 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.