Tropical methods for the localization of eigenvalues and application to their numerical computation

Andrea Marchesini 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
Inria Saclay - Ile de France, CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
Abstract : In this thesis we use tropical mathematics to locate and numerically compute eigenvalues of matrices and matrix polynomials. The first part of the work focuses on eigenvalues of matrices, while the second part focuses on matrix polynomials and adds a numerical experimental side along the theoretical one. By “locating” an eigenvalue we mean being able to identify some bounds within which it must lie. This can be useful in situations where one only needs approximate eigenvalues; moreover, they make good starting values for iterative eigenvalue-finding algorithms. Rather than full location, our result for matrices is in the form of majorization bounds to control the absolute value of the eigenvalues. These bounds are to some extent a generalization to matrices of a result proved by Ostrowski for polynomials: he showed (albeit with different terminology) that the product of the k largest absolute values of the roots of a polynomial can be bounded from above and below by the product of its k largest tropical (max-times) roots, up to multiplicative factors which are independent of the coefficients of the polynomial. We prove an analogous result for matrices: the product of the k largest absolute values of eigenvalues is bounded, up to a multiplicative factor, by the product of the k largest tropical eigenvalues. It should be noted that tropical eigenvalues can be computed by using the solution to a parametric optimal assignment problem, in a way that is robust with respect to small perturbations in the data. Another thing worth mentioning is that the multiplicative factor in the bound is of combinatorial nature and it is reminiscent of a work by Friedland, who essentially proved a specialization of our result to the particular case k = 1 (i.e. for the largest eigenvalue only). We can interpret the absolute value as an archimedean valuation; in this light, there is a correspondence between the present result and previous work by Akian, Bapat and Gaubert, who dealt with the same problem for matrices over fields with non- archimedean valuation (specifically Puiseux series, with the leading exponent as valuation) and showed in that case more stringent bounds, with no multiplicative factor, and with generic equality rather than upper and lower bounds. The second part of the thesis revolves around the computation of eigenvalues of matrix polynomials. For linear matrix polynomials, stable algorithms such as the QZ method have been known for a long time. Eigenproblems for matrix polynomials of higher degree are usually reduced to the linear case, using a linearization such as the companion linearization. This however can worsen the condition number and backward error of the computed eigenvalue with respect to perturbations in the coefficients of the original polynomial (even if they remain stable in the coefficients of the linearized). To mitigate this inconvenience it is common to perform a scaling of the matrix polynomial before linearizing. Various scaling methods have been proposed. In our work, we introduce a two-sided diagonal scaling strategy based on the tropical eigenvalues of the matrix polynomial obtained by taking entrywise valuation of the original one (and we will consider both the archimedean and non-archimedean case). We study the effect of this scaling on the conditioning and backward error, with both analytic formulas and numerical examples, showing that it can increase the accuracy of the computed eigenvalues by several orders of magnitude.
Document type :
Theses
Complete list of metadatas

Cited literature [49 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01285110
Contributor : Andrea Marchesini <>
Submitted on : Tuesday, March 8, 2016 - 3:58:24 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:31 PM
Long-term archiving on: Sunday, November 13, 2016 - 11:53:46 AM

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

  • HAL Id : tel-01285110, version 1

Citation

Andrea Marchesini. Tropical methods for the localization of eigenvalues and application to their numerical computation. Spectral Theory [math.SP]. Ecole polytechnique X, 2015. English. ⟨tel-01285110⟩

Share

Metrics

Record views

494

Files downloads

650