On the complexity of detecting positive eigenvectors of nonlinear cone maps

DOI10.2140/INVOLVE.2019.12.141MaRDI QIDQ1639628zbMATH OpenOpenAlexFDO

Authors Bas Lemmens, Lewis White

Publication date 13 June 2018

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.08658, https://kar.kent.ac.uk/64390/1/Lemmens_White_v1.pdf

zbMATH Keywords

Hilbert's metricillumination problempositive eigenvectorsnonlinear maps on cones

Mathematics Subject Classification ID

Iterative procedures involving nonlinear operators (47J25) Monotone and positive operators on ordered Banach spaces or other ordered topological vector spaces (47H07) Nonlinear spectral theory, nonlinear eigenvalue problems (47J10)

Abstract: In recent work with Lins and Nussbaum the first author gave an algorithm that can detect the existence of a positive eigenvector for order-preserving homogeneous maps on the standard positive cone. The main goal of this paper is to determine the minimum number of iterations this algorithm requires. It is known that this number is equal to the illumination number of the unit ball of the variation norm. In this paper we determine its illumination number, and hence provide a sharp lower bound for the running time of the algorithm.

Recommendations

• Dynamics of piecewise linear maps and sets of nonnegative matrices
• An origin displacement method for calculating maximum eigenvalue of nonnegative matrix under diagonal similarity transformation
• An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials
• The smoothing method for finding the largest eigenvalue of nonnegative matrices
• Computational geometry of positive definiteness
• On the nonnegative eigenvalue problem
• A homotopy method for computing the largest eigenvalue of an irreducible nonnegative tensor
• Algorithms and merit functions for the principal eigenvalue.
• On the range of eigenvalues of an interval matrix
• An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor

Cites work

• An operator approach to zero-sum repeated games
• Equivalence of communication and projective boundedness properties for monotone and homogeneous functions
• Finsler structures for the part metric and Hilbert's projective metric and applications to ordinary differential equations
• Hilbert’s projective metric and iterated nonlinear maps
• Iterated nonlinear maps and Hilbert’s projective metric. II
• Nonlinear Perron-Frobenius theory
• The Asymptotic Theory of Stochastic Games
• The Perron-Frobenius theorem for homogeneous, monotone functions
• The two-sex multiethnic stable population model

Cited in

(2)

• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• Continuous extension of order-preserving homogeneous maps.

This page was built for publication: On the complexity of detecting positive eigenvectors of nonlinear cone maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1639628)