Go backward to Problem Statement
Go up to Parallel Resultant Computation
Go forward to Parallel Algorithm
|
Go backward to Problem Statement Go up to Parallel Resultant Computation Go forward to Parallel Algorithm |
|
Collins [12] describes an efficient sequential algorithm for multivariate polynomial computation based on a modular approach: we use various prime numbers p to map the coefficients of A and B into modular domains Zp = {0,...,p-1}, i.e., we compute polynomials a=Mapp(A), b=Mapp(B) where
a, b inZp[x1,...,xr-1][xr].We may only use primes p such that degree(a)=degree(A) and degree(b) = degree(B) where degree(P) denotes the degree of polynomial P in the main variable. Using modular arithmetic in Zp, we compute the modular resultant c := Resultantp(a, b), i.e.,
c inZp[x1,...,xr-1].We then apply the Chinese Remainder Algorithm to lift the result from Zp to ZP*p, i.e.,
ChineseRemainder(C, c, P, p) inZP*p[x1,...,xr-1]where P is the product of the primes used so far and C is the combination of the corresponding modular resultants:
C inZP[x1,...,xr-1]The algorithm iterates until P exceeds a predetermined bound cb for the size of the coefficients of the resultant and then returns C. The algorithm is sketched below:
C := Resultant(A, B)
m := degree(A); n := degree(B)
cb := CoeffBound(A, B)
C := 0; P := 1
while P <= cb do
p := a new prime number;
if Am mod p != 0 /\ Bn mod p != 0 then
a := Mapp(A); b := Mapp(B)
c := Resultantp(a, b)
C := ChineseRemainder(C, c, P, p)
P := P*p
end
end
end Resultant