Go backward to Sequential Algorithm Go up to Parallel Resultant Computation Go forward to Implementation

Parallel Algorithm

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)
   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 A_m mod p != 0 /\ B_n 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