A New Strategy for Exact Determination of the Joint Spectral Radius

Computing the joint spectral radius of a finite matrix family is, though interesting for many applications, a difficult problem. This work proposes a method for determining the exact value which is based on graph-theoretical ideas. In contrast to some other algorithms in the literature, the purpose of the approach is not to find an extremal norm for the matrix family. To validate that the finiteness property (FP) is satisfied for a certain matrix product, a tree is to be analyzed whose nodes code sets of matrix products. A sufficient, and in certain situations also necessary, criterion is given by existence of a finite tree with special properties, and an algorithm for searching such a tree is proposed. The suggested method applies in case of several FP-products as well and is not limited to asymptotically simple matrix families. In the smoothness analysis of subdivision schemes, joint spectral radius determination is crucial to detect Hölder regularity. The palindromic symmetry of matrices, which results from symmetric binary subdivision, is considered in the context of set-valued trees. Several illustrating examples explore the capabilities of the approach, consolidated by examples from subdivision.

Die Berechnung des gemeinsamen Spektralradius (joint spectral radius) einer endlichen Matrixfamilie ist, obgleich für viele Anwendungen interessant, ein schwieriges Problem. Diese Arbeit schlägt eine Methode zur Bestimmung des exakten Wertes vor, die auf graphentheoretischen Ideen basiert. Im Gegensatz zu einigen anderen Algorithmen aus der Literatur zielt dieser Ansatz nicht darauf ab, eine Extremalnorm zu finden. Um zu bestätigen, dass die Endlichkeitseigenschaft (finiteness property, kurz: FP) von einem gewissen Matrixprodukt erfüllt wird, wird ein Baum analysiert, dessen Knoten Mengen von Matrixprodukten kodieren. Eine hinreichende und in gewissen Situationen auch notwendige Bedingung ist durch Existenz eines endlichen Baumes mit speziellen Eigenschaften gegeben, und ein Algorithmus für die Suche nach einem solchen Baum wird präsentiert. Die dargestellte Methode gilt auch im Falle von mehreren FP-Produkten und ist nicht auf asymptotisch einfache Familien beschränkt. Im Rahmen der Glattheitsanalyse von Subdivisionschemata ist die Bestimmung des gemeinsamen Spektralradius äußerst wichtig, um die Hölder-Regularität zu ermitteln. Die palindromische Symmetrie von Matrizen, die aus symmetrischer binärer Subdivision resultieren, wird im Kontext der mengenwertigen Bäume betrachtet. Mit mehreren illustrierenden Beispielen werden die Möglichkeiten des Ansatzes erkundet und durch Beispiele der Subdivision ergänzt.