AMS :: Mathematics of Computation Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials
HTML articles powered by AMS MathViewer

by Jared Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril and David S. Watkins;
Math. Comp. 88 (2019), 313-347
DOI: https://doi.org/10.1090/mcom/3338
Published electronically: April 12, 2018

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 and eigenvectors. In this article we propose a new 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. Also the eigenvectors can be computed at the same cost.

The algorithm is a variant of Francis’s implicitly shifted QR algorithm applied on the 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 each matrix of the pencil as a product of $k$ matrices of unitary-plus-rank-one form, admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. A backward error analysis is included, implying normwise backward stability after a proper scaling. Computing the eigenvectors via reordering the Schur form is discussed as well.

Numerical experiments illustrate stability and efficiency of the proposed methods.

References
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 65F15, 65L07
  • Retrieve articles in all journals with MSC (2010): 65F15, 65L07
Bibliographic Information
  • Jared Aurentz
  • Affiliation: Instituto de Ciencias Matemáticas, Universidad Autónoma de Madrid, Madrid, Spain
  • MR Author ID: 1012086
  • Email: jared.aurentz@icmat.es
  • Thomas Mach
  • Affiliation: Department of Mathematics, Nazarbayev University, Astana 010000, Kazakhstan
  • MR Author ID: 901224
  • Email: thomas.mach@nu.edu.kz
  • Leonardo Robol
  • Affiliation: ISTI, Area della ricerca CNR, Pisa, Italy
  • MR Author ID: 1069123
  • Email: leonardo.robol@isti.cnr.it
  • Raf Vandebril
  • Affiliation: Department of Computer Science, KU Leuven, 3001 Leuven, Belgium
  • MR Author ID: 720650
  • Email: raf.vandebril@cs.kuleuven.be
  • David S. Watkins
  • Affiliation: Department of Mathematics, Washington State University, Pullman, Washington 99164-3113
  • MR Author ID: 180870
  • Email: watkins@math.wsu.edu
  • Received by editor(s): November 16, 2016
  • Received by editor(s) in revised form: June 14, 2017, and October 31, 2017
  • Published electronically: April 12, 2018
  • Additional Notes: This research was partially supported by the Research Council KU Leuven, project C14/16/056 (Inverse-free Rational Krylov Methods: Theory and Applications), and by the GNCS/INdAM project “Metodi numerici avanzati per equazioni e funzioni di matrici con struttura”.
  • © Copyright 2018 American Mathematical Society
  • Journal: Math. Comp. 88 (2019), 313-347
  • MSC (2010): Primary 65F15, 65L07
  • DOI: https://doi.org/10.1090/mcom/3338
  • MathSciNet review: 3854060