Go backward to Sequential Algorithm Go up to Parallel Resultant Computation Go forward to Implementation |
Various parallel versions of the modular algorithm have been investigated and implemented on shared memory machines [13] and on workstation networks [14]. Their common idea is to compute the resultants in the individual modular domains in parallel; they differ in their approaches to efficiently combine the modular resultants to yield the integer resultant. We apply the idea used by [13] where the sequential structure of the combination phase is maintained but the individual coefficients of the resultant are computed in parallel.
The parallel algorithm starts for each modular domain a task that maps A and B into this domain and computes the coefficients of the modular resultant (up to a predetermined degree bound db). The task results are collected and for each resultant coefficient a task is started that iteratively combines the corresponding modular coefficients. The task results are collected to build the overall result.
C := ResultantParallel(A, B)The structure of the algorithm is illustrated in Figure *.
m := degree(A); n := degree(B)
cb := CoeffBound(A, B)
db := DegreeBound(A, B)
C := 0; P := 1; T := [ ]; L := [ ]
while P <= cb do
p := a new prime number;
if Am mod p != 0 /\ Bn mod p != 0 then
t := start(ResultantModular, p, db, A, B)
P := P*p; T := T || [t]; L := L || [p]
end
end
R := WaitForAll(T)
T := [ ]
for i in[0 ...db] do
t := start(ChineseRemainderCoeff, L,
[R[j]i | j in[1...length(R)])
T := T || [t]
end
C := WaitForAll(T)
end ResultantParallel