Estimating the extremal eigenvalues of a symmetric matrix (Q753418)

For an \(n\times n\) real symmetric non-singular matrix A and a natural number m the author proposes an algorithm to approximate the values of trace \(A^ m\) and trace \(A^{-m}\) (that enables us to estimate the two absolutely extremal eigenvalues \(\lambda_ 1\) and \(\lambda_ n\) of the matrix A; \(| \lambda_ 1| =\max \{| \lambda_ i| \}\), \(| \lambda_ n| =\min \{| \lambda_ i| \}\) for \(i=1,2,...,n)\). Instead of the powers of A, the algorithm needs to calculate traces of matrices of the form \((p_ rI-A)^{-1}\) for \(r=0,1,...,Q-1\), where \(Q>m\) is an integer, \(p_ r=H\omega^ r\), \(H<| \lambda_ 1|\) being a real number and \(\omega\) being a primitive Q-th root of 1 \((\omega^ Q=1\), \(\omega^ r\neq 1\) for \(0<r<Q).\) The algorithm is analyzed for some special classes of matrices: if A is a Hermitian or real Toeplitz matrix, its time complexity is of the order of O(mn log\({}^ 2n)\); for Toeplitz-like matrices having a small displacement rank d, it is of the order of \(O(md^ 2n \log^ 2n)\). For bounded matrices with lower bandwidth w and upper bandwidth \(w^*\) (i.e. \(a_{ij}=0\) for \(i-j>w\) or \(j-i>w^*)\), the cost is of the order of \(O((w+w^*)^ 2mn)\), but in the case when A is a strongly diagonally dominant matrix, the algorithm needs some modifications increasing the cost about log n times to guarantee its numerical stability. Finally, for symmetric positive definite matrix A having O(\(\sqrt{n})\)- separator tree, the algorithm needs \(O(mn^ 2)\) arithmetic operations. With about the same cost the method gives approximations of trace \(A^ s\) simultaneously for all s between -m and m. Th classical algorithms, calculating powers of A, involve O(log m) matrix multiplications, i.e. \(O(n^ 3\log m)\) arithmetic operations in general case. The space cost of the algorithm is of the same order as input data, i.e. \(O(n^ 2).\) The author analyzes also the numerical stability of the algorithm in dependence of the magnitude of the parameter H.