Article Contents
Article Contents

# Trace minimization method via penalty for linear response eigenvalue problems

• *Corresponding author: Yuan Shen

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

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

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

 Citation:

• 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$)

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$)

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$)

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$)

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

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

Table 1.  Numerical results on random problems

 ($n, k$) LOBP4dCG Bcheb-dav Alg. 1 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

Table 2.  Numerical results on random problems

 ($n, k$) Bcheb-dav Alg. 1 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

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

 ($n, k$) LOBP4dCG Bcheb-dav Alg. 1 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

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

 ($n, k$) Bcheb-dav Alg. 1 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 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

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

 ($n, k$) LOBP4dCG Bcheb-dav Alg. 2 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
•  [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.

Figures(6)

Tables(5)