2014, 4(1): 75-91. doi: 10.3934/naco.2014.4.75

An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials

1. 

Department of Mathematics and Statistics, Curtin University, Bentley, WA, Australia

Received  February 2013 Revised  November 2013 Published  December 2013

In this paper, we propose an iterative method for calculating the largest eigenvalue of nonhomogeneous nonnegative polynomials. This method is a generalization of the method in [19]. We also prove this method is convergent for irreducible nonhomogeneous nonnegative polynomials.
Citation: Nur Fadhilah Ibrahim. An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 75-91. doi: 10.3934/naco.2014.4.75
References:
[1]

M. Akian, S. Gaubert and A. Guterman, Tropical polyhedra are equivalent to mean payoff games,, , ().   Google Scholar

[2]

F. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat, Synchronization and Linearity,, Wiley Series in Probability and Mathematical Statistics, (1992).   Google Scholar

[3]

L. Baratchart, M. Berthod and L. Pottier, Optimization of positive generalized polynomials under lpconstraints, Journal of Convex Analysis, 5 (1998), 353.   Google Scholar

[4]

L. Bloy and R. Verma, On computing the underlying fiber directions from the diffusion orientation distribution function,, Medical Image Computing and Computer-Assisted Intervention MICCAI, (2008), 1.   Google Scholar

[5]

L. Collatz, Einschliessungssatz für die charakteristischen Zahlen von Matrizen,, Math. Zeit., 48 (1942), 221.   Google Scholar

[6]

K. C. Chang, K. J. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors,, Commun. Math. Sci., 6 (2008), 507.   Google Scholar

[7]

K. C. Chang, K. J. Pearson and T. Zhang, Primitivity, the convergence of the NQZ method and the largest eigenvalue for nonnegative tensors,, SIAM J. Matrix Anal. Appl., 32 (2011), 806.  doi: 10.1137/100807120.  Google Scholar

[8]

K. Chang, L. Qi and G. Zhou, Singular values of a real rectangular tensor,, Journal of Mathematical Analysis and Applications, 370 (2010), 284.  doi: 10.1016/j.jmaa.2010.04.037.  Google Scholar

[9]

L. De Lathauwer, B. De Moor and J. Vandewalle, On the best rank-1 and rank- (R1, ...,Rn) approximation of higher-order tensors,, SIAM J. Matrix Anal. Appl., 21 (2000), 1324.   Google Scholar

[10]

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

[11]

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

[12]

J. Gunawardena, From max-plus algebra to nonexpansive maps: a nonlinear theory for discrete event systems,, Theoritical Computer Science, 293 (2003), 141.  doi: 10.1016/S0304-3975(02)00235-9.  Google Scholar

[13]

J. Gunawardena (editor), Idempotency,, Publications of the Isaac Newton Institute, (1998).  doi: 10.1017/CBO9780511662508.  Google Scholar

[14]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications,, SIAM Rev., 51 (2009), 455.  doi: 10.1137/07070111X.  Google Scholar

[15]

V. N. Kolokoltsov, Nonexpansive maps and option pricing theory,, Kybernetika, 34 (1998), 713.   Google Scholar

[16]

V. N. Kolokoltsov and V. P. Maslov, Idempotency Analysis and Applications,, Kluwer Academic, (1997).   Google Scholar

[17]

L. H. Lim, Multilinear pagerank: measuring higher order connectivity in linked objects,, The Internet: Today and Tomorrow, (2005).   Google Scholar

[18]

Y. Liu, G. Zhou and N. F. Ibrahim, An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor,, Journal of Computational and Applied Mathematics, 235 (2010), 286.  doi: 10.1016/j.cam.2010.06.002.  Google Scholar

[19]

M. Ng, L. Qi and G. Zhou, Finding the largest eigenvalue of a nonnegative tensor,, SIAM J. Matrix Anal. Appl., 31 (2009), 1090.  doi: 10.1137/09074838X.  Google Scholar

[20]

Q. Ni, L. Qi and F. Wang, An eigenvalue method for testing the positive definiteness of a multivariate form,, IEEE Transactions on Automatic Control, 53 (2008), 1096.  doi: 10.1109/TAC.2008.923679.  Google Scholar

[21]

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

[22]

R. D. Nussbaum, Iterated nonlinear map and Hilbert's projective metric, II,, Memoirs of the AMS, 79 (1989).  doi: 10.1090/memo/0401.  Google Scholar

[23]

M. Morishima, Equilibrium, Stability and Growth,, Clarenson, (2002).   Google Scholar

[24]

L. Qi, F. Wang and Y. Wang, Z-eigenvalue methods for a global polynomial optimization problem,, Mathematical Programming, 118 (2009), 301.  doi: 10.1007/s10107-007-0193-6.  Google Scholar

[25]

L. Qi , Y. Wang and E. X. Wu, D-eigenvalues of diffusion kurtosis tensor,, J. Comput. Appl. Math., 221 (2008), 150.  doi: 10.1016/j.cam.2007.10.012.  Google Scholar

[26]

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games,, Israel Jurnal of Mathematics, 121 (2001), 221.  doi: 10.1007/BF02802505.  Google Scholar

[27]

R. Varga, Matrix Iterative Analysis,, Prentice-Hall, (1962).   Google Scholar

[28]

R. J. Wood and M. J. O'Neill, Finding the spectral radius of a large sparse non-negative matrix,, Anziam J., 48 (2007).   Google Scholar

[29]

Q. Yang and Y. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors,, SIAM J. Matrix Anal. Appl., 31 (2010), 2517.  doi: 10.1137/090778766.  Google Scholar

[30]

Q. Yang and Y. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors II,, SIAM J. Matrix Anal. Appl., 32 (2011), 1236.  doi: 10.1137/100813671.  Google Scholar

[31]

G. Zhou, L. Caccetta and L. Qi, Convergence of an algorithm for the largest singular value of a nonnegative rectangular tensor,, Linear Algebra Appl., 438 (2013), 959.  doi: 10.1016/j.laa.2011.06.038.  Google Scholar

show all references

References:
[1]

M. Akian, S. Gaubert and A. Guterman, Tropical polyhedra are equivalent to mean payoff games,, , ().   Google Scholar

[2]

F. Baccelli, G. Cohen, G. J. Olsder and J. P. Quadrat, Synchronization and Linearity,, Wiley Series in Probability and Mathematical Statistics, (1992).   Google Scholar

[3]

L. Baratchart, M. Berthod and L. Pottier, Optimization of positive generalized polynomials under lpconstraints, Journal of Convex Analysis, 5 (1998), 353.   Google Scholar

[4]

L. Bloy and R. Verma, On computing the underlying fiber directions from the diffusion orientation distribution function,, Medical Image Computing and Computer-Assisted Intervention MICCAI, (2008), 1.   Google Scholar

[5]

L. Collatz, Einschliessungssatz für die charakteristischen Zahlen von Matrizen,, Math. Zeit., 48 (1942), 221.   Google Scholar

[6]

K. C. Chang, K. J. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors,, Commun. Math. Sci., 6 (2008), 507.   Google Scholar

[7]

K. C. Chang, K. J. Pearson and T. Zhang, Primitivity, the convergence of the NQZ method and the largest eigenvalue for nonnegative tensors,, SIAM J. Matrix Anal. Appl., 32 (2011), 806.  doi: 10.1137/100807120.  Google Scholar

[8]

K. Chang, L. Qi and G. Zhou, Singular values of a real rectangular tensor,, Journal of Mathematical Analysis and Applications, 370 (2010), 284.  doi: 10.1016/j.jmaa.2010.04.037.  Google Scholar

[9]

L. De Lathauwer, B. De Moor and J. Vandewalle, On the best rank-1 and rank- (R1, ...,Rn) approximation of higher-order tensors,, SIAM J. Matrix Anal. Appl., 21 (2000), 1324.   Google Scholar

[10]

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

[11]

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

[12]

J. Gunawardena, From max-plus algebra to nonexpansive maps: a nonlinear theory for discrete event systems,, Theoritical Computer Science, 293 (2003), 141.  doi: 10.1016/S0304-3975(02)00235-9.  Google Scholar

[13]

J. Gunawardena (editor), Idempotency,, Publications of the Isaac Newton Institute, (1998).  doi: 10.1017/CBO9780511662508.  Google Scholar

[14]

T. G. Kolda and B. W. Bader, Tensor decompositions and applications,, SIAM Rev., 51 (2009), 455.  doi: 10.1137/07070111X.  Google Scholar

[15]

V. N. Kolokoltsov, Nonexpansive maps and option pricing theory,, Kybernetika, 34 (1998), 713.   Google Scholar

[16]

V. N. Kolokoltsov and V. P. Maslov, Idempotency Analysis and Applications,, Kluwer Academic, (1997).   Google Scholar

[17]

L. H. Lim, Multilinear pagerank: measuring higher order connectivity in linked objects,, The Internet: Today and Tomorrow, (2005).   Google Scholar

[18]

Y. Liu, G. Zhou and N. F. Ibrahim, An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor,, Journal of Computational and Applied Mathematics, 235 (2010), 286.  doi: 10.1016/j.cam.2010.06.002.  Google Scholar

[19]

M. Ng, L. Qi and G. Zhou, Finding the largest eigenvalue of a nonnegative tensor,, SIAM J. Matrix Anal. Appl., 31 (2009), 1090.  doi: 10.1137/09074838X.  Google Scholar

[20]

Q. Ni, L. Qi and F. Wang, An eigenvalue method for testing the positive definiteness of a multivariate form,, IEEE Transactions on Automatic Control, 53 (2008), 1096.  doi: 10.1109/TAC.2008.923679.  Google Scholar

[21]

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

[22]

R. D. Nussbaum, Iterated nonlinear map and Hilbert's projective metric, II,, Memoirs of the AMS, 79 (1989).  doi: 10.1090/memo/0401.  Google Scholar

[23]

M. Morishima, Equilibrium, Stability and Growth,, Clarenson, (2002).   Google Scholar

[24]

L. Qi, F. Wang and Y. Wang, Z-eigenvalue methods for a global polynomial optimization problem,, Mathematical Programming, 118 (2009), 301.  doi: 10.1007/s10107-007-0193-6.  Google Scholar

[25]

L. Qi , Y. Wang and E. X. Wu, D-eigenvalues of diffusion kurtosis tensor,, J. Comput. Appl. Math., 221 (2008), 150.  doi: 10.1016/j.cam.2007.10.012.  Google Scholar

[26]

D. Rosenberg and S. Sorin, An operator approach to zero-sum repeated games,, Israel Jurnal of Mathematics, 121 (2001), 221.  doi: 10.1007/BF02802505.  Google Scholar

[27]

R. Varga, Matrix Iterative Analysis,, Prentice-Hall, (1962).   Google Scholar

[28]

R. J. Wood and M. J. O'Neill, Finding the spectral radius of a large sparse non-negative matrix,, Anziam J., 48 (2007).   Google Scholar

[29]

Q. Yang and Y. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors,, SIAM J. Matrix Anal. Appl., 31 (2010), 2517.  doi: 10.1137/090778766.  Google Scholar

[30]

Q. Yang and Y. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors II,, SIAM J. Matrix Anal. Appl., 32 (2011), 1236.  doi: 10.1137/100813671.  Google Scholar

[31]

G. Zhou, L. Caccetta and L. Qi, Convergence of an algorithm for the largest singular value of a nonnegative rectangular tensor,, Linear Algebra Appl., 438 (2013), 959.  doi: 10.1016/j.laa.2011.06.038.  Google Scholar

[1]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042

[2]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020147

[3]

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

[4]

Zhong Wan, Chunhua Yang. New approach to global minimization of normal multivariate polynomial based on tensor. Journal of Industrial & Management Optimization, 2008, 4 (2) : 271-285. doi: 10.3934/jimo.2008.4.271

[5]

Kaili Zhang, Haibin Chen, Pengfei Zhao. A potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 429-443. doi: 10.3934/jimo.2018049

[6]

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

[7]

Fan Wu. Conditional regularity for the 3D Navier-Stokes equations in terms of the middle eigenvalue of the strain tensor. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020078

[8]

Huan Gao, Zhibao Li, Haibin Zhang. A fast continuous method for the extreme eigenvalue problem. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008

[9]

Yanfei Wang, Dmitry Lukyanenko, Anatoly Yagola. Magnetic parameters inversion method with full tensor gradient data. Inverse Problems & Imaging, 2019, 13 (4) : 745-754. doi: 10.3934/ipi.2019034

[10]

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

[11]

Francisco Guillén-González, Mamadou Sy. Iterative method for mass diffusion model with density dependent viscosity. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 823-841. doi: 10.3934/dcdsb.2008.10.823

[12]

Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529

[13]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025

[14]

Tobias Breiten, Sergey Dolgov, Martin Stoll. Solving differential Riccati equations: A nonlinear space-time method using tensor trains. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020034

[15]

Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028

[16]

Xiu Ye, Shangyou Zhang. A new weak gradient for the stabilizer free weak Galerkin method with polynomial reduction. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020277

[17]

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

[18]

Jiawei Dou, Lan-sun Chen, Kaitai Li. A monotone-iterative method for finding periodic solutions of an impulsive competition system on tumor-normal cell interaction. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 555-562. doi: 10.3934/dcdsb.2004.4.555

[19]

Lianjun Zhang, Lingchen Kong, Yan Li, Shenglong Zhou. A smoothing iterative method for quantile regression with nonconvex $ \ell_p $ penalty. Journal of Industrial & Management Optimization, 2017, 13 (1) : 93-112. doi: 10.3934/jimo.2016006

[20]

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, 2020, 13 (6) : 1773-1790. doi: 10.3934/dcdss.2020104

 Impact Factor: 

Metrics

  • PDF downloads (48)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]