Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems

Hong-Yi Miao; Li Wang

doi:10.3934/naco.2021012

Article Contents

2021, Volume 11, Issue 4: 677-685. Doi: 10.3934/naco.2021012

This issue Previous Article An alternate gradient method for optimization problems with orthogonality constraints Next Article

Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems

Hong-Yi Miao^1,2, and
Li Wang^1, ,

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
^* Corresponding author: Li Wang

Received: January 2021

Revised: March 2021

Early access: March 2021

Published: December 2021

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

Abstract / Introduction Full Text(HTML) Figure(0) / Table(6) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 65F15, 65N25; Secondary: 65F10.

Citation:

FullText(HTML)

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[3]	K. J. Bathe, Finite Element Procedures in Engineering Analysis, Prentice-Hall, Englewood Cliffs, 1982.
[4]	M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer., 14 (2005), 1-137. doi: 10.1017/S0962492904000212.
[5]	L. Bergamaschi, R. Bru, A. Martinez and M. Putti, Quasi-Newton preconditioners for the inexact Newton method, Electronic Transactions on Numerical Analysis, 23 (2006), 76-87.
[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.
[7]	D. R. Fokkema, G. 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.
[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.
[9]	G. Hagerty, Finding a Few Eigenvalues of Large Sparse Nonsymmetric Matrices, Ph.D Thesis, Washington State University, 2001.
[10]	M. E. Hochstenbach and Y. Notay, The Jacobi-Davidson method, GAMM-Mitteilungen, 29 (2006), 368-382. doi: 10.1002/gamm.201490038.
[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.
[12]	Y. Saad, Iterative Methods for Aparse Linear Systems, PWS publishing, Boston, 1996. doi: 10.1137/1.9780898718003.
[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.
[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.
[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.
[16]	K. Wu, Y. Saad and A. Stathopoulos, Inexact Newton preconditioning techniques for large symmetric eigenvalue problems, J. Electronic Transactions on Numerical Analysis, 7 (1998), 202-214.