Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T15:18:41.451Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing the Smallest Eigenvalue of Large Ill-Conditioned Hankel Matrices

Part of: Numerical linear algebra Nontrigonometric harmonic analysis Computer aspects of numerical algorithms Special matrices Error analysis and interval analysis

Published online by Cambridge University Press:  03 July 2015

Niall Emmart ,
Yang Chen  and
Charles C. Weems
Niall Emmart*
Affiliation:
College of Information and Computer Science, University of Massachusetts, Amherst, MA 01002, USA
Yang Chen
Affiliation:
Department of Mathematics, University of Macau, Macau, China
Charles C. Weems
Affiliation:
College of Information and Computer Science, University of Massachusetts, Amherst, MA 01002, USA
*
*Corresponding author. Email addresses: [email protected] (N. Emmart), [email protected] (Y. Chen), [email protected] (C. C.Weems)
Get access

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 are 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

Parallel eigensolverHankel matricesextremely ill-conditioned matrices

MSC classification

Secondary: 15B52: Random matrices 15B57: Hermitian, skew-Hermitian, and related matrices 42C05: Orthogonal functions and polynomials, general theory 65F15: Eigenvalues, eigenvectors 65G30: Interval and finite arithmetic 65Y05: Parallel computation
Type
Research Article
Information
Communications in Computational Physics , Volume 18 , Issue 1 , July 2015 , pp. 104 - 124
Copyright
Copyright © Global-Science Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Akhiezer, N. I., The classical moment problem and some related questions in analysis, Oliver and Boyd, Edinburgh, 1965.Google Scholar
[2]Anderson, G. W., Guionnet, A. and Zeitouni, O., An introduction to random matrices, The University Press, Cambridge, 2010.Google Scholar
[3]Bai, Z., Chen, Y. and Liang, Y.-C., Random matrix theory and its applications, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore. Vol. 18, 2009.Google Scholar
[4]Berg, C., Chen, Y. and Ismail, M.E.H., Small eigenvalues of large Hankel matrices: the indeterminate case, Math. Scand., vol. 91, 67–81, 2002.Google Scholar
[5]Blower, G., Random Matrices: High dimensional phenomena, The Univeristy Press, Cambridge, 2009.Google Scholar
[6]Berg, C. and Szwarc, R., The smallest eigenvalue of Hankel matrices, Constructive Approximation, vol. 34, 107–133, 2011.CrossRefGoogle Scholar
[7]Burden, R. L., Faires, J. D., Numerical Analysis, 4th edition. PWS-KENT Publishing Company, Boston, Massachusetts, 1989.Google Scholar
[8]Chen, Y., Haq, N. and McKay, M., Random matrix models, double-time Painleve equations, and wireless relaying, J. Math. Phys., vol. 54, 063506, 2013.Google Scholar
[9]Chen, Y. and Lawrence, N.D., Small eigenvalues of large Hankel matrices, J. Phys. A: Math. Gen., vol. 32, 7305–7315, 1999.Google Scholar
[10]Chen, Y. and Lubinsky, S.D., Smallest eigenvalues of Hankel matrices for exponential weights, J. Math. Anal. Appl., vol. 293, 476-495, 2004.Google Scholar
[11]Chen, Y. and McKay, M., Coulomb fluid, Painlevé Transcendents, and the information theory of MIMO systems, IEEE Trans. Information Theory, vol. 58, 4594–4634, 2012.Google Scholar
[12]Dharmawansa, P., McKay, M. and Chen, Y., Distributions of Demmel and Related Condition Numbers, Siam J. Matrix Anal., vol. 34, 257–279, 2012.Google Scholar
[13]Demmel, J. W., Heath, M. T., van der Vorst, H. A.. Parallel Numerical Linear Algebra, ACTA Numerica, 1992.Google Scholar
[14]GNU Open Source Community. The GNU Multiple Precision Arithmetic Library. http://www.gmplib.orgGoogle Scholar
[15]Kerov, S. V., Asymptotic representation theory of symmetric group and its application in analysis, American Mathematical Society, 2003.Google Scholar
[16]Krein, M. G. and Nudelman, A. A.. Markov moment problems and extremal problems, American Mathematical Society, 1977.Google Scholar
[17]Li, S., Mckay, M. and Chen, Y., On the distribution of MIMO mutual information: An indepth Painlevé based characterization, IEEE Trans. Information Theory, vol. 59, 5271–5296, 2013.Google Scholar
[18]Lubinsky, D. S., Condition of Hankel matrices for exponential weights, J. Math. Anal. Appl., vol. 314, 266285, 2006.Google Scholar
[19]Mehta, M. L., Random Matrices, 3rd edition. Elsevier, Singapore, 2006.Google Scholar
[20]Moore, R. E., Interval Analysis. Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1966.Google Scholar
[21]Parlett, B. N., The Symmetric Eigenvalue Problem, Classics in Applies Mathematics; 20. Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1997.Google Scholar
[22]Stoer, J., Bulirsch, R., Introduction to Numerical Analysis, 3rd edition. Texts in Applied Mathematics 12. Springer Science and Business Media, LLC, New York, New York, 2002.Google Scholar
[23]Quadeer, A. A., Louie, R. H., Shekhar, K., Chakraborty, A. K., Hsing, M., Mckay, M. R., Statistical linkage analysis of substitutions in patient-derived sequences of genotype 1a Hepatitis C Virius non-structural protein 3 exposes targets for immunogen design. J. Virology, 2014, Apr. 23.Google Scholar
[24]Szegö, G., On some Hermitian forms associated with two given curves of the complex plane, Trans. Amer. Math. Soc., vol. 40, 450–461, 1936.Google Scholar
[25]Widom, H., Rapidly Increasing Kernels, Proc. Amer. Math. Soc. vol., 14, 501–506, 1963.Google Scholar
[26]Widom, H. and Wilf, H., Small eigenvalues of large Hankel matrices, Proc. Amer. Math. Soc., vol. 17, 338–344, 1966.Google Scholar