Volume 18, Issue 1
Computing the Smallest Eigenvalue of Large Ill-Conditioned Hankel Matrices

Niall Emmart, Yang Chen & Charles C. Weems

Commun. Comput. Phys., 18 (2015), pp. 104-124.

Published online: 2018-04

Preview Full PDF 486 1519
Export citation
  • Abstract

This paper presents a parallel algorithm for finding the smallest eigenvalue of a family of Hankel matrices that are ill-conditioned. Such matrices arise in random matrix theory and require the use of extremely high precision arithmetic. Surprisingly, we find that a group of commonly-used approaches that are designed for high efficiency 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 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 previously possible, with the potential for extending this work to systems with greater levels of parallelism. The contributions of this work are in three areas: determination that a direct algorithm based on the secant method is more effective when extreme fixed-point precision is required than the algorithms more typically used in parallel floating-point computations; the particular mix of optimizations required for extreme precision large matrix operations on a modern multi-core cluster, and the numerical results themselves.

  • Keywords

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CiCP-18-104, author = {}, title = {Computing the Smallest Eigenvalue of Large Ill-Conditioned Hankel Matrices}, journal = {Communications in Computational Physics}, year = {2018}, volume = {18}, number = {1}, pages = {104--124}, abstract = {

This paper presents a parallel algorithm for finding the smallest eigenvalue of a family of Hankel matrices that are ill-conditioned. Such matrices arise in random matrix theory and require the use of extremely high precision arithmetic. Surprisingly, we find that a group of commonly-used approaches that are designed for high efficiency 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 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 previously possible, with the potential for extending this work to systems with greater levels of parallelism. The contributions of this work are in three areas: determination that a direct algorithm based on the secant method is more effective when extreme fixed-point precision is required than the algorithms more typically used in parallel floating-point computations; the particular mix of optimizations required for extreme precision large matrix operations on a modern multi-core cluster, and the numerical results themselves.

}, issn = {1991-7120}, doi = {https://doi.org/10.4208/cicp.260514.231214a}, url = {http://global-sci.org/intro/article_detail/cicp/11020.html} }
TY - JOUR T1 - Computing the Smallest Eigenvalue of Large Ill-Conditioned Hankel Matrices JO - Communications in Computational Physics VL - 1 SP - 104 EP - 124 PY - 2018 DA - 2018/04 SN - 18 DO - http://doi.org/10.4208/cicp.260514.231214a UR - https://global-sci.org/intro/article_detail/cicp/11020.html KW - AB -

This paper presents a parallel algorithm for finding the smallest eigenvalue of a family of Hankel matrices that are ill-conditioned. Such matrices arise in random matrix theory and require the use of extremely high precision arithmetic. Surprisingly, we find that a group of commonly-used approaches that are designed for high efficiency 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 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 previously possible, with the potential for extending this work to systems with greater levels of parallelism. The contributions of this work are in three areas: determination that a direct algorithm based on the secant method is more effective when extreme fixed-point precision is required than the algorithms more typically used in parallel floating-point computations; the particular mix of optimizations required for extreme precision large matrix operations on a modern multi-core cluster, and the numerical results themselves.

Niall Emmart, Yang Chen & Charles C. Weems. (2020). Computing the Smallest Eigenvalue of Large Ill-Conditioned Hankel Matrices. Communications in Computational Physics. 18 (1). 104-124. doi:10.4208/cicp.260514.231214a
Copy to clipboard
The citation has been copied to your clipboard