Author:

Keywords:

polynomial eigenvalue problem, linearization, tropical scaling, well-separated tropical roots, block companion linearization, Lagrange-type linearization, Science & Technology, Physical Sciences, Mathematics, Applied, Mathematics, Polynomial eigenvalue problem, Linearization, Tropical scaling, Well-separated tropical roots, Block companion linearization, BACKWARD ERROR, MATRIX POLYNOMIALS, ROOTS, 01 Mathematical Sciences, 08 Information and Computing Sciences, 09 Engineering, Numerical & Computational Mathematics, 40 Engineering, 49 Mathematical sciences

Abstract:

We propose an algorithm to solve polynomial eigenvalue problems via linearization combining several ingredients: a specific choice of linearization, which is constructed using input from tropical algebra and the notion of well-separated tropical roots, an appropriate scaling applied to the linearization and a modified stopping criterion for the $QZ$ iterations that takes advantage of the properties of our scaled linearization. Numerical experiments suggest that our polynomial eigensolver computes all the finite and well-conditioned eigenvalues to high relative accuracy even when they are very different in magnitude.