A fast implicit QR algorithm for eigenvalue computation of low rank corrections of unitary matrices is adjusted to work with matrix pencils arising from polynomial zerofinding problems . The modified QZ algorithm computes the generalized eigenvalues
of certain NxN rank structured matrix pencils using O(N^2) ops and O(N) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.
We extend previous results on the exponential off-diagonal decay of the entries of analytic functions of banded and sparse matrices to the case where the matrix entries are elements of a $C^*$-algebra.
Motivated by applications in quantum chemistry and solid state physics, we apply general results from approximation theory and matrix analysis to the study of the decay properties of spectral projectors associated with large and sparse Hermitian matr
ices. Our theory leads to a rigorous proof of the exponential off-diagonal decay (nearsightedness) for the density matrix of gapped systems at zero electronic temperature in both orthogonal and non-orthogonal representations, thus providing a firm theoretical basis for the possibility of linear scaling methods in electronic structure calculations for non-metallic systems. We further discuss the case of density matrices for metallic systems at positive electronic temperature. A few other possible applications are also discussed.
We study a variant of the univariate approximate GCD problem, where the coefficients of one polynomial f(x)are known exactly, whereas the coefficients of the second polynomial g(x)may be perturbed. Our approach relies on the properties of the matrix
which describes the operator of multiplication by gin the quotient ring C[x]=(f). In particular, the structure of the null space of the multiplication matrix contains all the essential information about GCD(f; g). Moreover, the multiplication matrix exhibits a displacement structure that allows us to design a fast algorithm for approximate GCD computation with quadratic complexity w.r.t. polynomial degrees.
