Filtering Subspaces: How Parallelism and HPC gave new life to an old eigenvalue solver method

Subspace Iteration (SI) is perhaps one of the earliest iterative algorithmsused as a numerical eigensolver. After an early success, SI methods were abandonedin favor of iterative methods having a smaller footprint in terms of FLOP count.In the last 15 years, subspace methods with polynomial and rational filtering haveseen a resurgence. In this talk I illustrate how the advent of HPC middlewaretogether with advanced parallel computing paradigms are at the base of the revivaland success of modern SI methods.Arguably one of the earliest mentions of SI in the scientific literature is thework by L. Bauer in 1957, where SI is applied to the solution of the symmetricalgebraic eigenvalue problem. Several were the attempts to further develop andgeneralize it in the 1960s and 1970s. The first notable effort in this direction isthe fundamental work of Rutishauser in a number of papers spanning from 1969 to1970. Rutishauser builds on Bauer’s Simultaneous Iteration method and introducesfor the first time the concept of filtering through Chebyschev polynomials. Startingfrom the mid 1970s, the development of iterative eigensolvers for the Hermitianeigenvalue problem took on a different direction due to the revival of the Lanczosalgorithm and its variants. With respect to the latter, SI methods generally requirea higher FLOP count to reach convergence, and this made them, at the time, nolonger competitive.Subspace iteration eigensolvers with polynomial filtering saw a resurgence inpopularity starting in the middle of the 2000s with their application to the exteriorspectrum of Hamiltonian matrices emerging in electronic structure theory. Soonafter, a different class of SI methods based on rational filters started emerging andsaw a rapid expansion and application to both Hermitian and non-Hermitian eigen-problems. There are two main reasons for the comeback: 1) the advent of highlyspecialized HPC libraries (e.g. BLAS) which are able to make a distinction betweenslow FLOPs and fast FLOPs in the current hierarchy of caches, and 2) the ability to leverage the hierarchy of nested parallelism that methods based on subspace iter-ation can offer. In this talk I present a brief overview of how these two factors havecontributed to the revival of SI, illustrate recent developments in the field, and givean outlook on the future of these methods and on how their use could positivelyimpact scientific computing applications