Tropical scaling of polynomial matrices
From MaRDI portal
Abstract: The eigenvalues of a matrix polynomial can be determined classically by solving a generalized eigenproblem for a linearized matrix pencil, for instance by writing the matrix polynomial in companion form. We introduce a general scaling technique, based on tropical algebra, which applies in particular to this companion form. This scaling, which is inspired by an earlier work of Akian, Bapat, and Gaubert, relies on the computation of "tropical roots". We give explicit bounds, in a typical case, indicating that these roots provide accurate estimates of the order of magnitude of the different eigenvalues, and we show by experiments that this scaling improves the accuracy (measured by normwise backward error) of the computations, particularly in situations in which the data have various orders of magnitude. In the case of quadratic polynomial matrices, we recover in this way a scaling due to Fan, Lin, and Van Dooren, which coincides with the tropical scaling when the two tropical roots are equal. If not, the eigenvalues generally split in two groups, and the tropical method leads to making one specific scaling for each of the groups.
Recommendations
- Tropical roots as approximations to eigenvalues of matrix polynomials
- Polynomial eigenvalue solver based on tropically scaled Lagrange linearization
- Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots
- Optimal Scaling of Generalized and Polynomial Eigenvalue Problems
- Scaling of general quadratic matrix equations
Cited in
(29)- Log-majorization of the moduli of the eigenvalues of a matrix polynomial by tropical roots
- On the backward error incurred by the compact rational Krylov linearization
- Polynomial eigenvalue solver based on tropically scaled Lagrange linearization
- Backward error measures for roots of polynomials
- Min-max elementwise backward error for roots of polynomials and a corresponding backward stable root finder
- On the conditioning for heavily damped quadratic eigenvalue problem solved by linearizations
- A multiscale semi-smooth Newton method for optimal transport
- Tropical bounds for eigenvalues of matrices
- Non-archimedean valuations of eigenvalues of matrix polynomials
- On a class of matrix pencils and -ifications equivalent to a given matrix polynomial
- A Padé approximate linearization algorithm for solving the quadratic eigenvalue problem with low-rank damping
- Dependence of supertropical eigenspaces
- Improving the numerical stability of the Sakurai-Sugiura method for quadratic eigenvalue problems
- A Max-Plus Approach to Incomplete Cholesky Factorization Preconditioners
- Scaling algorithms for unbalanced optimal transport problems
- Backward error of polynomial eigenvalue problems solved by linearization of Lagrange interpolants
- Generalized spectral radius and its max algebra version
- Bounds on the generalized and the joint spectral radius of Hadamard products of bounded sets of positive operators on sequence spaces
- Incomplete LU preconditioner based on max-plus approximation of LU factorization
- Max-Plus Algebraic Statistical Leverage Scores
- Tropical Vandermonde matrices
- The tropical scaling for the polynomial eigenvalue problem solved by a contour integral method
- Tropical roots as approximations to eigenvalues of matrix polynomials
- On some aspects of spectral theory for infinite bounded non-negative matrices in max algebra
- Eigenvalue methods for sparse tropical polynomial systems
- Solving the quadratic eigenvalue problem expressed in non-monomial bases by the tropical scaling
- Global bounds of backward errors of polynomial eigenvalue problem solved by a companion linearization
- Tropical Laurent series, their tropical roots, and localization results for the eigenvalues of nonlinear matrix functions
- On the spectrum in max algebra
This page was built for publication: Tropical scaling of polynomial matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3407662)
