Implementation and tuning of a parallel symmetric Toeplitz eigensolver

In a previous paper (Vidal et al., 2008, [21]), we presented a parallel solver for the symmetric Toeplitz eigenvalue problem, which is based on a modified version of the Lanczos iteration. However, its efficient implementation on modern parallel architectures is not trivial.In this paper, we present an efficient implementation on multicore processors which takes advantage of the features of this architecture. Several optimization techniques have been incorporated to the algorithm: improvement of Discrete Sine Transform routines, utilization of the Gohberg–Semencul formulas to solve the Toeplitz linear systems, optimization of the workload distribution among processors, and others. Although the algorithm follows a distributed memory parallel programming paradigm that is led by the nature of the mathematical derivation, special attention has been paid to obtaining the best performance in multicore environments. Hybrid techniques, which merge OpenMP and MPI, have been used to increase the performance in these environments. Experimental results show that our implementation takes advantage of multicore architectures and clearly outperforms the results obtained with LAPACK or ScaLAPACK.

Research highlights
► The goal is the efficient computation of eigenvalues of Symmetric Toeplitz matrices.
► Efficient parallel algorithm based on Lanczos method plus “Shift-and-invert” technique.
► Use of fast symmetric Toeplitz solvers and optimized kernels for computing the DST.
► Tuned algorithm for multicore architecture; clear improvement over Lapack/Scalapack.