Next: Bibliography Up: Advanced Computer Algebra: From Newton Previous: Hensel Lifting

# Solving polynomial equations via Newton iteration

Let R be a commutative ring R with units. Let p R and R[y]. We are concerned with solving the equation

 (g)  =  0. (120)

The following Proposition 10 states that Relation (122) computes better and better approximations of solutions of Relation (120) that is, approximations modulo higher and higher powers of p.

Proposition 10   Let R[y], k and g, h R be such that

 (g)   0 modpk (121)

Assume that (g) is invertible modulo p and let denote by (g)-1 its inverse. Consider an element h R such that

 h   g - (g) (g)-1modp2 k (122)

Then the following assertions hold
1. (g  0 modp2 k
2. h   g modpk
3. (h) is invertible modulo p

Remark 18   Intuitively, Proposition 10 says that if g is a good approximation of a zero of then h is a better approximation, at least twice as accurate.

Remark 19   Proposition 10 leads to an algorithm provided that we can
• check whether (g) is invertible modulo p and
• compute its inverse modulo p in case.
Then for computing the inverse of (h) modulo p the idea is to apply the algorithm to itself! That is, to the particular case of

 (g)  =  1/g - f (123)

This leads to Algorithm 9. Finally recall that for a prime element p in an Euclidean domain R, the computation of (g)-1 modulo p can be done by the Extended Euclidean Algorithm.

Algorithm 9

Theorem 14   Algorithm 9 is correct.

Proof. Let gr   gr-1 - (gr-1)sr-1modp2r. Then we have

 g   gr modp (124)

In other words gr is a solution of higher precision. Then proving the theorem turns into proving the invariants for i = 0 ... r
1. gi   g0modp,
2. (gi  0 modp2i,
3. if i < r then si (gi  1 modp2i.
The case i = 0 is clear and we assume that i > 0 holds. Then by induction hypothesis p2i-1 divides
(gi-1)
si-1 - (gi-1)-1
Then p2i divides their product, that is

 (gi-1si-1   (gi-1)(gi-1)-1 modp2i. (125)

Now we calculate

 gi gi-1 - (gi-1)si-1 modp2i gi-1 - (gi-1)(gi-1)-1 modp2i
(126)

Now applying Proposition 10 with g = gi, h = gi and k = 2i-1 we obtain the first two invariants.

...

Remark 20   The general mutivariate Newton iteration works as follows. Let = (,...,) be a function in n variables y1,..., yn. From an approximation a n to a commo root of ,..., we obtain a better one a * with

 a *   =  a - J-1(a) (a) (127)

where J is the Jacobian matrix of . The Hensel lifting can be considered as a special case of Newton iteration as follows.
• Consider the coefficients of g and h in a factorization f = g h as indeterminates.
• Comparing the coefficients of 1, x, x2,... lead to a system of n equations and n unknowns whose solution leads to a factorization of f.
• The invertibility of J is equivalent to the coprimality of f and g. Indeed J is exactly the Sylvester matrix of f and g. Hence, its determinant is the resultant of f and g.

Next: Bibliography Up: Advanced Computer Algebra: From Newton Previous: Hensel Lifting
Marc Moreno Maza
2003-06-06