Computations with infinite Toeplitz matrices and polynomials (Q1348083)

Polynomial computations are related with operations involving infinite band Toeplitz matrices in a unifying framework with a systematic treatment of theory and algorithms. Applications to the numerical solution of Markov chains, of nonlinear matrix equations, to spectral factorizations and to the solution of finite Toeplitz systems are shown. The main technique introduced for the analysis of these computational problems is the Graeffe iteration. The matrix formulation of this iteration is expressed in terms of bi-infinite banded Toeplitz matrices and applied for the design of efficient bi-infinite Toeplitz solvers. A modification of the Graeffe's iteration is introduced which has a much wider set of applications, and which applies in particular to matrix polynomials of degree 2. The modified Graeffe iteration and its matrix version are extended to matrix power series and to (bi-)infinite (or to finite) block Hessenberg block Toeplitz matrices. The generalized Graeffe iteration and the corresponding matrix version cyclic reduction is applied to the design of effective algorithms for the solution of banded Toeplitz systems, nonlinear matrix equations, polynomial factorization problems, and solution of resultant-like systems.