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,, , ().

[2]

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

[3]

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

[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.

[5]

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

[6]

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

[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.

[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.

[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.

[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.

[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.

[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.

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[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.

[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.

[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.

[21]

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

[22]

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

[23]

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

[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.

[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.

[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.

[27]

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

[28]

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

[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.

[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.

[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.

show all references

References:
[1]

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

[2]

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

[3]

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

[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.

[5]

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

[6]

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

[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.

[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.

[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.

[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.

[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.

[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.

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[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.

[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.

[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.

[21]

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

[22]

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

[23]

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

[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.

[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.

[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.

[27]

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

[28]

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

[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.

[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.

[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.

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

Qilong Zhai, Ran Zhang. Lower and upper bounds of Laplacian eigenvalue problem by weak Galerkin method on triangular meshes. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-11. doi: 10.3934/dcdsb.2018091

[12]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[13]

Lunji Song, Zhimin Zhang. Polynomial preserving recovery of an over-penalized symmetric interior penalty Galerkin method for elliptic problems. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1405-1426. doi: 10.3934/dcdsb.2015.20.1405

[14]

Yiju Wang, Guanglu Zhou, Louis Caccetta. Nonsingular $H$-tensor and its criteria. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1173-1186. doi: 10.3934/jimo.2016.12.1173

[15]

Michel H. Geoffroy, Alain Piétrus. A fast iterative scheme for variational inclusions. Conference Publications, 2009, 2009 (Special) : 250-258. doi: 10.3934/proc.2009.2009.250

[16]

Nicolas Van Goethem. The Frank tensor as a boundary condition in intrinsic linearized elasticity. Journal of Geometric Mechanics, 2016, 8 (4) : 391-411. doi: 10.3934/jgm.2016013

[17]

Henry O. Jacobs, Hiroaki Yoshimura. Tensor products of Dirac structures and interconnection in Lagrangian mechanics. Journal of Geometric Mechanics, 2014, 6 (1) : 67-98. doi: 10.3934/jgm.2014.6.67

[18]

François Monard. Efficient tensor tomography in fan-beam coordinates. Inverse Problems & Imaging, 2016, 10 (2) : 433-459. doi: 10.3934/ipi.2016007

[19]

Shouchuan Hu, Nikolaos S. Papageorgiou. Nonlinear Neumann equations driven by a nonhomogeneous differential operator. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1055-1078. doi: 10.3934/cpaa.2011.10.1055

[20]

Arnold Dikansky. Fitzhugh-Nagumo equations in a nonhomogeneous medium. Conference Publications, 2005, 2005 (Special) : 216-224. doi: 10.3934/proc.2005.2005.216

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]