Highly Scalable Algorithms and Solvers for Eigen-Problems: Unconstrained Optimization and Multiple Power Iterations

William Marsh Rice University, Houston TX

Investigators

Abstract

In today's big-data era, many organizations are facing the challenge of making sense of or use of massive datasets collected or flowing in at unprecedented rates. The first step is often to reduce the size of data to a manageable level by extracting essence and removing redundancy. Many techniques for data reduction and information extraction rely on so-called "principal component analysis" which requires intensive mathematical calculations. As data size keeps growing fast, such intensive computations need to be carried out on high-performance parallel computers that are able to execute a large number of independent tasks simultaneously. Currently, bottlenecks have appeared in commonly used mathematical methods that prevent big tasks from being broken up into enough independent small pieces to be quickly handled in parallel. In other words, the current mathematical methods have encountered difficulty in scalability. To break through the bottlenecks, this scalability issues must be attacked by devising new methodologies. This project proposes a few new approaches of higher scalability. Preliminary experiments have demonstrated clear promises, offering multi-fold speedups on a wide class of problems even on commodity computers. Careful theoretical and experimental investigations will be carried out in this project to fully develop the proposed methodologies. Computing a relatively large number of principal eigenpairs or singular pairs of large-scale matrices (or data sets) is a fundamental computational problem with wide-ranging applications, especially in today's big-data information era. Fast-increasing problem sizes and ever-evolving computer architectures have posed new algorithmic challenges. A constant challenge is to reach for higher algorithm concurrency in order to solve critical application problems on massively parallel computers. Currently, the main bottleneck to high scalability lies in the combined tasks of Rayleigh-Ritz and orthogonalization (RR/Orth, in short) that are heavily used by most state-of-the-art eigensolvers. The proposed research is to explore new strategies for developing highly parallel and scalable algorithms. A key idea is to reduce the use of RR/Orth operations in exchange for operations of higher concurrency. One approach makes use of unconstrained optimization formulations without orthogonality constraint so that, in principle, reasonable unconstrained optimization algorithms can be used without needing RR/Orth operations; another approach utilizes a simple but embarrassingly parallel procedure called multi-power method (MPM). Preliminary theoretical and numerical results are presented to demonstrate the potential of these approaches. In particular, the MPM approach has been empirically shown to achieve an "optimal performance" under reasonable conditions. It remains challenging to attain robustness and efficiency levels comparable to those of state-of-the-art eigensolvers.