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

Keywords

  • math.NA

Fingerprint Dive into the research topics of 'Fast and backward stable computation of the eigenvalues of matrix polynomials'. Together they form a unique fingerprint.

  • KU Leuven

    Thomas Mach (Visiting researcher)

    Oct 10 2016Oct 14 2016

    Activity: Visiting typesVisiting an external research institution

Cite this