Abstract
This paper presents a parallel algorithm for finding the smallest eigenvalue of a particular form of ill-conditioned Hankel matrix, which requires the use of extremely high precision arithmetic. Surprisingly, we find that commonly-used approaches that are designed for high efficiency are actually less efficient than a direct approach under these conditions. We then develop a parallel implementation of the algorithm that takes into account the unusually high cost of individual arithmetic operations. Our approach combines message passing and shared memory, achieving near-perfect scalability and high tolerance for network latency. We are thus able to find solutions for much larger matrices than has been previously possible, with the potential for extending this work to systems with greater levels of parallelism.
Introduction
The challenge of finding the smallest eigenvalue of large, dense, and symmetric Hankel matrices is central to "moment problems"—the reconstruction of probability distributions from statistical moments—and random matrix theory. However, these matrices are notoriously ill-conditioned. In numerical linear algebra, an ill-conditioned matrix is one where tiny input changes or rounding errors lead to massive output errors. For the specific family of matrices studied here, the condition number grows faster than $N^N$, rendering standard double-precision arithmetic (15-17 decimal digits) entirely inadequate. Solving these problems necessitates extended precision arithmetic, often requiring tens of thousands of bits of precision.
Methodology
Algorithm Selection
The researchers evaluated four standard algorithms under the unique constraints of ultra-high precision:
- Lanczos Algorithm: Typically the standard for eigenvalues, it proved unstable here, requiring over 200,000 bits of precision.
- Householder’s Algorithm: A standard transformation method.
- Jacobi Method: An iterative method for symmetric matrices.
- The Secant Algorithm: This direct approach emerged as the winner. It utilizes an $LDL^T$ decomposition (a variant of Cholesky factorization) to compute the determinant of $(M - xI)$ and a Secant root-finder to identify where the determinant equals zero.
Parallel Implementation
The Secant/$LDL^T$ approach was implemented using a hybrid parallel model to handle the computational load:
- MPI (Message Passing Interface): Distributed data across nodes in a Beowulf cluster.
- OpenMP: Parallelized computation across multiple cores within individual nodes.
- Latency Hiding: A dedicated background thread managed communication, broadcasting data for subsequent steps while the current computational step was still in progress.
Key Results and Insights
Efficiency in High Precision
In standard computing environments, iterative methods like Lanczos are preferred to avoid expensive matrix factorizations. However, at 20,000+ bits of precision, the "cost" of an algorithm shifts. The direct $LDL^T$ method required significantly fewer bits of precision to achieve the same accuracy as iterative methods, making it the most efficient choice.
As shown in the performance data, the Secant method consistently outperformed the Jacobi and Householder methods by factors of 4x to 16x for larger matrices. For example, at $N=400$, the Secant method completed in 603.84 seconds, while the Jacobi method took 9888.59 seconds.
Scalability and Latency
As the required precision ($K$) increases, arithmetic operation time grows quadratically ($O(K^2)$), while network data transfer time grows only linearly. This makes high-precision problems "CPU bound," allowing for near-perfect scalability. On a 240-core cluster, the algorithm achieved 91.2% computational efficiency for a $1500 \times 1500$ matrix, with only 8.4% of time lost to network latency.
Conclusion
By prioritizing a direct determinant-based approach over more complex iterative methods, the researchers successfully computed eigenvalues for matrices up to $2000 \times 2000$—a significant leap from previous benchmarks of $300 \times 300$. While memory constraints and network bottlenecks remain for smaller matrices or lower-precision cases, this approach demonstrates that extreme ill-conditioning can, paradoxically, be leveraged to achieve high parallel efficiency.
Summary updated