Trace minimization method via penalty for linear response eigenvalue problems

Yadan Chen; Yuan Shen; Shanshan Liu

doi:10.3934/jimo.2021206

Article Contents

2023, Volume 19, Issue 1: 773-791. Doi: 10.3934/jimo.2021206

This issue Previous Article Sharp bounds on the minimum $M$-eigenvalue and strong ellipticity condition of elasticity $Z$-tensors-tensors Next Article

Trace minimization method via penalty for linear response eigenvalue problems

1.
China National Clearing Center, Beijing 100048, China
2.
School of Economics and Management, University of the Chinese Academy of Sciences, Beijing 100190, China
3.
School of Applied Mathematics, Nanjing University of Finance & Economics, Nanjing 210023, China
4.
Hefei 168 Middle School, Hefei 230031, China

^*Corresponding author: Yuan Shen
^*Corresponding author: Yuan Shen

Received: May 31, 2021

Revised: July 31, 2021

Early access: December 2021

Published: January 2023

The second author is supported by the National Social Science Foundation of China under Grants 19AZD018, 20BGL028, 19BGL205, 17BTQ063

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

Abstract

In various applications, such as the computation of energy excitation states of electrons and molecules, and the analysis of interstellar clouds, the linear response eigenvalue problem, which is a special type of the Hamiltonian eigenvalue problem, is frequently encountered. However, traditional eigensolvers may not be applicable to this problem owing to its inherently large scale. In fact, we are usually more interested in computing some of the smallest positive eigenvalues. To this end, a trace minimum principle optimization model with orthogonality constraint has been proposed. On this basis, we propose an unconstrained surrogate model called trace minimization via penalty, and we establish its equivalence with the original constrained model, provided that the penalty parameter is larger than a certain threshold. By avoiding the orthogonality constraint, we can use a gradient-type method to solve this model. Specifically, we use the gradient descent method with Barzilai–Borwein step size. Moreover, we develop a restarting strategy for the proposed algorithm whereby higher accuracy and faster convergence can be achieved. This is verified by preliminary experimental results.

Keywords:

Mathematics Subject Classification: Primary: 65L15, 15A18; Secondary: 90C30.

Citation:

FullText(HTML)

Figure 1. Normalized residual norm vs iteration with $ k = 5 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)

Download: Full-size image PowerPoint slide

Figure 2. Normalized residual norm vs iteration with $ k = 50 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)

Download: Full-size image PowerPoint slide

Figure 3. Frobenius norm of gradient vs iteration with $ k = 5 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)

Download: Full-size image PowerPoint slide

Figure 4. Frobenius norm of gradient vs iteration with $ k = 50 $ (upper left: $ n = 1000 $; upper right: $ n = 2000 $; lower left: $ n = 4000 $; lower right: $ n = 6000 $)

Download: Full-size image PowerPoint slide

Figure 5. Normalized residual norm via iteration with $ k = 5 $ (left: n = 1000; middle: n = 2000; right: n = 4000)

Download: Full-size image PowerPoint slide

Figure 6. Frobenius norm of gradient via iteration with $ k = 5 $ (left: n = 1000; middle: n = 2000; right: n = 4000)

Download: Full-size image PowerPoint slide

Table 1. Numerical results on random problems

($ n, k $)	LOBP4dCG		Bcheb-dav		Alg. 1
($ n, k $)	NRN	time	NRN	time	NRN	time
(1000, 5)	3.374e-7	5.158	4.370e-7	1.213	9.953e-7	1.391
(2000, 5)	2.792e-6	16.156	5.319e-7	5.425	9.973e-7	2.529
(4000, 5)	2.052e-7	46.707	7.597e-7	29.476	9.355e-7	4.848
(6000, 5)	2.964e-7	219.598	7.230e-7	127.189	6.736e-7	17.503

| Show Table

DownLoad: CSV

Table 2. Numerical results on random problems

($ n, k $)	Bcheb-dav		Alg. 1
($ n, k $)	NRN	time	NRN	time
(1000, 50)	8.179e-7	1.924	6.617e-6	5.286
(2000, 50)	1.351e-7	10.493	9.445e-7	27.038
(4000, 50)	1.713e-7	45.975	9.239e-7	55.971
(6000, 50)	4.060e-7	237.142	9.587e-7	189.574

| Show Table

DownLoad: CSV

Table 3. Numerical results on random problems with smaller $ k $

($ n, k $)	LOBP4dCG		Bcheb-dav		Alg. 1
($ n, k $)	NRN	time	NRN	time	NRN	time
(1000, 2)	9.353e-10	1.034	2.347e-7	1.920	8.977e-7	0.522
(2000, 2)	2.639e-9	4.906	8.093e-7	5.481	9.122e-7	0.928
(4000, 2)	1.283e-9	21.372	9.518e-7	35.761	9.729e-7	1.159
(6000, 2)	2.050e-9	59.513	9.235e-7	218.249	6.868e-7	5.190

| Show Table

DownLoad: CSV

Table 4. Numerical results on random problems with larger $ k $

($ n, k $)	Bcheb-dav		Alg. 1
($ n, k $)	NRN	time	NRN	time
(500, 50)	1.721e-8	0.572	9.607e-6	2.462
(750, 75)	2.133e-8	1.740	9.994e-6	6.769
(1000, 100)	1.299e-8	2.945	9.902e-6	16.409
(1500, 150)	4.218e-8	10.376	9.999e-6	24.900
(2000, 200)	2.782e-8	19.507	7.717e-6	64.872
($ n, k $)	Bcheb-dav		Alg. 1
($ n, k $)	NRN	time	NRN	time
(500, 100)	1.713e-8	1.557	9.989e-6	7.355
(750, 150)	1.606e-8	2.310	9.996e-6	20.053
(1000, 200)	2.837e-8	6.128	9.993e-6	46.477
(1500, 300)	2.647e-8	15.524	9.815e-6	85.150
(2000, 400)	1.692e-8	28.886	4.970e-6	415.430

| Show Table

DownLoad: CSV

Table 5. Numerical results on random problems ($ tol = 10^{-9} $)

($ n, k $)	LOBP4dCG		Bcheb-dav		Alg. 2
($ n, k $)	NRN	time	NRN	time	NRN	time
(1000, 5)	1.741e-6	4.556	5.682e-10	1.641	1.969e-8	29.810
(2000, 5)	5.263e-8	13.573	6.082e-9	6.988	9.740e-10	80.980
(4000, 5)	3.956e-8	77.154	6.694e-9	44.313	9.257e-10	315.360

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Z. Bai and R. Li, Minimization principles for the linear response eigenvalue problem I: Theory, SIAM J. Matrix Anal. Appl., 33 (2012), 1075-1100. doi: 10.1137/110838960.
[2]	Z. Bai and R. Li, Minimization principles for the linear response eigenvalue problem II: Computation, SIAM J. Matrix Anal. Appl., 34 (2013), 392-416. doi: 10.1137/110838972.
[3]	Z. Bai, R. Li and W. Lin, Linear response eigenvalue problem solved by extended locally optimal preconditioned conjugate gradient methods, Sci. China Math., 59 (2016), 1443-1460. doi: 10.1007/s11425-016-0297-1.
[4]	P. Benner, H. Fassbender and M. Stoll, A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process, Linear Algebra Appl., 435 (2011), 578-600. doi: 10.1016/j.laa.2010.04.048.
[5]	M. E. Casida, Time-dependent density-functional response theory for molecules, Recent Advances in Density Functional Methods, (1995), 155–192. doi: 10.1142/9789812830586_0005.
[6]	U. Flaschka, W. Lin and J. Wu, A KQZ algorithm for solving linear-response eigenvalue equations, Linear Algebra Appl., 165 (1992), 93-123. doi: 10.1016/0024-3795(92)90231-X.
[7]	G. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 205-224. doi: 10.1137/0702016.
[8]	M. Gruning, A. Marini and X. Gonze, Exciton-plasmon states in nanoscale materials: Breakdown of the Tamm-Dancoff approximation, Nano Letters, 9 (2009), 2820-2824. doi: 10.1021/nl803717g.
[9]	W. Lin, P. van Dooren and Q. Xu, Equivalent Characterizations of Periodical Ininvariant Subspaces, NCTS Preprints Series 1998-8, National Center for Theoretical Sciences, Math. Division, National Tsing Hua University, 1998.
[10]	X. Liu, Z. Wen and Y. Zhang, Limited memory block Krylov subspace optimization for computing dominant singular value decompositions, SIAM J. Sci. Comput., 35 (2013), A1641–A1668. doi: 10.1137/120871328.
[11]	X. Liu, Z. Wen and Y. Zhang, An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations, SIAM J. Optim., 25 (2015), 1571-1608. doi: 10.1137/140971464.
[12]	M. J. Lucero, A. M. N. Niklasson, S. Tretiak and M. Challacombe, Molecular-orbital-free algorithm for excited states in time-dependent perturbation theory, J. Chem. Phys., 129 (2008), 064114. doi: 10.1063/1.2965535.
[13]	M. T. Lusk and A. E. Mattsson, High-performance computing for materials design to advance energy science, MRS Bulletin, 36 (2011), 169-174. doi: 10.1557/mrs.2011.30.
[14]	J. Olsen and P. Jorgensen, Linear and nonlinear response functions for an exact state and for an MCSCF state, J. Chem. Phys., 82 (1985), 3235-3264. doi: 10.1063/1.448223.
[15]	G. Onida, L. Reining and A. Rubio, Electronic excitations: Density-functional versus manybody Green's function approaches, Rev. Modern Phys., 74 (2002), 601-659. doi: 10.1103/RevModPhys.74.601.
[16]	D. Rocca, D. Lu and G. Galli, Ab initio calculations of optical absorpation spectra: Solution of the Bethe-Salpeter equation within density matrix perturbation theory, J. Chem. Phys., 133 (2010), 164109.
[17]	Y. Saad, J. R. Chelikowsky and S. M. Shontz, Numerical methods for electronic structure calculations of materials, SIAM Rev., 52 (2010), 3-54. doi: 10.1137/060651653.
[18]	Z. Teng and R. Li, Convergence analysis of Lanczos-type methods for the linear response eigenvalue problem, J. Comput. Appl. Math., 247 (2013), 17-33. doi: 10.1016/j.cam.2013.01.003.
[19]	Z. Teng, Y. Zhou and R. Li, A block Chebyshev-Davidson method for linear response eigenvalue problems, Adv. Comput. Math., 42 (2016), 1103-1128. doi: 10.1007/s10444-016-9455-2.
[20]	Z. Wen, C. Yang, X. Liu and Y. Zhang, Trace-penalty minimization for large-scale eigenspace computation, J. Sci. Comput., 66 (2016), 1175-1203. doi: 10.1007/s10915-015-0061-0.
[21]	H. Zhong and H. Xu, Weighted Golub-Kahan-Lanczos bidiagonalization algorithms, Electron. Trans. Numer. Anal., 47 (2017), 153-178. doi: 10.1553/etna_vol47s153.