What is and how to compute efficiently the Markovian Joint Spectral Radius?

Applied and Computational Mathematics Seminar
Monday, April 20, 2015 - 15:05
1 hour (actually 50 minutes)
Skiles 005
L'Aquila, Italy
Given a finite set of matrices F, the Markovian Joint Spectral Radius represents the maximal rate of growth of products of matrices in F when the matrices are multiplied each other following some Markovian law. This quantity is important, for instance, in the study of the so called zero stability of variable stepsize BDF methods for the numerical integration of ordinary differential equations. Recently Kozyakin, based on a work by Dai, showed that, given a set F of N matrices of dimension d and a graph G, which represents the admissible products, it is possibile to compute the Markovian Joint Spectral Radius of the couple (F,G) as the classical Joint Spectral Radius of a new set of N matrices of dimension N*d, which are produced as a particular lifting of the matrices in F. Clearly by this approach the exact evaluation or the simple approximation of the Markovian Joint Spectral Radius becomes a challenge even for reasonably small values of N and d. In this talk we briefly review the theory of the Joint Spectral Radius, and we introduce the Markovian Joint Spectral Radius. Furthermore we address the question whether it is possible to reduce the exact calculation computational complexity of the Markovian Joint Spectral Radius. We show that the problem can be recast as the computation of N polytope norms in dimension d. We conclude the presentation with some numerical examples. This talk is based on a joint work with Nicola Guglielmi from the University of L'Aquila, Italy, and Vladimir Yu. Protasov from the Moscow State University, Russia.