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

在当今的大数据时代，许多组织都面临着如何理解或使用以前所未有的速度收集或流入的大量数据集的挑战。第一步通常是通过提取精华和去除冗余来将数据大小减小到可管理的水平。许多数据简化和信息提取技术依赖于所谓的“主成分分析”，这需要大量的数学计算。随着数据量的快速增长，这种密集的计算需要在能够同时执行大量独立任务的高性能并行计算机上进行。目前，在常用的数学方法中出现了瓶颈，这些方法阻止将大任务分解成足够多的独立小块以快速并行处理。换句话说，目前的数学方法在可扩展性方面遇到了困难。要突破瓶颈，必须通过设计新的方法来解决可伸缩性问题。本项目提出了一些具有更高可扩展性的新方法。初步的实验已经证明了明确的承诺，即使在普通计算机上，也能在广泛的问题上提供成倍的加速。本项目将进行仔细的理论和实验调查，以充分发展所提出的方法。计算大规模矩阵（或数据集）的相对大量的主特征对或奇异对是一个具有广泛应用的基本计算问题，特别是在今天的大数据信息时代。快速增长的问题规模和不断发展的计算机体系结构对算法提出了新的挑战。为了解决大规模并行计算机上的关键应用问题，实现更高的算法并发性是一个持续的挑战。目前，高可扩展性的主要瓶颈在于大多数最先进的特征解算器大量使用的瑞利-里兹和正交化（RR/ north，简而言之）的组合任务。提出的研究旨在探索开发高度并行和可扩展算法的新策略。一个关键思想是减少RR/ north操作的使用，以换取更高并发性的操作。一种方法是利用无正交性约束的无约束优化公式，这样，原则上可以使用合理的无约束优化算法，而不需要RR/ north操作；另一种方法使用一种简单但令人尴尬的并行程序，称为多功率法（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.