Trace-penalty minimization for large-scale eigenspace computation. (English) Zbl 1373.65026

The eigenspace corresponding to the \(k\) smallest eigenvalues of a large-scale matrix pencil \((A,B)\) with symmetric matrices of size \(n\times n\) (and \(B\) positive definite) is the solution of the constrained problem \(\min_X \mathrm{tr}(X^TAX)\) with \(X\in\mathbb{R}^{n\times k}\) satisfying \(X^TBX=I\). It is proposed to solve this problem by minimizing \(f_\mu(X)=\frac{1}{2}\mathrm{tr}(X^TAX)+\frac{\mu}{4}\|X^TBX-I\|_F\) using standard methods. A key result shown is that \(\mu\) need not be very large, but that if suffices to choose \(\max(0,\lambda_k)<\mu<\lambda_n\) where \(\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n\) are the sorted eigenvalues of \(A\) for there to be essentially only one minimum that is global. Algorithmic aspects of a classical steepest descent minimization procedure are discussed. This includes restarts, the choice of the parameter \(\mu\), and stopping criteria. Also the complexity of the algorithm is discussed and it is extensively tested on numerical examples.


65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
15A22 Matrix pencils
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI Link


[1] Anderson, E., Bai, Z., Dongarra, J., Greenbaum, A., McKenney, A., Du Croz, J., Hammerling, S., Demmel, J., Bischof, C., Sorensen, D.: Lapack: a portable linear algebra library for high-performance computers, in Proceedings of the 1990 ACM/IEEE conference on Supercomputing, Supercomputing ’90, IEEE Computer Society Press, pp. 2-11 (1990) · Zbl 1151.65321
[2] Barzilai, J; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055
[3] Blackford, L.S., Choi, J., Cleary, A., D’Azeuedo, E., Demmel, J., Dhillon, I., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.C.: ScaLAPACK User’s Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1997) · Zbl 0886.65022
[4] Courant, R, Variational methods for the solution of problems of equilibrium and vibrations, Bull. Am. Math. Soc., 49, 1-23, (1943) · Zbl 0063.00985
[5] Dai, YH, On the nonmonotone line search, J. Optim. Theory Appl., 112, 315-330, (2002) · Zbl 1049.90087
[6] Grippo, L; Lampariello, F; Lucidi, S, A nonmonotone line search technique for newton’s method, SIAM J. Numer. Anal., 23, 707-716, (1986) · Zbl 0616.65067
[7] Knyazev, A; Argentati, M; Lashuk, I; Ovtchinnikov, E, Block locally optimal preconditioned eigenvalue xolvers (blopex) in hypre and petsc, SIAM J. Sci. Comput., 29, 2224-2239, (2007) · Zbl 1149.65026
[8] Knyazev, Andrew V, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 517-541, (2001) · Zbl 0992.65028
[9] Kronik, L; Makmal, A; Tiago, M; Alemany, MMG; Huang, X; Saad, Y; Chelikowsky, JR, PARSEC - the pseudopotential algorithm for real-space electronic structure calculations: recent advances and novel applications to nanostructures, Phys. Status Solidi. (b), 243, 1063-1079, (2006)
[10] Lehoucq, R.B., Sorensen, D.C., Yang, C.: ARPACK users’ guide: Solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, vol. 6 of software, environments, and tools, society for industrial and applied mathematics (SIAM), Philadelphia, PA, (1998) · Zbl 0901.65021
[11] Nocedal, Jorge, Wright, Stephen J.: Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[12] Saad, Yousef; Chelikowsky, James R; Shontz, Suzanne M, Numerical methods for electronic structure calculations of materials, SIAM Rev., 52, 3-54, (2010) · Zbl 1185.82004
[13] Sameh, Ahmed H; Wisniewski, John A, A trace minimization algorithm for the generalized eigenvalue problem, SIAM J. Numer. Anal., 19, 1243-1259, (1982) · Zbl 0493.65017
[14] Stathopoulos, Andreas; McCombs, James R, Nearly optimal preconditioned methods for Hermitian eigenproblems under limited memory. part II: seeking many eigenvalues, SIAM J. Sci. Comput., 29, 2162-2188, (2007) · Zbl 1151.65320
[15] Stathopoulos, A; McCombs, JR, PRIMME: preconditioned iterative multimethod eigensolver-methods and software description, ACM Trans. Math. Softw., 37, 21:1-21:30, (2010) · Zbl 1364.65087
[16] Sun, Wenyu, Yuan, Yaxiang: Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006) · Zbl 1129.90002
[17] Teter, MP; Payne, MC; Allan, DC, Solution of schrödinger’s equation for large systems, Phys. Rev. B, 40, 12255-12263, (1989)
[18] Yang, Chao; Meza, Juan C; Lee, Byounghak; Wang, Lin-Wang, KSSOLV-a MATLAB toolbox for solving the Kohn-Sham equations, ACM Trans. Math. Softw., 36, 1-35, (2009) · Zbl 1364.65112
[19] Zhang, Hongchao; Hager, William W, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14, 1043-1056, (2004) · Zbl 1073.90024
[20] Zhou, Y, A block Chebyshev-Davidson method with inner-outer restart for large eigenvalue problems, J. Comput. Phys., 229, 9188-9200, (2010) · Zbl 1203.65077
[21] Zhou, Y; Saad, Y, A Chebyshev-Davidson algorithm for large symmetric eigenproblems, SIAM J. Matrix Anal. Appl., 29, 954-971, (2007) · Zbl 1151.65321
[22] Zhou, Y; Saad, Y, Block krylovschur method for large symmetric eigenvalue problems, Numer. Algorithms, 47, 341-359, (2008) · Zbl 1153.65330
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.