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

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.
Bevilacqua, Roberto; Del Corso, Gianna M.; Gemignani, Luca
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/937932
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact