Exploring and extending eigensolvers for Toeplitz(-like) matrices : A study of numerical eigenvalue and eigenvector computations combined with matrix-less methods

Sammanfattning

We implement an eigenvalue solving algorithm proposed by Ng and Trench, specialized for Toeplitz(-like) matrices, utilizing root finding in conjunction with an iteratively calculated version of the characteristic polynomial. The solver also yields corresponding eigenvectors as a free bi-product. We combine the algorithm with matrix-less methods in order to yield eigenvector approximations, and examine its behavior both regarding demands for time and computational power. The algorithm is fully parallelizable, and although solving of all eigenvalues to the bi-Laplacian discretization matrix - which we used as a model matrix - is not superior to standard methods, we see promising results when using it as an eigenvector solver, using eigenvector approximations from standard solvers or a matrix-less method. We also note that an advantage of the algorithm we examine is that it can calculate singular, specific eigenvalues (and the corresponding eigenvectors), anywhere in the spectrum, whilst standard solvers often have to calculate all eigenvalues, which could be a useful feature. We conclude that - while the algorithm shows promising results - more experiments are needed, and propose a number of topics which could be studied further, e.g. different matrices (Toeplitz-like, full), and looking at even larger matrices.