Newton’s Iteration and the Hensel Construction

K. O. Geddes, S. R. Czapor and G. Labahn
Additional contact information
K. O. Geddes: University of Waterloo
S. R. Czapor: Laurentian University
G. Labahn: University of Waterloo

Chapter Chapter 6 in Algorithms for Computer Algebra, 1992, pp 205-277 from Springer

Abstract: Abstract In this chapter we continue our discussion of techniques for inverting modular and evaluation homomorphisms defined on the domain Z[x 1, . . ., x v ]. The particular methods developed in this chapter are based on Newton's iteration for solving a polynomial equation. Unlike the integer and polynomial Chinese remainder algorithms of the preceding chapter, algorithms based on Newton's iteration generally require only one image of the solution in a domain of the form Z p [x 1] from which to reconstruct the desired solution in the larger domain Z[x 1, . . . , x v]. A particularly important case of Newton's iteration to be discussed here is the Hensel construction. It will be seen that multivariate polynomial computations (such as GCD computation and factorization) can be performed much more efficiently (in most cases) by methods based on the Hensel construction than by methods based on the Chinese remainder algorithms of the preceding chapter

Keywords: Iteration Step; Computer Algebra; Multivariate Polynomial; Prime Integer; Degree Constraint (search for similar items in EconPapers)
Date: 1992
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-0-585-33247-5_6

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

DOI: 10.1007/978-0-585-33247-5_6

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 ().