• Previous Article
    Solving nonlinear differential equations using hybrid method between Lyapunov's artificial small parameter and continuous particle swarm optimization
  • NACO Home
  • This Issue
  • Next Article
    Individual biometrics pattern based artificial image analysis techniques
doi: 10.3934/naco.2021012

Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems

1. 

Jiangsu Key Laboratory for NSLSCS, School of Mathematical Science, Nanjing Normal University, Nanjing, 210023, China

2. 

College of Science, Nanjing Forestry University, Nanjing, 210023, China

* Corresponding author: Li Wang

Received  January 2021 Revised  March 2021 Published  March 2021

Fund Project: The authors are supported by the National Natural Science Foundation of China under grant 41571380 and 10971102, Major project 16KJA110001 of the Natural Science Foundation of the Jiangsu Higher Education Institution

An efficiently preconditioned Newton-like method for the computation of the eigenpairs of large and sparse nonsymmetric matrices is proposed. A sequence of preconditioners based on the Broyden-type rank-one update formula are constructed for the solution of the linearized Newton system. The properties of the preconditioned matrix are investigated. Numerical results are given which reveal that the new proposed algorithms are efficient.

Citation: Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, doi: 10.3934/naco.2021012
References:
[1]

Z. Z. Bai and G. H. Golub, Accelerated Hermitian and skew-Hermitian splitting methods for saddle-point problems, SIAM J. Numer. Anal., 27 (2007), 1-23.  doi: 10.1093/imanum/drl017.  Google Scholar

[2]

Z. Z. Bai and C. Q. Miao, On local quadratic convergence of inexact simplified Jacobi-Davidson method, Linear Algebra Appl., 520 (2017), 215-241.  doi: 10.1016/j.laa.2017.01.018.  Google Scholar

[3]

K. J. Bathe, Finite Element Procedures in Engineering Analysis, Prentice-Hall, Englewood Cliffs, 1982.  Google Scholar

[4]

M. BenziG. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1-137.  doi: 10.1017/S0962492904000212.  Google Scholar

[5]

L. BergamaschiR. BruA. Martinez and M. Putti, Quasi-Newton preconditioners for the inexact Newton method, Electronic Transactions on Numerical Analysis, 23 (2006), 76-87.   Google Scholar

[6]

L. Bergamaschi and A. Martinez, Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems, arXiv: 1312.1553v1 [math.NA], 5 Dec, 2013. doi: 10.1080/10556788.2014.908878.  Google Scholar

[7]

D. R. FokkemaG. L. G. Sleijpen and H. A. Van der vorst, Acclerated inexact Newton schemes for large systems of nolinear equations, SIAM Journal on Scientific Computing, 19 (1997), 657-674.  doi: 10.1137/S1064827595296148.  Google Scholar

[8]

M. A. Freitag and A. Spence, Rayleigh quotient iteration and simplified Jacobi-Davidson method with preconditioned iterative solves, Linear Algebra Appl., 428 (2008), 2049-2060.  doi: 10.1016/j.laa.2007.11.013.  Google Scholar

[9]

G. Hagerty, Finding a Few Eigenvalues of Large Sparse Nonsymmetric Matrices, Ph.D Thesis, Washington State University, 2001.  Google Scholar

[10]

M. E. Hochstenbach and Y. Notay, The Jacobi-Davidson method, GAMM-Mitteilungen, 29 (2006), 368-382.  doi: 10.1002/gamm.201490038.  Google Scholar

[11]

J. Pestana and A. J. Wathen, Natural preconditioning and iterative methods for saddle point problems, SIAM Rev., 57 (2015), 71-91.  doi: 10.1137/130934921.  Google Scholar

[12]

Y. Saad, Iterative Methods for Aparse Linear Systems, PWS publishing, Boston, 1996. doi: 10.1137/1.9780898718003.  Google Scholar

[13]

G. L. Sleijpen and H. A. Van Der Vorst, A Jacobi-Davidson method for linear eigenvalue problems, SIAM J. Matrix Anal., 17 (1996), 401-425.  doi: 10.1137/S0895479894270427.  Google Scholar

[14]

G. L. Sleljpen and H. A. Van Der Vorst, Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT., 42 (2002), 159-182.  doi: 10.1023/A:1021930421106.  Google Scholar

[15]

G. Wu and L. Zhang, On expansion of search subspaces for large non-Hermitian eigenproblems, J. Linear Algebra and Applications, 454 (2014), 107-129.  doi: 10.1016/j.laa.2014.04.021.  Google Scholar

[16]

K. WuY. Saad and A. Stathopoulos, Inexact Newton preconditioning techniques for large symmetric eigenvalue problems, J. Electronic Transactions on Numerical Analysis, 7 (1998), 202-214.   Google Scholar

show all references

References:
[1]

Z. Z. Bai and G. H. Golub, Accelerated Hermitian and skew-Hermitian splitting methods for saddle-point problems, SIAM J. Numer. Anal., 27 (2007), 1-23.  doi: 10.1093/imanum/drl017.  Google Scholar

[2]

Z. Z. Bai and C. Q. Miao, On local quadratic convergence of inexact simplified Jacobi-Davidson method, Linear Algebra Appl., 520 (2017), 215-241.  doi: 10.1016/j.laa.2017.01.018.  Google Scholar

[3]

K. J. Bathe, Finite Element Procedures in Engineering Analysis, Prentice-Hall, Englewood Cliffs, 1982.  Google Scholar

[4]

M. BenziG. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1-137.  doi: 10.1017/S0962492904000212.  Google Scholar

[5]

L. BergamaschiR. BruA. Martinez and M. Putti, Quasi-Newton preconditioners for the inexact Newton method, Electronic Transactions on Numerical Analysis, 23 (2006), 76-87.   Google Scholar

[6]

L. Bergamaschi and A. Martinez, Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems, arXiv: 1312.1553v1 [math.NA], 5 Dec, 2013. doi: 10.1080/10556788.2014.908878.  Google Scholar

[7]

D. R. FokkemaG. L. G. Sleijpen and H. A. Van der vorst, Acclerated inexact Newton schemes for large systems of nolinear equations, SIAM Journal on Scientific Computing, 19 (1997), 657-674.  doi: 10.1137/S1064827595296148.  Google Scholar

[8]

M. A. Freitag and A. Spence, Rayleigh quotient iteration and simplified Jacobi-Davidson method with preconditioned iterative solves, Linear Algebra Appl., 428 (2008), 2049-2060.  doi: 10.1016/j.laa.2007.11.013.  Google Scholar

[9]

G. Hagerty, Finding a Few Eigenvalues of Large Sparse Nonsymmetric Matrices, Ph.D Thesis, Washington State University, 2001.  Google Scholar

[10]

M. E. Hochstenbach and Y. Notay, The Jacobi-Davidson method, GAMM-Mitteilungen, 29 (2006), 368-382.  doi: 10.1002/gamm.201490038.  Google Scholar

[11]

J. Pestana and A. J. Wathen, Natural preconditioning and iterative methods for saddle point problems, SIAM Rev., 57 (2015), 71-91.  doi: 10.1137/130934921.  Google Scholar

[12]

Y. Saad, Iterative Methods for Aparse Linear Systems, PWS publishing, Boston, 1996. doi: 10.1137/1.9780898718003.  Google Scholar

[13]

G. L. Sleijpen and H. A. Van Der Vorst, A Jacobi-Davidson method for linear eigenvalue problems, SIAM J. Matrix Anal., 17 (1996), 401-425.  doi: 10.1137/S0895479894270427.  Google Scholar

[14]

G. L. Sleljpen and H. A. Van Der Vorst, Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT., 42 (2002), 159-182.  doi: 10.1023/A:1021930421106.  Google Scholar

[15]

G. Wu and L. Zhang, On expansion of search subspaces for large non-Hermitian eigenproblems, J. Linear Algebra and Applications, 454 (2014), 107-129.  doi: 10.1016/j.laa.2014.04.021.  Google Scholar

[16]

K. WuY. Saad and A. Stathopoulos, Inexact Newton preconditioning techniques for large symmetric eigenvalue problems, J. Electronic Transactions on Numerical Analysis, 7 (1998), 202-214.   Google Scholar

Table 1.  The results for the largest real eigenvalue of $ A $
Algorithm eigenvalue CPU time (s)
GMRES-INewton 7.9817 9.8430
PGMRES-INewton 7.9817 6.9330
Algorithm eigenvalue CPU time (s)
GMRES-INewton 7.9817 9.8430
PGMRES-INewton 7.9817 6.9330
Table 2.  The results of GMRES-INewton and PGMRES-INewton method
GMRES-INewton PGMRES-INewton
k $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(\mathcal{A}) $ $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(P^{-1}\mathcal{A}) $
1 2.8670e+03 1.4750e+00 3.1275e+09 2.8670e+03 1.4750e+00 3.1275e+09
2 5.6282e+01 7.2040e-01 2.8736e+05 2.4063e+01 4.8650e-02 4.0326e+04
3 1.2415e+00 3.8120e-02 6.1342e+04 3.4120e-03 6.7520e-03 3.3108e+04
4 1.3586e-04 3.3470e-05 3.1625e+04 5.4758e-05 1.2050e-05 3.0213e+03
GMRES-INewton PGMRES-INewton
k $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(\mathcal{A}) $ $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(P^{-1}\mathcal{A}) $
1 2.8670e+03 1.4750e+00 3.1275e+09 2.8670e+03 1.4750e+00 3.1275e+09
2 5.6282e+01 7.2040e-01 2.8736e+05 2.4063e+01 4.8650e-02 4.0326e+04
3 1.2415e+00 3.8120e-02 6.1342e+04 3.4120e-03 6.7520e-03 3.3108e+04
4 1.3586e-04 3.3470e-05 3.1625e+04 5.4758e-05 1.2050e-05 3.0213e+03
Table 3.  The results for the largest real eigenvalue of $ A $
Algorithm eigenvalue CPU time (s)
GMRES-INewton 0.4338 12.5310
PGMRES-INewton 0.4338 10.4990
Algorithm eigenvalue CPU time (s)
GMRES-INewton 0.4338 12.5310
PGMRES-INewton 0.4338 10.4990
Table 4.  The results of GMRES-INewton and PGMRES-INewton method
GMRES-INewton PGMRES-INewton
k $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(\mathcal{A}) $ $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(P^{-1}\mathcal{A}) $
1 2.6740e+02 5.8630e+01 1.2640e+10 2.6740e+02 5.8630e+01 1.2640e+10
2 4.3572e+01 1.0270e+01 6.0304e+07 7.6230e+00 9.6810e-02 5.6210e+05
3 3.0450e+00 7.8140e-01 2.4639e+05 3.2540e-02 4.2830e-04 3.2790e+04
4 6.3580e-02 4.6720e-02 5.1852e+04 4.9130e-05 1.4270e-06 4.5870e+04
5 2.3710e-04 1.0390e-03 1.3089e+05
GMRES-INewton PGMRES-INewton
k $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(\mathcal{A}) $ $ ||r_{k}|| $ $ |\lambda_{k}-\lambda^{*}| $ $ cond(P^{-1}\mathcal{A}) $
1 2.6740e+02 5.8630e+01 1.2640e+10 2.6740e+02 5.8630e+01 1.2640e+10
2 4.3572e+01 1.0270e+01 6.0304e+07 7.6230e+00 9.6810e-02 5.6210e+05
3 3.0450e+00 7.8140e-01 2.4639e+05 3.2540e-02 4.2830e-04 3.2790e+04
4 6.3580e-02 4.6720e-02 5.1852e+04 4.9130e-05 1.4270e-06 4.5870e+04
5 2.3710e-04 1.0390e-03 1.3089e+05
Table 5.  The results for the largest real eigenvalue of a random matrix
Algorithm eigenvalue CPU time (s)
GMRES-INewton 298.2441 15.7350
PGMRES-INewton 298.2441 9.1470
Algorithm eigenvalue CPU time (s)
GMRES-INewton 298.2441 15.7350
PGMRES-INewton 298.2441 9.1470
Table 6.  The results for the largest imaginary eigenvalue of a random matrix
Algorithm eigenvalue CPU time (s)
GMRES-INewton -0.0001+0.0054$ i $ 16.2370
PGMRES-INewton -0.0001+0.0054$ i $ 10.4790
Algorithm eigenvalue CPU time (s)
GMRES-INewton -0.0001+0.0054$ i $ 16.2370
PGMRES-INewton -0.0001+0.0054$ i $ 10.4790
[1]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[2]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381

[3]

Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1773-1793. doi: 10.3934/jimo.2018122

[4]

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

[5]

Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199

[6]

Jinyan Fan, Jianyu Pan. Inexact Levenberg-Marquardt method for nonlinear equations. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223

[7]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[8]

Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems & Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123

[9]

Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

[10]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013

[11]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030

[12]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135

[13]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[14]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[15]

T. Tachim Medjo. On the Newton method in robust control of fluid flow. Discrete & Continuous Dynamical Systems, 2003, 9 (5) : 1201-1222. doi: 10.3934/dcds.2003.9.1201

[16]

Xiaojiao Tong, Felix F. Wu, Yongping Zhang, Zheng Yan, Yixin Ni. A semismooth Newton method for solving optimal power flow. Journal of Industrial & Management Optimization, 2007, 3 (3) : 553-567. doi: 10.3934/jimo.2007.3.553

[17]

Zhi-Feng Pang, Yu-Fei Yang. Semismooth Newton method for minimization of the LLT model. Inverse Problems & Imaging, 2009, 3 (4) : 677-691. doi: 10.3934/ipi.2009.3.677

[18]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61

[19]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103

[20]

Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]