The problem of computing the joint spectral radius (JSR) [RS1960]
of several matrices plays an exceptional role
e.g. in the theory of refinable surfaces, subdivision schemes and wavelets.
In particular, the JSR characterizes the
smoothness of refinable curves and surfaces and the convergence of subdivision schemes. However, the problem
of the JSR`s computation is notoriously hard.
Currently there exist only two algorithms which can compute the joint spectral radius exactly,
the invariant polytope algorithm [GP2013,GP2016,Mej2020,MP2022]
and the finite expressible tree algorithm [MR2014].
The former tries to construct an invariant norm for all matrices,
the latter constructs an infinite tree of matrices whose branches are all multiplicatively bounded.

In this talk we compare these two algorithms,
show that they can handle different classes of examples
and construct a new algorithm combining both ideas
which converges in all cases when one of aforementioned algorithms does.
The efficiency of the new algorithm is illustrated with various examples.
In particular, we prove the finiteness conjecture [LW1995,CCGZ2010] for
all pairs of binary 3 times 3 matrices,
and are able to compute the joint spectral radius of
random matrices of dimension 25 in reasonable time.

Joint work with:
Ulrich Reif, Technical University Darmstadt, Germany;
Vladimir Yu. Protasov, Lomonosov Moscow State University, Russia.

[RS1960] G. C. Rota, G. Strang, A note on the joint spectral radius, Kon. Nederl. Acad. Wet. Proc. 63 (60), doi: 10.1016/S1385-7258(60)50046-1.

[GP2013] N. Guglielmi, V. Yu. Protasov, Exact computation of joint spectral characteristics of linear operators, Found. Comput. Math., 13 (2013) 1, 37–39, doi: 10.1007/s10208-012-9121-0.

[GP2016] N. Guglielmi, V. Yu. Protasov, Invariant polytopes of sets of matrices with applications to regularity of wavelets and subdivisions, SIAM J. Matr. Anal. Appl., 37 (2016) 1, 18–52, doi: 10.1137/15M1006945.

[Mej2020] T. Mejstrik, Improved invariant polytope algorithm and applications, ACM Trans. Math. Softw., 46 (2020) 3 (29), 1–26, doi: 10.1145/3408891.

[MP2022] T. Mejstrik, V. Yu. Protasov, Elliptic polytopes and Lyapunov norms of linear operators, SIMAX, under review, arXiv: https://arxiv.org/abs/2107.02610.

[MR2014] C. Möller, U. Reif, A tree-based approach to joint spectral radius determination, Linear Alg. Appl., 463 (2014), 154–170, doi: 10.1016/j.laa.2014.08.009.

[LW1995] J. C. Lagarias, Y. Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices, Lin. Alg. Appl., 214 (1995), 17–42. doi: 10.1016/0024-3795(93)00052-2.

[CCGZ2010] St. S. Capizzano, A. Cicone, N. Guglielmi, M. Zennaro, Finiteness property of pairs of 2 × 2 sign-matrices via real extremal polytope norm, Linear Algebra Appl., 432 (2010) 01, 796–816, doi: 10.1016/j.laa.2009.09.022