Matrix-less methods for the spectral approximation of large non-Hermitian Toeplitz matrices: A concise theoretical analysis and a numerical study

It is known that the generating function of a sequence of Toeplitz matrices may not describe the asymptotic distribution of the eigenvalues of the considered matrix sequence in the non-Hermitian setting. In a recent work, under the assumption that the eigenvalues are real, admitting an asymptotic expansion whose first term is the distribution function, fast algorithms computing all the spectra were proposed in different settings. In the current work, we extend this idea to non-Hermitian Toeplitz matrices with complex eigenvalues, in the case where the range of the generating function does not disconnect the complex field or the limiting set of the spectra, as the matrix-size tends to infinity, has one nonclosed analytic arc. For a generating function having a power singularity, we prove the existence of an asymptotic expansion, that can be used as a theoretical base for the respective numerical algorithm. Different generating functions are explored, highlighting different numerical and theoretical aspects; for example, non-Hermitian and complex symmetric matrix sequences, the reconstruction of the generating function, a consistent eigenvalue ordering, the requirements of high-precision data types. Several numerical experiments are reported and critically discussed, and avenues of possible future research are presented.