On the complexity of detecting positive eigenvectors of nonlinear cone maps

DOI10.2140/INVOLVE.2019.12.141zbMATH Open1420.47021arXiv1811.08658OpenAlexW3122413162MaRDI QIDQ1639628FDOQ1639628

Lewis White, Bas Lemmens

Publication date: 13 June 2018

Published in: Involve (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1811.08658

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

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)

Cites Work

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

Cited In (1)

• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$

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)