×

On the fast Lanczos method for computation of eigenvalues of Hankel matrices using multiprecision arithmetics. (English) Zbl 1413.65089

Summary: 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 \(10000\) 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=8192\) and working precision of \(b=32768\) 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.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15B05 Toeplitz, Cauchy, and related matrices
65T50 Numerical methods for discrete and fast Fourier transforms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Golub, Matrix Computations (1996)
[2] Bai, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (2000) · Zbl 0965.65058 · doi:10.1137/1.9780898719581
[3] Saad, Numerical Methods for Large Eigenvalue Problems (2011) · Zbl 1242.65068 · doi:10.1137/1.9781611970739
[4] Heinig, Fast algorithms for Toeplitz and Hankel matrices, Linear Algebra and its Applications 435 pp 1– (2011) · Zbl 1211.65035 · doi:10.1016/j.laa.2010.12.001
[5] Wang, A fast eigenvalue algorithm for Pascal matrices, Applied Mathematics and Computation 183 pp 711– (2006) · Zbl 1109.65033 · doi:10.1016/j.amc.2006.05.093
[6] Luk, A fast eigenvalue algorithm for Hankel matrices, Linear Algebra and its Applications 316 pp 171– (2000) · Zbl 0959.65056 · doi:10.1016/S0024-3795(00)00084-7
[7] Luk FT Qiao S Analysis of a fast Hankel eigenvalue algorithm Proceedings of the SPIE 3807, Advanced Signal Processing Algorithms, Architectures, and Implementations IX Denver, USA 1999 324 333 10.1117/12.367649
[8] Matiyasevich Yu Hidden life of Riemann’s zeta function 2. Electrons and trains 2007
[9] Matiyasevich Yu The Riemann hypothesis and eigenvalues of related Hankel matrices. Preprint 03/2014 of Steklov Institute of Mathematics at St.Petersburg 2014 http://www.pdmi.ras.ru/preprint/2014/14-03.html
[10] GNU. GNUMP library http://gmplib.org
[11] Fousse, MPFR: a multiple-precision binary floating-point library with correct rounding, ACM Transactions on Mathematical Software 33: (2007) · Zbl 1365.65302 · doi:10.1145/1236463.1236468
[12] Johansson F Arb library http://fredrikj.net/arb/
[13] Bailey D Arprec library http://crd-legacy.lbl.gov/ dhbailey/mpdist/
[14] Advanpix. Matlab multiprecision computing toolbox http://www.advanpix.com/
[15] Borgerding M Kiss FFT http://sourceforge.net/projects/kissfft/
[16] Beliakov G On fast matrix-vector multiplication with a Hankel matrix in multiprecision arithmetics 2014
[17] Borwein, CMS Books in Mathematics,, in: The Riemann Hypothesis: A Resource for the Afficionado and Virtuoso Alike. (2008) · Zbl 1132.11047 · doi:10.1007/978-0-387-72126-2
[18] Clay Institute The millennium prize problems 2013 http://www.claymath.org/millennium/
[19] Matiyasevich Yu Hidden life of Riemann’s zeta function. 1. Arrow, bow, and targets 2007
[20] Beliakov, Approximation of Riemann’s zeta function by finite Dirichlet series: a multiprecision numerical approach, Experimental Mathematics 24 pp 1– (2015) · Zbl 1381.11075 · doi:10.1080/10586458.2014.976801
[21] Beliakov, A parallel algorithm for calculation of the determinants and minors using arbitrary precision arithmetics, BIT Numerical Mathematics (2015)
[22] Arbenz P Numerical methods for solving large scale eigenvalue problems, online lecture notes http://people.inf.ethz.ch/arbenz/ewp/lnotes.html
[23] Gu, A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM Journal on Matrix Analysis and Applications 16 pp 172– (1995) · Zbl 0815.65050 · doi:10.1137/S0895479892241287
[24] Demmel, Applied Numerical Linear Algebra (1997) · doi:10.1137/1.9781611971446
[25] Karatsuba, Multiplication of many-digital numbers by automatic computers, Proceedings of the USSR Academy of Sciences (Translation in the academic journal Physics Doklady, 7 (1963), pp. 595-596) 145 pp 293– (1962)
[26] Cormen T Leiserson C Rivest R Stein C Introduction to algorithms MIT Press Cambridge, MA 2009
[27] Cariow, Fast algorithms to compute matrix-vector products for Toeplitz and Hankel matrices, PRZEGLAD ELEKTROTECHNICZNY (Electrical Review) 88 pp 166– (2012)
[28] Simon, The Lanczos algorithm with partial reorthogonalization, Mathematics of Comping 42 pp 115– (1984) · Zbl 0546.65017 · doi:10.1090/S0025-5718-1984-0725988-X
[29] Simon, Analysis of the symmetric Lanczos algorithm with reorthogonalization methods, Linear Algebra and its Applications 61 pp 101– (1984) · Zbl 0579.65030 · doi:10.1016/0024-3795(84)90025-9
[30] Matiyasevich Yu Numerical study of Riemann’s zeta functions via determinants http://logic.pdmi.ras.ru/ yumat/talks/muenchen_2014/index.php
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.