Research Repository

Tropical Roots as Approximations to Eigenvalues of Matrix Polynomials

Noferini, Vanni and Sharify, Meisam and Tisseur, Françoise (2015) 'Tropical Roots as Approximations to Eigenvalues of Matrix Polynomials.' SIAM Journal on Matrix Analysis and Applications, 36 (1). pp. 138-157. ISSN 0895-4798

14096637x.pdf - Published Version
Available under License Creative Commons Attribution.

Download (412kB) | Preview


The tropical roots of txp(x) = max0≤ i≤ℓ ∥Ai∥xi are points at which the maximum is attained for at least two values of i for some x. These roots, which can be computed in only O (ℓ) operations, can be good approximations to the moduli of the eigenvalues of the matrix polynomial P (λ) = Σi=0ℓ λi Ai, in particular when the norms of the matrices Ai vary widely. Our aim is to investigate this observation and its applications. We start by providing annuli defined in terms of the tropical roots of txp (x) that contain the eigenvalues of P (λ). Our localization results yield conditions under which tropical roots offer order of magnitude approximations to the moduli of the eigenvalues of P (λ). Our tropical localization of eigenvalues is less tight than eigenvalue localization results derived from a generalized matrix version of Pellet's theorem but they are easier to interpret. Tropical roots are already used to determine the starting points for matrix polynomial eigensolvers based on scalar polynomial root solvers such as the Ehrlich-Aberth method and our results further justify this choice. Our results provide the basis for analyzing the effect of Gaubert and Sharify's tropical scalings for P (λ) on (a) the conditioning of linearizations of tropically scaled P (λ) and (b) the backward stability of eigensolvers based on linearizations of tropically scaled P (λ). We anticipate that the tropical roots of txp(x), on which the tropical scalings are based will help designing polynomial eigensolvers with better numerical properties than standard algorithms for polynomial eigenvalue problems such as that implemented in the MATLAB function polyeig.

Item Type: Article
Uncontrolled Keywords: polynomial eigenvalue problem; matrix polynomial; tropical algebra; localization of eigenvalues; Rouche's theorem; Pellet's theorem; Newton's polygon; tropical scaling
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 20 Oct 2015 13:38
Last Modified: 15 Jan 2022 00:46

Actions (login required)

View Item View Item