In this paper we present a novel matrix method for polynomial rootfinding. The roots are approximated by computing the eigenvalues of a permuted version of the companion matrix associated with the polynomial in block upper Hessenberg form with possibly nonsquare subdiagonal blocks. It is shown that this form, referred to as a lower staircase form of the companion matrix in reference to its characteristic appearance, is well suited for the application of the QR eigenvalue algorithm. In particular, each matrix generated under this iteration is block upper Hessenberg and, moreover, all its submatrices located in a specified upper triangular portion are of rank two at most with entries represented by means of four given vectors. By exploiting these properties we design a fast and computationally simple structured QR iteration which computes the eigenvalues of a companion matrix of size $n$ in lower staircase form using $O(n^2)$ flops and $O(n)$ memory storage. This iteration is theoretically faster than other fast variants of the QR iteration for companion matrices in customary Hessenberg form. Numerical experiments show the efficiency and the accuracy of the proposed approach.

A CMV--based eigensolver for companion matrices

BEVILACQUA, ROBERTO;DEL CORSO, GIANNA MARIA;GEMIGNANI, LUCA
2015

Abstract

In this paper we present a novel matrix method for polynomial rootfinding. The roots are approximated by computing the eigenvalues of a permuted version of the companion matrix associated with the polynomial in block upper Hessenberg form with possibly nonsquare subdiagonal blocks. It is shown that this form, referred to as a lower staircase form of the companion matrix in reference to its characteristic appearance, is well suited for the application of the QR eigenvalue algorithm. In particular, each matrix generated under this iteration is block upper Hessenberg and, moreover, all its submatrices located in a specified upper triangular portion are of rank two at most with entries represented by means of four given vectors. By exploiting these properties we design a fast and computationally simple structured QR iteration which computes the eigenvalues of a companion matrix of size $n$ in lower staircase form using $O(n^2)$ flops and $O(n)$ memory storage. This iteration is theoretically faster than other fast variants of the QR iteration for companion matrices in customary Hessenberg form. Numerical experiments show the efficiency and the accuracy of the proposed approach.
Bevilacqua, Roberto; DEL CORSO, GIANNA MARIA; Gemignani, Luca
File in questo prodotto:
File Dimensione Formato  
97806.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 344.7 kB
Formato Adobe PDF
344.7 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
simax_final.pdf

embargo fino al 21/06/2015

Descrizione: Articolo principale
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 781.06 kB
Formato Adobe PDF
781.06 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/750203
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 6
social impact