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.