Newton Algebraic Iteration and Newton-Structured Algebraic Iteration

Newton iteration is a fundamental tool of computer algebra. We specify this iteration for the general problem of algebraic rootfinding and apply it first to the solution of some important problems of computations with polynomials and integers. Then it is applied to computations with general and structured matrices M: we compute the characteristic polynomial det(xI — M), the minimum polynomial, the inverse M−1, and the Krylov matrix K(M, v, q) (for a vector v and a positive integer q). The matrix computation algorithms are fast (although not always superfast) and allow most effective parallelization. For the inversion of matrices filled with integers or rational numbers, Newton's algebraic iteration enables dramatic decrease of the precision of the computations. If in addition, the input matrix is structured, then the algorithm reaches the superfast level in terms of its bit-operation complexity, which is nearly linear in the bit-complexity of the representation of the output. That is, Newton's algebraic iteration nearly reaches optimality. The approach requires computations modulo a random prime and its powers, to avoid singularities. For some problems the algorithm is nearly optimal also in terms of arithmetic complexity. At the end of the chapter, in particular in Exercise 7.15, we briefly recall some advanced techniques that yield effective parallelization of the superfast sequential computations with integer Toeplitz-like matrices.