×

An experimental study of approximation algorithms for the joint spectral radius. (English) Zbl 1276.65021

Summary: We describe several approximation algorithms for the joint spectral radius and compare their performance on a large number of test cases. The joint spectral radius of a set \(\Sigma\) of \(n\times n\) matrices is the maximal asymptotic growth rate that can be obtained by forming products of matrices from \(\Sigma\). This quantity is NP-hard to compute and appears in many areas, including in system theory, combinatorics and information theory. A dozen algorithms have been proposed this last decade for approximating the joint spectral radius but little is known about their practical efficiency. We overview these approximation algorithms and classify them in three categories: approximation obtained by examining long products, by building a specific matrix norm, and by using optimization-based techniques. All these algorithms are now implemented in a (freely available) MATLAB toolbox that was released in 2011. This toolbox allows us to present a comparison of the approximations obtained on a large number of test cases as well as on sets of matrices taken from the literature. Finally, in our comparison we include a method, available in the toolbox, that combines different existing algorithms and that is the toolbox’s default method. This default method is able to find optimal products for all test cases of dimension less than four.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
65F35 Numerical computation of matrix norms, conditioning, scaling
15A30 Algebraic systems of matrices
93C05 Linear systems in control theory

Software:

JSR; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berger, M.A., Wang, Y.: Bounded semi-groups of matrices. Linear Algebra Appl. 166, 21-27 (1992). · Zbl 0818.15006
[2] Blondel, V.D., Nesterov, Y.: Computationally efficient approximations of the joint spectral radius. SIAM J. Matrix Anal. Appl. 27(1), 256-272 (2005). · Zbl 1089.65031
[3] Blondel, V.D., Nesterov, Y., Theys, J.: On the accuracy of the ellipsoid norm approximation of the joint spectral radius. Linear Algebra Appl. 394(1), 91-107 (2005). · Zbl 1086.15020
[4] Blondel, V.D., Theys, J., Vladimirov, A.A.: An elementary counterexample to the finiteness conjecture. SIAM J. Matrix Anal. Appl. 24(4), 963-970 (2003). · Zbl 1043.15007
[5] Bousch, T., Mairesse, J.: Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture. J. AMS 15(1), 77-111 (2002). · Zbl 1057.49007
[6] Chang, CT; Blondel, VD, Approximating the joint spectral radius using a genetic algorithm framework, 8681-8686 (2011), Italy
[7] Cicone, A., Guglielmi, N., Serra-Capizzano, S., Zennaro, M.: Finiteness property of pairs of 2×2 sign-matrices via real extremal polytope norms. Linear Algebra Appl. 432(2-3), 796-816 (2010). · Zbl 1186.15006
[8] Daubechies, I., Lagarias, J.C.: Two-scale difference equations II. Local regularity, infinite products of matrices and fractals. SIAM J. Math. Anal. 23(4), 1031-1079 (1992). · Zbl 0788.42013
[9] Gripenberg, G.: Computing the joint spectral radius. Linear Algebra Appl. 234, 43-60 (1996). · Zbl 0863.65017
[10] Guglielmi, N., Zennaro, M.: Balanced complex polytopes and related vector and matrix norms. J. Convex Anal. 14, 729-766 (2007). · Zbl 1128.52010
[11] Guglielmi, N.: Finding extremal complex polytope norms for families of real matrices. SIAM J. Matrix Anal. Appl. 31(2), 602-620 (2009). · Zbl 1197.93129
[12] Gurvits, L.: Stability of discrete linear inclusion. Linear Algebra Appl. 231, 47-85 (1995). · Zbl 0845.68067
[13] Hare, K.G., Morris, I.D., Sidorov, N., Theys, J.: An explicit counterexample to the Lagarias-Wang finiteness conjecture. Adv. Math. 226(6), 4667-4701 (2011). · Zbl 1218.15005
[14] Jungers, R.M.: The Joint Spectral Radius: Theory and Applications. Springer-Verlag, Berlin, Germany (2009)
[15] Jungers, R.M., Protasov, V.Y., Blondel, V.D.: Overlap-free words and spectra of matrices. Theor. Comp. Sci. 410(38), 3670-3684 (2009). · Zbl 1171.68035
[16] Knuth, D.E.: The Art of Computer Programming, Volume 2, Seminumerical Algorithms. Addison-Wesley, Reading, MA (1997) · Zbl 0883.68015
[17] Kozyakin, V.S.: Proof of a Counterexample to the Finiteness Conjecture in the Spirit of the Theory of Dynamical Systems. Preprint 1005. Weierstraß-Institut f¨ur Angewandte Analysis und Stochastik, Berlin (2005)
[18] Kozyakin, V.S.: Structure of extremal trajectories of discrete linear systems and the finiteness conjecture. Autom. Remote Control 68(1), 174-209 (2007). · Zbl 1195.93082
[19] Kozyakin, V.S.: On accuracy of approximation of the spectral radius by the Gelfand formula. Linear Algebra Appl. 431(11), 2134-2141 (2009). · Zbl 1177.15012
[20] Kozyakin, V.S.: A relaxation scheme for computation of the joint spectral radius of matrix sets. J. Diff. Equ. Appl. 17(2), 185-201 (2011) · Zbl 1214.65015
[21] Kozyakin, V.S.: Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete Continuous Dyn. Syst., Ser. B 14(1), 143-158 (2010). · Zbl 1201.65067
[22] Lagarias, J.C., Wang, Y.: The finiteness conjecture for the generalized spectral radius of a set of matrices. Linear Algebra Appl. 214, 17-42 (1995). · Zbl 0818.15007
[23] Maesumi, M.: An efficient lower bound for the generalized spectral radius of a set of matrices. Linear Algebra Appl. 240, 1-7 (1996). · Zbl 0848.15017
[24] Maesumi, M.: Calculating joint spectral radius of matrices and H¨older exponent of wavelets. Approx. Theory IX 2, 1-8 (1998). · Zbl 0916.42026
[25] Moision, B.E., Orlitsky, A., Siegel, P.H.: On codes that avoid specified differences. IEEE Trans. Inf. Theory 47(1), 433-442 (2001). · Zbl 0998.94563
[26] Parrilo, P.A.: Jadbabaie, A.: Approximation of the joint spectral radius using sum of squares. Linear Algebra Appl 428(10), 2385-2402 (2008). · Zbl 1151.65032
[27] Protasov, V.Y.: The joint spectral radius and invariant sets of linear operators. Fundam. Prikl. Mat. 2(1), 205-231 (1996). · Zbl 0899.47002
[28] Protasov, V.Y., Jungers, R.M.: Joint spectral characteristics of matrices: a conic programming approach. SIAM J. Matrix. Anal. Appl. 31(4), 2146-2162 (2010). · Zbl 1203.65093
[29] Rota, G.C., Strang, G.: A note on the joint spectral radius. Indag. Math. 22, 379-381 (1960). · Zbl 0095.09701
[30] Shorten, R., Wirth, F., Mason, O., Wulff, K., King, C.: Stability criteria for switched and hybrid systems. SIAM Review 49(4), 545-592 (2007). · Zbl 1127.93005
[31] Tsitsiklis, J.N., Blondel, V.D.: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate. Math. Cont. Sign. Syst. 10(1), 31-40 (1997). · Zbl 0888.65044
[32] Vankeerbergen, G., Hendrickx, J., Jungers, R., Chang, C.T., Blondel, V.: The JSR Toolbox. MATLAB®Central. [Software, MATLAB® toolbox]. Files available at http://www.mathworks.com/matlabcentral/fileexchange/33202-the-jsr-toolbox (2011)
[33] Wirth, F.: The generalized spectral radius and extremal norms. Linear Algebra Appl. 342(1), 17-40 (2002). · Zbl 0996.15020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.