Semi-analytical solutions for eigenvalue problems of chains and periodic graphs

Highlights：

• Our manuscript presents a semi-analytical approach to evaluate eigenvalues of sparse matrices with certain periodicity in entries. We first show the existence and nature of convergence to a limiting set of roots for a three-term polynomial recurrence of interest. The relations for the limiting set of roots are extended for a finite length of the recurrence. These roots represent the eigenvalues of tridiagonal (k-Toeplitz) matrices with any given periodicity k in the entries. Kronecker products and sums applied on these matrices represent spatial lattices and other periodic graphs, and thus the semi-analytical approach is extended to such matrices using the spectral rules of Kronecker operations. This method costs only O(N) arithmetic operations for a matrix of dimension N, for a given k. Further, for sufficiently large values of N, this method is more accurate than the direct numerical methods which are shown to incur large relative errors.

摘要

•Our manuscript presents a semi-analytical approach to evaluate eigenvalues of sparse matrices with certain periodicity in entries. We first show the existence and nature of convergence to a limiting set of roots for a three-term polynomial recurrence of interest. The relations for the limiting set of roots are extended for a finite length of the recurrence. These roots represent the eigenvalues of tridiagonal (k-Toeplitz) matrices with any given periodicity k in the entries. Kronecker products and sums applied on these matrices represent spatial lattices and other periodic graphs, and thus the semi-analytical approach is extended to such matrices using the spectral rules of Kronecker operations. This method costs only O(N) arithmetic operations for a matrix of dimension N, for a given k. Further, for sufficiently large values of N, this method is more accurate than the direct numerical methods which are shown to incur large relative errors.