Computing the smallest eigenvalue of large ill-conditioned Hankel matrices

Niall Emmart, Charles Weems, Yang ChenarXiv 2009 · DOI · arXiv

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.

Precision requirements (K) for various matrix sizes (N) and shape parameters (β).

Methodology

Algorithm Selection

The researchers evaluated four standard algorithms under the unique constraints of ultra-high precision:

  1. Lanczos Algorithm: Typically the standard for eigenvalues, it proved unstable here, requiring over 200,000 bits of precision.
  2. Householder’s Algorithm: A standard transformation method.
  3. Jacobi Method: An iterative method for symmetric matrices.
  4. 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.

Comparison of numerical algorithms for computing the smallest eigenvalue across different matrix sizes.

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

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.
BibTeX
@misc{emmart2009computing,
  author = {Niall Emmart and Charles Weems and Yang Chen},
  title = {{Computing the smallest eigenvalue of large ill-conditioned Hankel matrices}},
  year = {2009},
  eprint = {0902.0852},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0902.0852},
  howpublished = {arXiv},
}
Figure