Computing the Smallest Eigenvalue of Large Ill-Conditioned Hankel Matrices (Communications in Computational Physics, 2018)
This paper presents a parallel algorithm for finding the smallest eigenvalueof a family of Hankel matrices that are ill-conditioned. Such matrices arise in randommatrix theory and require the use of extremely high precision arithmetic. Surprisingly,we find that a group of commonly-used approaches that are designed for highefficiency are actually less efficient than a direct approach for this class of matrices.We then develop a parallel implementation of the algorithm that takes into accountthe unusually high cost of individual arithmetic operations. Our approach combinesmessage passing and shared memory, achieving near-perfect scalability and high tolerancefor network latency. We are thus able to find solutions for much larger matricesthan previously possible, with the potential for extending this work to systems withgreater levels of parallelism. The contributions of this work are in three areas: determinationthat a direct algorithm based on the secant method is more effective whenextreme fixed-point precision is required than the algorithms more typically usedin parallel floating-point computations; the particular mix of optimizations requiredfor extreme precision large matrix operations on a modern multi-core cluster, and thenumerical results themselves.