Computation of eigenvalues of Hankel matrices using multiprecision arithmetic

Abstract

The use of the fast Fourier transform (FFT) accelerates Lanczos tridiagonalisation method for Hankel and Toeplitz matrices by reducing the complexity of matrix–vector multiplication. In multiprecision arithmetics, the FFT has overheads that make it less competitive compared with alternative methods when the accuracy is over 10 000 decimal places. We studied two alternative Hankel matrix–vector multiplication methods based on multiprecision number decomposition and recursive Karatsuba-like multiplication, respectively. The first method was uncompetitive because of huge precision losses, while the second turned out to be five to 14 times faster than FFT in the ranges of matrix sizes up to n D 8192 and working precision of b D 32 768 bits we were interested in. We successfully applied our approach to eigenvalues calculations to studies of spectra of matrices that arise in research on Riemann zeta function. The recursive matrix–vector multiplication significantly outperformed both the FFT and the traditional multiplication in these studies.

Participants

Journal Articles

[1] Shaun Bangay and Gleb Beliakov. On the fast lanczos method for computation of eigenvalues of hankel matrices using multiprecision arithmetics. Numerical Linear Algebra with Applications, pages 485-500, 2016. nla.2035. [PDF] [BibTeX]

Images