Trace-Penalty Minimization for Large-Scale Eigenspace Computation

详细信息    查看全文

• 作者：Zaiwen Wen ; Chao Yang ; Xin Liu ; Yin Zhang
• 关键词：Eigenvalue computation ; Exact quadratic penalty approach ; Gradient methods ; 15A18 ; 65F15 ; 65K05 ; 90C06
• 刊名：Journal of Scientific Computing
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：66
• 期：3
• 页码：1175-1203
• 全文大小：839 KB
• 参考文献：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)
  2.Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)CrossRef MathSciNet MATH
  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)CrossRef
  4.Courant, R.: Variational methods for the solution of problems of equilibrium and vibrations. Bull. Am. Math. Soc. 49, 1–23 (1943)CrossRef MathSciNet MATH
  5.Dai, Y.H.: On the nonmonotone line search. J. Optim. Theory Appl. 112, 315–330 (2002)CrossRef MathSciNet MATH
  6.Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  8.Knyazev, Andrew V.: Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method. SIAM J. Sci. Comput. 23, 517–541 (2001)CrossRef MathSciNet MATH
  9.Kronik, L., Makmal, A., Tiago, M., Alemany, M.M.G., Huang, X., Saad, Y., Chelikowsky, J.R.: 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)CrossRef
  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)
  11.Nocedal, Jorge, Wright, Stephen J.: Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)
  12.Saad, Yousef, Chelikowsky, James R., Shontz, Suzanne M.: Numerical methods for electronic structure calculations of materials. SIAM Rev. 52, 3–54 (2010)CrossRef MathSciNet MATH
  13.Sameh, Ahmed H., Wisniewski, John A.: A trace minimization algorithm for the generalized eigenvalue problem. SIAM J. Numer. Anal. 19, 1243–1259 (1982)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  15.Stathopoulos, A., McCombs, J.R.: PRIMME: preconditioned iterative multimethod eigensolver-methods and software description. ACM Trans. Math. Softw. 37, 21:1–21:30 (2010)CrossRef
  16.Sun, Wenyu, Yuan, Yaxiang: Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006)
  17.Teter, M.P., Payne, M.C., Allan, D.C.: Solution of schrödinger’s equation for large systems. Phys. Rev. B 40, 12255–12263 (1989)CrossRef
  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)CrossRef MathSciNet
  19.Zhang, Hongchao, Hager, William W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043–1056 (2004)CrossRef MathSciNet MATH
  20.Zhou, Y.: A block Chebyshev-Davidson method with inner-outer restart for large eigenvalue problems. J. Comput. Phys. 229, 9188–9200 (2010)CrossRef MathSciNet MATH
  21.Zhou, Y., Saad, Y.: A Chebyshev-Davidson algorithm for large symmetric eigenproblems. SIAM J. Matrix Anal. Appl. 29, 954–971 (2007)CrossRef MathSciNet MATH
  22.Zhou, Y., Saad, Y.: Block krylovschur method for large symmetric eigenvalue problems. Numer. Algorithms 47, 341–359 (2008)CrossRef MathSciNet MATH
  
• 作者单位：Zaiwen Wen (1)
  Chao Yang (2)
  Xin Liu (3)
  Yin Zhang (4)
  
  1. Beijing International Center for Mathematical Research, Peking University, Beijing, China
  2. Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA, USA
  3. State Key Laboratory of Scientific and Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
  4. Department of Computational and Applied Mathematics, Rice University, Houston, TX, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Algorithms
  Computational Mathematics and Numerical Analysis
  Applied Mathematics and Computational Methods of Engineering
  Mathematical and Computational Physics
  
• 出版者：Springer Netherlands
• ISSN：1573-7691

文摘

In a block algorithm for computing relatively high-dimensional eigenspaces of large sparse symmetric matrices, the Rayleigh-Ritz (RR) procedure often constitutes a major bottleneck. Although dense eigenvalue calculations for subproblems in RR steps can be parallelized to a certain level, their parallel scalability, which is limited by some inherent sequential steps, is lower than dense matrix-matrix multiplications. The primary motivation of this paper is to develop a methodology that reduces the use of the RR procedure in exchange for matrix-matrix multiplications. We propose an unconstrained trace-penalty minimization model and establish its equivalence to the eigenvalue problem. With a suitably chosen penalty parameter, this model possesses far fewer undesirable full-rank stationary points than the classic trace minimization model. More importantly, it enables us to deploy algorithms that makes heavy use of dense matrix-matrix multiplications. Although the proposed algorithm does not necessarily reduce the total number of arithmetic operations, it leverages highly optimized operations on modern high performance computers to achieve parallel scalability. Numerical results based on a preliminary implementation, parallelized using OpenMP, show that our approach is promising. Keywords Eigenvalue computation Exact quadratic penalty approach Gradient methods