Matrix-less spectral approximation for large structured matrices

Abstract Sequences of structured matrices of increasing size, such as generalized locally Toeplitz sequences, arise in many scientific applications and especially in the numerical discretization of linear differential problems. We assume that the eigenvalues of a matrix $$X_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> , belonging to a sequence of such kind, are given by a regular expansion. Under this working hypothesis, we propose a method for computing approximations of the eigenvalues of $$X_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> for large n and we provide a theoretical analysis of its convergence. The method is called matrix-less because it does not operate on the matrix $$X_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> but on a few similar matrices of smaller size combined with an interpolation-extrapolation strategy. The working hypothesis and the performance of the proposed eigenvalue approximation method are benchmarked on several numerical examples, with a special attention to matrices arising from the discretization of variable-coefficient differential problems.