Optimization Online


Trace-Penalty Minimization for Large-scale Eigenspace Computation

Zaiwen Wen (zw2109***at***sjtu.edu.cn)
Chao Yang (cyang***at***lbl.gov)
Xin Liu (liuxin***at***lsec.cc.ac.cn)
Yin Zhang (yzhang***at***rice.edu)

Abstract: The Rayleigh-Ritz (RR) procedure, including orthogonalization, constitutes a major bottleneck in computing relatively high dimensional eigenspaces of large sparse matrices. Although operations involved 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 penalty model and establish its equivalence to the eigenvalue problem. This model enables us to deploy gradient-type 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

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Applications -- Science and Engineering (Basic Sciences Applications )


Download: [PDF]

Entry Submitted: 03/06/2013
Entry Accepted: 03/06/2013
Entry Last Modified: 01/17/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society