Fast and backward stable computation of the eigenvalues of matrix polynomials

Jared Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. Watkins

Research output: Contribution to journalArticle

Abstract

In the last decade matrix polynomials have been investigated with the primary focus on adequate linearizations and good scaling techniques for computing their eigenvalues. In this article we propose a new backward stable method for computing a factored Schur form of the associated companion pencil. The algorithm has a quadratic cost in the degree of the polynomial and a cubic one in the size of the coefficient matrices. The algorithm is a variant of Francis's implicitly shifted QR algorithm applied on the associated companion pencil. A preprocessing unitary equivalence is executed on the matrix polynomial to simultaneously bring the leading matrix coefficient and the constant matrix term to triangular form before forming the companion pencil. The resulting structure allows us to stably factor both matrices of the pencil into $k$ matrices which are of unitary-plus-rank-one form admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. The numerical experiments illustrate stability and efficiency of the proposed methods.
Original languageEnglish
JournalarXiv
Volume1611
Issue number10142
Publication statusPublished - Nov 30 2016

Fingerprint

Matrix Polynomial
Eigenvalue
QR Algorithm
Computing
Coefficient
Linearization
Eigenvalue Problem
Preprocessing
Triangular
Numerical Experiment
Equivalence
Scaling
Polynomial
Costs
Term
Form

Keywords

  • math.NA

Cite this

Aurentz, J., Mach, T., Robol, L., Vandebril, R., & Watkins, D. S. (2016). Fast and backward stable computation of the eigenvalues of matrix polynomials. arXiv, 1611(10142).

Fast and backward stable computation of the eigenvalues of matrix polynomials. / Aurentz, Jared; Mach, Thomas; Robol, Leonardo; Vandebril, Raf; Watkins, David S.

In: arXiv, Vol. 1611, No. 10142, 30.11.2016.

Research output: Contribution to journalArticle

Aurentz, J, Mach, T, Robol, L, Vandebril, R & Watkins, DS 2016, 'Fast and backward stable computation of the eigenvalues of matrix polynomials', arXiv, vol. 1611, no. 10142.
Aurentz J, Mach T, Robol L, Vandebril R, Watkins DS. Fast and backward stable computation of the eigenvalues of matrix polynomials. arXiv. 2016 Nov 30;1611(10142).
Aurentz, Jared ; Mach, Thomas ; Robol, Leonardo ; Vandebril, Raf ; Watkins, David S. / Fast and backward stable computation of the eigenvalues of matrix polynomials. In: arXiv. 2016 ; Vol. 1611, No. 10142.
@article{06557c0703354517a0703aa6e06d7222,
title = "Fast and backward stable computation of the eigenvalues of matrix polynomials",
abstract = "In the last decade matrix polynomials have been investigated with the primary focus on adequate linearizations and good scaling techniques for computing their eigenvalues. In this article we propose a new backward stable method for computing a factored Schur form of the associated companion pencil. The algorithm has a quadratic cost in the degree of the polynomial and a cubic one in the size of the coefficient matrices. The algorithm is a variant of Francis's implicitly shifted QR algorithm applied on the associated companion pencil. A preprocessing unitary equivalence is executed on the matrix polynomial to simultaneously bring the leading matrix coefficient and the constant matrix term to triangular form before forming the companion pencil. The resulting structure allows us to stably factor both matrices of the pencil into $k$ matrices which are of unitary-plus-rank-one form admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. The numerical experiments illustrate stability and efficiency of the proposed methods.",
keywords = "math.NA",
author = "Jared Aurentz and Thomas Mach and Leonardo Robol and Raf Vandebril and Watkins, {David S.}",
year = "2016",
month = "11",
day = "30",
language = "English",
volume = "1611",
journal = "arXiv",
issn = "2331-8422",
number = "10142",

}

TY - JOUR

T1 - Fast and backward stable computation of the eigenvalues of matrix polynomials

AU - Aurentz, Jared

AU - Mach, Thomas

AU - Robol, Leonardo

AU - Vandebril, Raf

AU - Watkins, David S.

PY - 2016/11/30

Y1 - 2016/11/30

N2 - In the last decade matrix polynomials have been investigated with the primary focus on adequate linearizations and good scaling techniques for computing their eigenvalues. In this article we propose a new backward stable method for computing a factored Schur form of the associated companion pencil. The algorithm has a quadratic cost in the degree of the polynomial and a cubic one in the size of the coefficient matrices. The algorithm is a variant of Francis's implicitly shifted QR algorithm applied on the associated companion pencil. A preprocessing unitary equivalence is executed on the matrix polynomial to simultaneously bring the leading matrix coefficient and the constant matrix term to triangular form before forming the companion pencil. The resulting structure allows us to stably factor both matrices of the pencil into $k$ matrices which are of unitary-plus-rank-one form admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. The numerical experiments illustrate stability and efficiency of the proposed methods.

AB - In the last decade matrix polynomials have been investigated with the primary focus on adequate linearizations and good scaling techniques for computing their eigenvalues. In this article we propose a new backward stable method for computing a factored Schur form of the associated companion pencil. The algorithm has a quadratic cost in the degree of the polynomial and a cubic one in the size of the coefficient matrices. The algorithm is a variant of Francis's implicitly shifted QR algorithm applied on the associated companion pencil. A preprocessing unitary equivalence is executed on the matrix polynomial to simultaneously bring the leading matrix coefficient and the constant matrix term to triangular form before forming the companion pencil. The resulting structure allows us to stably factor both matrices of the pencil into $k$ matrices which are of unitary-plus-rank-one form admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. The numerical experiments illustrate stability and efficiency of the proposed methods.

KW - math.NA

M3 - Article

VL - 1611

JO - arXiv

JF - arXiv

SN - 2331-8422

IS - 10142

ER -