• Previous Article
    Asymptotic stabilization of continuous-time periodic stochastic systems by feedback control based on periodic discrete-time observations
  • MCRF Home
  • This Issue
  • Next Article
    Boundary null-controllability of semi-discrete coupled parabolic systems in some multi-dimensional geometries
doi: 10.3934/mcrf.2020011

A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices

1. 

INRIA and CMAP, École polytechnique, IP Paris, CNRS, CMAP, Route de Saclay, 91128 Palaiseau, France

2. 

LocalSolver, 36 avenue Hoche, 75008 Paris, France

* Corresponding author: Stéphane Gaubert

Dedicated to Fréderic Bonnans on the occasion of his 60th birthday

Received  August 2018 Revised  November 2019 Published  December 2019

Fund Project: Stéphane Gaubert and Nikolas Stott were partially supported by the ANR projects MALTHY (ANR-13-INSE-0003) and DEMOCRITE (ANR-13-SECU-0007), by the PGMO program of EDF and Fondation Mathématique Jacques Hadamard, and by the "Investissement d'avenir", référence ANR-11-LABX-0056-LMH. S. Gaubert also gratefully acknowledges the support of the Mittag-Leffler institute.

We show that the joint spectral radius of a finite collection of nonnegative matrices can be bounded by the eigenvalue of a non-linear operator. This eigenvalue coincides with the ergodic constant of a risk-sensitive control problem, or of an entropy game, in which the state space consists of all switching sequences of a given length. We show that, by increasing this length, we arrive at a convergent approximation scheme to compute the joint spectral radius. The complexity of this method is exponential in the length of the switching sequences, but it is quite insensitive to the size of the matrices, allowing us to solve very large scale instances (several matrices in dimensions of order 1000 within a minute). An idea of this method is to replace a hierarchy of optimization problems, introduced by Ahmadi, Jungers, Parrilo and Roozbehani, by a hierarchy of nonlinear eigenproblems. To solve the latter eigenproblems, we introduce a projective version of Krasnoselskii-Mann iteration. This method is of independent interest as it applies more generally to the nonlinear eigenproblem for a monotone positively homogeneous map. Here, this method allows for scalability by avoiding the recourse to linear or semidefinite programming techniques.

Citation: Stéphane Gaubert, Nikolas Stott. A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices. Mathematical Control & Related Fields, doi: 10.3934/mcrf.2020011
References:
[1]

A. A. AhmadiR. M. JungersP. A. Parrilo and M. Roozbehani, Joint spectral radius and path-complete graph Lyapunov functions, SIAM J. Control and Optimization, 52 (2014), 687-717.  doi: 10.1137/110855272.  Google Scholar

[2]

M. AkianS. Gaubert and A. Guterman, Tropical polyhedra are equivalent to mean payoff games, International Journal of Algebra and Computation, 22 (2012), 125001, 43 pp.  doi: 10.1142/S0218196711006674.  Google Scholar

[3]

M. AkianS. GaubertJ. Grand-Clément and J. Guillaud, The operator approach to entropy games, Theor. Comp. Sys., 63 (2019), 1089-1130.  doi: 10.1007/s00224-019-09925-z.  Google Scholar

[4]

M. AkianS. Gaubert and A. Hochart, Generic uniqueness of the bias vector of finite stochastic games with perfect information, Journal of Mathematical Analysis and Applications, 457 (2018), 1038-1064.  doi: 10.1016/j.jmaa.2017.07.017.  Google Scholar

[5]

M. Akian, S. Gaubert and R. Nussbaum, A Collatz-Wielandt characterization of the spectral radius of order-preserving homogeneous maps on cones, (2011), arXiv: 1112.5968. Google Scholar

[6]

M. AkianS. Gaubert and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps, Trans. Amer. Math. Soc., 368 (2016), 1271-1320.  doi: 10.1090/S0002-9947-2015-06413-7.  Google Scholar

[7]

V. Anantharam and V. S. Borkar, A variational formula for risk-sensitive reward, arXiv: 1501.00676. Google Scholar

[8]

E. Asarin, J. Cervelle, A. Degorre, C. Dima, F. Horn and V. Kozyakin, Entropy games and matrix multiplication games, 33rd Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, (2016), Art. No. 11, 14 pp.  Google Scholar

[9]

J.-B. Baillon and R. E. Bruck, Optimal rates of asymptotic regularity for averaged nonexpansive mappings, Fixed Point Theory and Applications (Halifax, NS, 1991), World Sci. Publ., River Edge, NJ, (1992), 27–66.  Google Scholar

[10]

N. E. Barabanov, Lyapunov indicator for discrete inclusions. I, Autom. Remote Control, 49 (1988), 152-157.   Google Scholar

[11]

V. D. Blondel and Y. Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices, SIAM J. Matrix Anal., 31 (2009), 865-876.  doi: 10.1137/080723764.  Google Scholar

[12]

O. Bokanowski and H. Zidani, Anti-dissipative schemes for advection and application to Hamilton-Jacobi-Bellman equations, J. Sci. Compt., 30 (2007), 1-33.  doi: 10.1007/s10915-005-9017-0.  Google Scholar

[13]

P. J. Bushell, Hilbert's metric and positive contraction mappings in a banach space, Archive for Rational Mechanics and Analysis, 52 (1973), 330-338.  doi: 10.1007/BF00247467.  Google Scholar

[14]

I. Capuzzo Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming, Appl. Math. Optim., 10 (1983), 367-377.  doi: 10.1007/BF01448394.  Google Scholar

[15]

E. CarliniM. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. Vis. Sci., 7 (2004), 15-29.  doi: 10.1007/s00791-004-0124-5.  Google Scholar

[16]

R. CominettiJ. A. Soto and J. Vaisman, On the rate of convergence of Krasnosel'skii-Mann iterations and their connection with sums of Bernoullis, Israel Journal of Mathematics, 199 (2014), 757-772.  doi: 10.1007/s11856-013-0045-4.  Google Scholar

[17]

M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp., 43 (1894), 1-19.  doi: 10.1090/S0025-5718-1984-0744921-8.  Google Scholar

[18]

M. Edelstein and R. C. O'Brien, Nonexpansive mappings, asymptotic regularity and successive approximations, J. London Math. Soc., 17 (1978), 547-554.  doi: 10.1112/jlms/s2-17.3.547.  Google Scholar

[19]

M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math., 67 (1994), 315-344.  doi: 10.1007/s002110050031.  Google Scholar

[20]

S. FriedlandS. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra and its Applications, 438 (2013), 738-749.  doi: 10.1016/j.laa.2011.02.042.  Google Scholar

[21]

S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356 (2004), 4931-4950.  doi: 10.1090/S0002-9947-04-03470-1.  Google Scholar

[22]

S. Gaubert, W. McEneaney and Z. Qu, Curse of dimensionality reduction in max-plus based approximation methods: Theoretical estimates and improved pruning algorithms, Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, (2011), 1054–1061. doi: 10.1109/CDC.2011.6161386.  Google Scholar

[23]

S. Gaubert and N. Stott, Tropical Kraus maps for optimal control of switched systems, 56th IEEE Conference on Decision and Control, CC 2017, Melbourne, Australia, (2017). doi: 10.1109/CDC.2017.8263839.  Google Scholar

[24]

S. Gaubert and G. Vigeral, A maximin characterization of the escape rate of nonexpansive mappings in metrically convex spaces, Math. Proc. of Cambridge Phil. Soc., 152 (2012), 341-363.  doi: 10.1017/S0305004111000673.  Google Scholar

[25]

N. Guglielmi and V. Protasov, Exact computation of joint spectral characteristics of linear operators, Foundations of Computational Mathematics, 13 (2013), 37-97.  doi: 10.1007/s10208-012-9121-0.  Google Scholar

[26]

N. Guglielmi and M. Zennaro, Stability of linear problems: Joint spectral radius of sets of matrices, Current Challenges in Stability Issues for Numerical Differential Equations, Lecture Notes in Math., Fond. CIME/CIME Found. Subser., Springer, Cham, 2082 (2014), 265-313.  doi: 10.1007/978-3-319-01300-8_5.  Google Scholar

[27]

S. Ishikawa, Fixed points and iteration of a nonexpansive mapping in a Banach space, Proceedings of the American Mathematical Society, 59 (1976), 65-71.  doi: 10.1090/S0002-9939-1976-0412909-X.  Google Scholar

[28]

R. Jungers, Classical results and problems, Springer Berlin Heidelberg, Berlin, Heidelberg, (2009), 23–46. Google Scholar

[29]

R. Jungers, The Joint Spectral Radius. Theory and Applications, Lecture Notes in Control and Information Sciences, 385. Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-95980-9.  Google Scholar

[30]

V. Kozyakin, Iterative building of barabanov norms and computation of the joint spectral radius for matrix sets, Discrete and Continuous Dynamical Systems Series-B, 14 (2010), 143-158.  doi: 10.3934/dcdsb.2010.14.143.  Google Scholar

[31]

M. A. Krasnosel'ski$\mathop {\rm{i}}\limits^ \vee $, Two remarks on the method of successive approximations, Uspekhi Matematicheskikh Nauk, 10 (1955), 123-127.   Google Scholar

[32] B. Lemmens and R. Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge Tracts in Mathematics, 189. Cambridge University Press, Cambridge, 2012.  doi: 10.1017/CBO9781139026079.  Google Scholar
[33]

J. Mallet-Paret and R. D. Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators, Discrete and Continuous Dynamical Systems, 8 (2002), 519-562.  doi: 10.3934/dcds.2002.8.519.  Google Scholar

[34]

W. R. Mann, Mean value methods in iteration, Proceedings of the American Mathematical Society, 4 (1953), 506-510.  doi: 10.1090/S0002-9939-1953-0054846-3.  Google Scholar

[35]

W. M. McEneaney, A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs, SIAM Journal on Control and Optimization, 46 (2007), 1239-1276.  doi: 10.1137/040610830.  Google Scholar

[36]

W. M. McEneaney and L. J. Kluberg, Convergence rate for a curse-of-dimensionality-free method for a class of HJB PDEs, SIAM J. Control Optim., 48 (2009/10), 3052-3079.  doi: 10.1137/070681934.  Google Scholar

[37]

R. D. Nussbaum, Convexity and log convexity for the spectral radius, Linear Algebra Appl., 73 (1986), 59-122.  doi: 10.1016/0024-3795(86)90233-8.  Google Scholar

[38]

R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc., 75 (1988).  doi: 10.1090/memo/0391.  Google Scholar

[39]

A. Papadopoulos and M. Troyanov, Weak Finsler structures and the Funk weak metric, Math. Proc. Cambridge Philos. Soc., 147 (2009), 419-437.  doi: 10.1017/S0305004109002461.  Google Scholar

[40]

M. PhilippeR. EssickG. E. Dullerud and R. M. Jungers, Stability of discrete-time switching systems with constrained switching sequences, Automatica J. IFAC, 72 (2016), 242-250.  doi: 10.1016/j.automatica.2016.05.015.  Google Scholar

[41]

V. Y. Protasov, Spectral simplex method, Mathematical Programming, 156 (2016), 485-511.  doi: 10.1007/s10107-015-0905-2.  Google Scholar

[42]

Z. Qu, Contraction of Riccati flows applied to the convergence analysis of a max-plus curse-of-dimensionality-free method, SIAM Journal on Control and Optimization, 52 (2014), 2677-2706.  doi: 10.1137/130906702.  Google Scholar

[43]

N. Stott, Minimal Upper Bounds in the Löwner Order and Application to Invariant Computation for Switched Systems, Phd thesis, Université Paris-Saclay, École polytechnique, 2017. Google Scholar

show all references

References:
[1]

A. A. AhmadiR. M. JungersP. A. Parrilo and M. Roozbehani, Joint spectral radius and path-complete graph Lyapunov functions, SIAM J. Control and Optimization, 52 (2014), 687-717.  doi: 10.1137/110855272.  Google Scholar

[2]

M. AkianS. Gaubert and A. Guterman, Tropical polyhedra are equivalent to mean payoff games, International Journal of Algebra and Computation, 22 (2012), 125001, 43 pp.  doi: 10.1142/S0218196711006674.  Google Scholar

[3]

M. AkianS. GaubertJ. Grand-Clément and J. Guillaud, The operator approach to entropy games, Theor. Comp. Sys., 63 (2019), 1089-1130.  doi: 10.1007/s00224-019-09925-z.  Google Scholar

[4]

M. AkianS. Gaubert and A. Hochart, Generic uniqueness of the bias vector of finite stochastic games with perfect information, Journal of Mathematical Analysis and Applications, 457 (2018), 1038-1064.  doi: 10.1016/j.jmaa.2017.07.017.  Google Scholar

[5]

M. Akian, S. Gaubert and R. Nussbaum, A Collatz-Wielandt characterization of the spectral radius of order-preserving homogeneous maps on cones, (2011), arXiv: 1112.5968. Google Scholar

[6]

M. AkianS. Gaubert and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps, Trans. Amer. Math. Soc., 368 (2016), 1271-1320.  doi: 10.1090/S0002-9947-2015-06413-7.  Google Scholar

[7]

V. Anantharam and V. S. Borkar, A variational formula for risk-sensitive reward, arXiv: 1501.00676. Google Scholar

[8]

E. Asarin, J. Cervelle, A. Degorre, C. Dima, F. Horn and V. Kozyakin, Entropy games and matrix multiplication games, 33rd Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, (2016), Art. No. 11, 14 pp.  Google Scholar

[9]

J.-B. Baillon and R. E. Bruck, Optimal rates of asymptotic regularity for averaged nonexpansive mappings, Fixed Point Theory and Applications (Halifax, NS, 1991), World Sci. Publ., River Edge, NJ, (1992), 27–66.  Google Scholar

[10]

N. E. Barabanov, Lyapunov indicator for discrete inclusions. I, Autom. Remote Control, 49 (1988), 152-157.   Google Scholar

[11]

V. D. Blondel and Y. Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices, SIAM J. Matrix Anal., 31 (2009), 865-876.  doi: 10.1137/080723764.  Google Scholar

[12]

O. Bokanowski and H. Zidani, Anti-dissipative schemes for advection and application to Hamilton-Jacobi-Bellman equations, J. Sci. Compt., 30 (2007), 1-33.  doi: 10.1007/s10915-005-9017-0.  Google Scholar

[13]

P. J. Bushell, Hilbert's metric and positive contraction mappings in a banach space, Archive for Rational Mechanics and Analysis, 52 (1973), 330-338.  doi: 10.1007/BF00247467.  Google Scholar

[14]

I. Capuzzo Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming, Appl. Math. Optim., 10 (1983), 367-377.  doi: 10.1007/BF01448394.  Google Scholar

[15]

E. CarliniM. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. Vis. Sci., 7 (2004), 15-29.  doi: 10.1007/s00791-004-0124-5.  Google Scholar

[16]

R. CominettiJ. A. Soto and J. Vaisman, On the rate of convergence of Krasnosel'skii-Mann iterations and their connection with sums of Bernoullis, Israel Journal of Mathematics, 199 (2014), 757-772.  doi: 10.1007/s11856-013-0045-4.  Google Scholar

[17]

M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp., 43 (1894), 1-19.  doi: 10.1090/S0025-5718-1984-0744921-8.  Google Scholar

[18]

M. Edelstein and R. C. O'Brien, Nonexpansive mappings, asymptotic regularity and successive approximations, J. London Math. Soc., 17 (1978), 547-554.  doi: 10.1112/jlms/s2-17.3.547.  Google Scholar

[19]

M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math., 67 (1994), 315-344.  doi: 10.1007/s002110050031.  Google Scholar

[20]

S. FriedlandS. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra and its Applications, 438 (2013), 738-749.  doi: 10.1016/j.laa.2011.02.042.  Google Scholar

[21]

S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356 (2004), 4931-4950.  doi: 10.1090/S0002-9947-04-03470-1.  Google Scholar

[22]

S. Gaubert, W. McEneaney and Z. Qu, Curse of dimensionality reduction in max-plus based approximation methods: Theoretical estimates and improved pruning algorithms, Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, (2011), 1054–1061. doi: 10.1109/CDC.2011.6161386.  Google Scholar

[23]

S. Gaubert and N. Stott, Tropical Kraus maps for optimal control of switched systems, 56th IEEE Conference on Decision and Control, CC 2017, Melbourne, Australia, (2017). doi: 10.1109/CDC.2017.8263839.  Google Scholar

[24]

S. Gaubert and G. Vigeral, A maximin characterization of the escape rate of nonexpansive mappings in metrically convex spaces, Math. Proc. of Cambridge Phil. Soc., 152 (2012), 341-363.  doi: 10.1017/S0305004111000673.  Google Scholar

[25]

N. Guglielmi and V. Protasov, Exact computation of joint spectral characteristics of linear operators, Foundations of Computational Mathematics, 13 (2013), 37-97.  doi: 10.1007/s10208-012-9121-0.  Google Scholar

[26]

N. Guglielmi and M. Zennaro, Stability of linear problems: Joint spectral radius of sets of matrices, Current Challenges in Stability Issues for Numerical Differential Equations, Lecture Notes in Math., Fond. CIME/CIME Found. Subser., Springer, Cham, 2082 (2014), 265-313.  doi: 10.1007/978-3-319-01300-8_5.  Google Scholar

[27]

S. Ishikawa, Fixed points and iteration of a nonexpansive mapping in a Banach space, Proceedings of the American Mathematical Society, 59 (1976), 65-71.  doi: 10.1090/S0002-9939-1976-0412909-X.  Google Scholar

[28]

R. Jungers, Classical results and problems, Springer Berlin Heidelberg, Berlin, Heidelberg, (2009), 23–46. Google Scholar

[29]

R. Jungers, The Joint Spectral Radius. Theory and Applications, Lecture Notes in Control and Information Sciences, 385. Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-95980-9.  Google Scholar

[30]

V. Kozyakin, Iterative building of barabanov norms and computation of the joint spectral radius for matrix sets, Discrete and Continuous Dynamical Systems Series-B, 14 (2010), 143-158.  doi: 10.3934/dcdsb.2010.14.143.  Google Scholar

[31]

M. A. Krasnosel'ski$\mathop {\rm{i}}\limits^ \vee $, Two remarks on the method of successive approximations, Uspekhi Matematicheskikh Nauk, 10 (1955), 123-127.   Google Scholar

[32] B. Lemmens and R. Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge Tracts in Mathematics, 189. Cambridge University Press, Cambridge, 2012.  doi: 10.1017/CBO9781139026079.  Google Scholar
[33]

J. Mallet-Paret and R. D. Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators, Discrete and Continuous Dynamical Systems, 8 (2002), 519-562.  doi: 10.3934/dcds.2002.8.519.  Google Scholar

[34]

W. R. Mann, Mean value methods in iteration, Proceedings of the American Mathematical Society, 4 (1953), 506-510.  doi: 10.1090/S0002-9939-1953-0054846-3.  Google Scholar

[35]

W. M. McEneaney, A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs, SIAM Journal on Control and Optimization, 46 (2007), 1239-1276.  doi: 10.1137/040610830.  Google Scholar

[36]

W. M. McEneaney and L. J. Kluberg, Convergence rate for a curse-of-dimensionality-free method for a class of HJB PDEs, SIAM J. Control Optim., 48 (2009/10), 3052-3079.  doi: 10.1137/070681934.  Google Scholar

[37]

R. D. Nussbaum, Convexity and log convexity for the spectral radius, Linear Algebra Appl., 73 (1986), 59-122.  doi: 10.1016/0024-3795(86)90233-8.  Google Scholar

[38]

R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc., 75 (1988).  doi: 10.1090/memo/0391.  Google Scholar

[39]

A. Papadopoulos and M. Troyanov, Weak Finsler structures and the Funk weak metric, Math. Proc. Cambridge Philos. Soc., 147 (2009), 419-437.  doi: 10.1017/S0305004109002461.  Google Scholar

[40]

M. PhilippeR. EssickG. E. Dullerud and R. M. Jungers, Stability of discrete-time switching systems with constrained switching sequences, Automatica J. IFAC, 72 (2016), 242-250.  doi: 10.1016/j.automatica.2016.05.015.  Google Scholar

[41]

V. Y. Protasov, Spectral simplex method, Mathematical Programming, 156 (2016), 485-511.  doi: 10.1007/s10107-015-0905-2.  Google Scholar

[42]

Z. Qu, Contraction of Riccati flows applied to the convergence analysis of a max-plus curse-of-dimensionality-free method, SIAM Journal on Control and Optimization, 52 (2014), 2677-2706.  doi: 10.1137/130906702.  Google Scholar

[43]

N. Stott, Minimal Upper Bounds in the Löwner Order and Application to Invariant Computation for Switched Systems, Phd thesis, Université Paris-Saclay, École polytechnique, 2017. Google Scholar

Table 1.  Convergence of the hierarchy on $ 5 \times 5 $ matrices
Level $ d $ CPU Time (s) Eigenvalue $ \lambda_d $ Relative error
1 $ 0.01 $ $ 2.165 $ $ 6.8 $%
2 $ 0.01 $ $ 2.102 $ $ 3.7 $%
3 $ 0.01 $ $ 2.086 $ $ 2.9 $%
4 $ 0.01 $ $ 2.059 $ $ 1.6 $%
5 $ 0.02 $ $ 2.041 $ $ 0.7 $%
6 $ 0.05 $ $ 2.030 $ $ 0.1 $%
7 $ 0.7 $ $ 2.027 $ $ 0.0 $%
8 $ 0.32 $ $ 2.027 $ $ 0.0 $%
9 $ 1.12 $ $ 2.027 $ $ 0.0 $%
Level $ d $ CPU Time (s) Eigenvalue $ \lambda_d $ Relative error
1 $ 0.01 $ $ 2.165 $ $ 6.8 $%
2 $ 0.01 $ $ 2.102 $ $ 3.7 $%
3 $ 0.01 $ $ 2.086 $ $ 2.9 $%
4 $ 0.01 $ $ 2.059 $ $ 1.6 $%
5 $ 0.02 $ $ 2.041 $ $ 0.7 $%
6 $ 0.05 $ $ 2.030 $ $ 0.1 $%
7 $ 0.7 $ $ 2.027 $ $ 0.0 $%
8 $ 0.32 $ $ 2.027 $ $ 0.0 $%
9 $ 1.12 $ $ 2.027 $ $ 0.0 $%
Table 2.  Computation time for large matrices
Dimension $ n $ Level $ d $ Eigenvalue $ \lambda_d $ CPU Time
$ 10 $ $ 2 $ $ 4.287 $ $ 0.01 $ s
$ 3 $ $ 4.286 $ $ 0.03 $ s
$ 20 $ $ 2 $ $ 8.582 $ $ 0.01 $ s
$ 3 $ $ 8.576 $ $ 0.03 $ s
$ 50 $ $ 2 $ $ 22.34 $ $ 0.04 $ s
$ 3 $ $ 22.33 $ $ 0.16 $ s
$ 100 $ $ 2 $ $ 44.45 $ $ 0.17 $ s
$ 3 $ $ 44.45 $ $ 0.53 $ s
$ 200 $ $ 2 $ $ 89.77 $ $ 0.71 $ s
$ 3 $ $ 89.76 $ $ 2.46 $ s
$ 500 $ $ 2 $ $ 224.88 $ $ 5.45 $ s
$ 3 $ $ 224.88 $ $ 19.7 $ s
$ 1000 $ $ 2 $ $ 449.87 $ $ 44.0 $ s
$ 3 $ $ 449.87 $ $ 2.7 $ min
$ 2000 $ $ 2 $ $ 889.96 $ $ 4.6 $ min
$ 3 $ $ 889.96 $ $ 19.2 $ min
$ 5000 $ $ 2 $ $ 2249.69 $ $ 51.9 $ min
$ 3 $ $ 2249.57 $ $ 3.3 $ h
Dimension $ n $ Level $ d $ Eigenvalue $ \lambda_d $ CPU Time
$ 10 $ $ 2 $ $ 4.287 $ $ 0.01 $ s
$ 3 $ $ 4.286 $ $ 0.03 $ s
$ 20 $ $ 2 $ $ 8.582 $ $ 0.01 $ s
$ 3 $ $ 8.576 $ $ 0.03 $ s
$ 50 $ $ 2 $ $ 22.34 $ $ 0.04 $ s
$ 3 $ $ 22.33 $ $ 0.16 $ s
$ 100 $ $ 2 $ $ 44.45 $ $ 0.17 $ s
$ 3 $ $ 44.45 $ $ 0.53 $ s
$ 200 $ $ 2 $ $ 89.77 $ $ 0.71 $ s
$ 3 $ $ 89.76 $ $ 2.46 $ s
$ 500 $ $ 2 $ $ 224.88 $ $ 5.45 $ s
$ 3 $ $ 224.88 $ $ 19.7 $ s
$ 1000 $ $ 2 $ $ 449.87 $ $ 44.0 $ s
$ 3 $ $ 449.87 $ $ 2.7 $ min
$ 2000 $ $ 2 $ $ 889.96 $ $ 4.6 $ min
$ 3 $ $ 889.96 $ $ 19.2 $ min
$ 5000 $ $ 2 $ $ 2249.69 $ $ 51.9 $ min
$ 3 $ $ 2249.57 $ $ 3.3 $ h
[1]

Marianne Akian, Stéphane Gaubert, Antoine Hochart. A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 207-231. doi: 10.3934/dcds.2020009

[2]

Jiu Ding, Noah H. Rhee. A unified maximum entropy method via spline functions for Frobenius-Perron operators. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 235-245. doi: 10.3934/naco.2013.3.235

[3]

Stefan Klus, Péter Koltai, Christof Schütte. On the numerical approximation of the Perron-Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (1) : 51-79. doi: 10.3934/jcd.2016003

[4]

Victor Kozyakin. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 143-158. doi: 10.3934/dcdsb.2010.14.143

[5]

Martin Lustig, Caglar Uyanik. Perron-Frobenius theory and frequency convergence for reducible substitutions. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 355-385. doi: 10.3934/dcds.2017015

[6]

Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457

[7]

Chaoqian Li, Yaqiang Wang, Jieyi Yi, Yaotang Li. Bounds for the spectral radius of nonnegative tensors. Journal of Industrial & Management Optimization, 2016, 12 (3) : 975-990. doi: 10.3934/jimo.2016.12.975

[8]

Xiongping Dai, Yu Huang, Mingqing Xiao. Realization of joint spectral radius via Ergodic theory. Electronic Research Announcements, 2011, 18: 22-30. doi: 10.3934/era.2011.18.22

[9]

Victor Kozyakin. Minimax joint spectral radius and stabilizability of discrete-time linear switching control systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3537-3556. doi: 10.3934/dcdsb.2018277

[10]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2020013

[11]

Yu-Feng Sun, Zheng Zeng, Jie Song. Quasilinear iterative method for the boundary value problem of nonlinear fractional differential equation. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019045

[12]

Qun Lin, Ryan Loxton, Kok Lay Teo. The control parameterization method for nonlinear optimal control: A survey. Journal of Industrial & Management Optimization, 2014, 10 (1) : 275-309. doi: 10.3934/jimo.2014.10.275

[13]

Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201

[14]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117

[15]

Pierre Lissy. Construction of gevrey functions with compact support using the bray-mandelbrojt iterative process and applications to the moment method in control theory. Mathematical Control & Related Fields, 2017, 7 (1) : 21-40. doi: 10.3934/mcrf.2017002

[16]

Miao Yu, Haoyang Lu, Weipeng Shang. A new iterative identification method for damping control of power system in multi-interference. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020104

[17]

Morten Brøns. An iterative method for the canard explosion in general planar systems. Conference Publications, 2013, 2013 (special) : 77-83. doi: 10.3934/proc.2013.2013.77

[18]

Janusz Mierczyński. Averaging in random systems of nonnegative matrices. Conference Publications, 2015, 2015 (special) : 835-840. doi: 10.3934/proc.2015.0835

[19]

Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855

[20]

Tahereh Salimi Siahkolaei, Davod Khojasteh Salkuyeh. A preconditioned SSOR iteration method for solving complex symmetric system of linear equations. Numerical Algebra, Control & Optimization, 2019, 9 (4) : 483-492. doi: 10.3934/naco.2019033

2018 Impact Factor: 1.292

Metrics

  • PDF downloads (25)
  • HTML views (136)
  • Cited by (0)

Other articles
by authors

[Back to Top]