Newton Algebraic Iteration and Newton-Structured Algebraic Iteration

Victor Y. Pan
Additional contact information
Victor Y. Pan: Lehman College, CUNY, Department of Mathematics and Computer Science

Chapter Chapter 7 in Structured Matrices and Polynomials, 2001, pp 219-239 from Springer

Abstract: Abstract 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.

Keywords: Formal Power Series; Minimum Polynomial; Integer Matrix; Integer Matrice; Krylov Space (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-0129-8_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461201298

DOI: 10.1007/978-1-4612-0129-8_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().