MRRR-based eigensolvers for multi-core processors and supercomputers

The real symmetric tridiagonal eigenproblem is of outstanding importance in numerical computations; it arises frequently as part of eigensolvers for standard and generalized dense Hermitian eigenproblems that are based on a reduction to tridiagonal form. For its solution, the algorithm of Multiple Relatively Robust Representations (MRRR or MR3 in short) - introduced in the late 1990s - is among the fastest methods. To compute k eigenpairs of a n-by-n real tridiagonal T, MRRR only requires O(kn) arithmetic operations; in contrast, all the other practical methods require O(k^2 n) or O(n^3) operations in the worst case. This thesis centers around the performance and accuracy of MRRR. First, we investigate how MRRR can make efficient use of modern multi-core architectures. We present a parallelization strategy that dynamically divides and schedules the work into tasks. This task-based approach is flexible and produces remarkable workload balancing. In a number of experiments, comparing our multi-threaded eigensolver, mr3smp, with the widely used LAPACK (Linear Algebra PACKage) and Intel’s Math Kernel library (MKL), we show that mr3smp outperforms even the fastest solvers available. Second, for massively parallel distributed/shared-memory systems, we introduce an eigensolver, PMRRR, that merges the task-based approach with a parallelization based on message-passing. Our design uses non-blocking communications, thus allowing processes to proceed computation while waiting to receive data. Experimentally, we show the importance of such an overlap of computation and communication for load balancing and scalability. Moreover, with a thorough performance study, we demonstrate that the new eigensolvers of the Elemental library, which are based on PMRRR, are faster and more scalable than the widely used eigensolvers of ScaLAPACK. Third, we present a mixed precision variant of MRRR, which improves the standard algorithm in multiple ways. In fact, compared with the best available methods (Divide & Conquer and the QR algorithm), the standard MRRR exhibits inferior accuracy and robustness. Moreover, when confronted with heavily clustered eigenvalues, its performance and scalability can suffer severely; such scalability problems especially arise on distributed-memory architectures. Our mixed precision approach makes MRRR at least as accurate as Divide & Conquer and the QR algorithm. In particular in context of direct methods for large-scale standard and generalized Hermitian eigenproblems, such an improvement comes with little or no performance penalty: eigensolvers based on our mixed precision MRRR are oftentimes faster than solvers based on Divide & Conquer and, in some circumstances, even faster than solvers based on the standard MRRR. Additionally, the use of mixed precisions considerably enhances robustness and parallel scalability