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

在当今的大数据时代，许多组织都面临着如何理解或使用以前所未有的速度收集或涌入的海量数据集的挑战。第一步通常是通过提取本质和去除冗余来将数据大小减少到可管理的水平。许多数据约简和信息提取技术依赖于所谓的“主成分分析”，这需要密集的数学计算。随着数据量的快速增长，这种密集的计算需要在能够同时执行大量独立任务的高性能并行计算机上进行。目前，常用的数学方法出现了瓶颈，这些方法阻止大任务被分解成足够独立的小块，以便快速并行处理。换句话说，当前的数学方法在可伸缩性方面遇到了困难。为了突破瓶颈，必须通过设计新的方法来解决可伸缩性问题。本项目提出了几种具有较高可扩展性的新方法。初步实验已经证明了明确的前景，即使是在商用计算机上，也能在广泛的类别问题上提供数倍的加速。计算大规模矩阵(或数据集)的较大数量的主特征对或奇异偶是一个具有广泛应用的基本计算问题，特别是在当今大数据信息时代。快速增长的问题规模和不断发展的计算机体系结构提出了新的算法挑战。一个持续不断的挑战是达到更高的算法并发性，以便在大规模并行计算机上解决关键应用问题。目前，高可伸缩性的主要瓶颈在于Rayleigh-Ritz和正交化(简称RR/Orth)的组合任务，这些任务被大多数最先进的特征解析器大量使用。提出的研究是为了探索开发高度并行和可扩展算法的新策略。一个关键的想法是减少RR/ORTH操作的使用，以换取更高并发性的操作。一种方法利用没有正交性约束的无约束优化公式，原则上可以使用合理的无约束优化算法，而不需要RR/Orth运算；另一种方法使用一种简单但令人尴尬的并行过程，称为多幂方法(MPM)。文中给出了初步的理论和数值结果，以证明这些方法的潜力。特别是，MPM方法已经被经验证明在合理的条件下实现了“最佳性能”。要达到与最先进的特征解析器相当的健壮性和效率水平，仍然具有挑战性。

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.