Algorithm 1011: Improved Invariant Polytope Algorithm and Applications

摘要

In several papers of 2013-2016, Guglielmi and Protasov made a breakthrough in the problem of the joint spectral radius computation, developing the invariant polytope algorithm that for most matrix families finds the exact value of the joint spectral radius. This algorithm found many applications in problems of functional analysis, approximation theory, combinatorics, and so on. In this article, we propose a modification of the invariant polytope algorithm making it roughly 3 times faster (single threaded), suitable for higher dimensions, and parallelise it. The modified version works for most matrix families of dimensions up to 25, for non-negative matrices up to 3,000. In addition, we introduce a new, fast algorithm, called modified Gripen-berg algorithm, for computing good lower bounds for the joint spectral radius. The corresponding examples and statistics of numerical results are provided. Several applications of our algorithms are presented. In particular, we find the exact values of the regularity exponents of Daubechies wavelets up to order 42 and the capacities of codes that avoid certain difference patterns.