Go backward to Distributed MapleGo up to TopGo forward to Conclusions |

As discussed in Section *, one of the most time-consuming
components of the CASA function `pacPlot`

is the computation of
multi-variate polynomial resultants. In this section, we are going to describe
the problem, a sequential solution algorithm, a parallel version of this
algorithm, and our implementation of this algorithm in Distributed Maple. We
conclude by listing benchmark results that demonstrate the actual efficiency
of the parallel solution.

Let *A=SUM _{i=0}^{m}A_{i} x^{i}* and

The Sylvester matrix ofA, B inI[x]

whose upper part consists of

A _{m}A _{m-1}... A _{0}... ... ... ... A _{m}A _{m-1}... A _{0}B _{n}B _{n-1}... B _{0}... ... ... ... B _{n}B _{n-1}... B _{0}

Resultant(A,B) inI.

In the context of the plotting of algebraic curves, we are interested in the
special case where *A* and *B* are polynomials in *r* variables over the
integers, i.e., given

we want to findA,B inZ[x_{1},...,x_{r-1}][x_{r}]

For plotting algebraic curves in two dimensions, we have to solve this problem forResultant(A,B) inZ[x_{1},...,x_{r-1}].

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 * Z_{p} =
{0,...,p-1}*, i.e., we compute polynomials

We may only use primesa, b inZ_{p}[x_{1},...,x_{r-1}][x_{r}].

We then apply the Chinese Remainder Algorithm to lift the result fromc inZ_{p}[x_{1},...,x_{r-1}].

whereChineseRemainder(C, c, P, p) inZ_{P*p}[x_{1},...,x_{r-1}]

The algorithm iterates untilC inZ_{P}[x_{1},...,x_{r-1}]

C:= Resultant(A,B)

m:= degree(A);n:= degree(B)

:= CoeffBound(cbA,B)

C:=0;P:=1

whileP <=cbdo

p:= a new prime number;

ifA_{m}mod p != 0 /\ B_{n}mod p != 0then

a:= Map;_{p}(A)b:= Map_{p}(B)

c:= Resultant(_{p}a,b)

C:= ChineseRemainder(C,c,P,p)

P:=P*p

end

endend Resultant

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.

The structure of the algorithm is illustrated in Figure *.C:= ResultantParallel(A,B)

m:= degree(A);n:= degree(B)

:= CoeffBound(cbA,B)

:= DegreeBound(dbA,B)

C:=0;P:=1;T:=[ ];L:=[ ]

whileP <=cbdo

p:= a new prime number;

ifA_{m}mod p != 0 /\ B_{n}mod p != 0then

t:= start(ResultantModular,p,,dbA,B)

P:=P*p;T:=T || [t];L:=L || [p]

end

end

R:= WaitForAll(T)

T:=[ ]

fori 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

We have implemented above algorithm for *r=2* using
the Distributed Maple constructs `dist[start]`

and
`dist[wait]`

. Furthermore, we have replaced the Maple function
`resultant/bivariate`

(which is called by Maple
for computing the resultants of bivariate polynomials) by a version that uses
our parallel implementation if the degrees of both input polynomials in the
main variable are are greater than five and the degree of one input polynomial
is greater than ten. All other cases are still solved by sequential methods.

The implementation differs from above algorithm in that each task computes multiple modular resultants respectively multiple coefficients of the integer resultant. By adjusting the number of elements computed by a task we can effectively control its grain size.

For estimating the execution time of a "ResultantModular" task we use the complexity bound [12]

where

(1+max(degree _{r}(A), degree_{r}(B)))*PROD _{i=1}^{r}(1+max(degree_{i}(A), degree_{i}(B)))*SUM _{i=1}^{r}(1+max(degree_{i}(A), degree_{i}(B)))

We also adjust the number of coefficients computed per "ChineseRemainderCoeff" task such that it processes for any input a constant number of modular coefficients. We have experimentally determined a value for this constant (1800) such that the execution time of a the task roughly matches the execution time of a "ResultantModular" task.

The first four modular resultants are actually computed sequentially in order to derive an improved value for the degree bound such that fewer coefficients have to be considered in the rest of the algorithm.

We have benchmarked our implementation with numerous inputs and machine configurations; the results of some of these experiments are shown below. The system environment in which the parallel program has been executed consists of (various subsets of) the following machines:

- 8 Linux PCs (1 Pentium at 350 Mhz, 2 Pentium at 333 Mhz, 5 Pentium at 266Mhz),
- 4 Silicon Graphics Octane multiprocessors (2 R10000 at 250 Mhz each),
- 1 Sun Ultrasparc workstation (1 Sparc at 296 Mhz),
- 1 Silicon Graphics Origin multiprocessor (32 R10000 at 195MHz, 7 processors used).

We have applied the CASA function `pacPlot`

to four algebraic curves
represented by the randomly generated bivariate polynomials listed in
Figure * and have measured the execution times of the corresponding
resultant computations (using the sequential resultant function provided by
Maple and our parallel version). The results are listed in Figure *
and visualized in Figure *.

Name Tot.Deg. Value 9-11-3 14 23x^{4}y^{8}-17x^{6}y^{6}+22x^{8}+84x^{7}y^{7}+20x^{4}y^{6}-49x^{3}y^{8}-80x^{4}y^{2}-5x^{3}y-92x^{3}y^{2}-47y^{8}+5xy^{5}10-7-2 13 55x^{8}y^{2}+66x^{9}y^{4}+27y^{3}+31x^{2}y^{5}-75x^{2}y^{6}-70y^{8}-97x^{2}y^{9}10-8-2 18 -22x^{9}y^{9}-26x^{2}y^{5}+85x^{8}y-50x^{2}y^{6}-74x^{6}y^{4}-31x^{8}y^{7}-172x^{7}y^{7}12-7-2 20 99xy^{9}-12x^{6}y^{2}-26x^{2}y^{11}-47x^{8}y^{11}-61x^{5}y^{8}-90x^{9}y^{11}+94x^{2}y

Processors Performance Time (s) 9-11-3 10-7-2 10-8-2 12-7-2 Sequential 1 634 214 84 1267 1 0.73 958 317 122 1920 2 1.73 386 135 53 746 3 2.73 251 91 35 477 4 3.46 192 72 36 370 8 6.48 112 47 25 204 12 9.66 88 43 25 143 16 12.1 73 35 26 111 20 15.34 73 29 24 93 24 17.99 66 29 24 84

The largest speedup was 15 (compared to a sequential execution time of 1267 seconds) with 24 processors, which corresponds to an efficiency of more than 80% (considering the total system performance). All four examples achieved an efficiency of at least 50% with 8 processors, three examples achieved an efficiency of at least 50% with 20 processors. The example that ran shortest (sequential execution time of 84 seconds) achieved a maximum speedup of 3.5 with 8 processors (50% efficiency).

Machines

Tasks

Utilization

The visualization of a program run shown in Figure * (curve
12-7-2, 24 processors) gives an impression of the dynamic behavior of the
algorithm (the diagrams have been produced from a trace file generated by the
scheduler on issuing the Maple command `dist[trace]`

). The left figure
shows the load of each machine, the middle figure displays all tasks, and the
right figure shows the machine utilization during the computation of the
resultant.

We see that a very short initial phase where only one machine is active (the sequential computation of four modular resultants) is followed by a long phase where all machines are active computing modular resultants in parallel. This phase is followed by a shorter phase where only part of the machines are active combining the coefficients of the modular resultants by the Chinese Remainder Algorithm. Since tasks have been calibrated to run about 10 seconds, there is not sufficiently much parallelism to keep all machines active in this phase.

The fact that some of the Chinese Remainder tasks seem to execute significantly longer than other tasks can be attributed to the fact that exactly these tasks are on Linux PCs: while the raw (integer) processing power of these machines is larger than those of all other machines, their communication bandwidth (external sockets and/or internal pipes) is apparently much lower. Since the Chinese Remaindering tasks receive very large input arguments, they start execution on these PCs later than on other machines and/or need more time to transfer their results. This is also the reason why we choose to run the initial Maple kernel of a Distributed Maple session on a (otherwise slower) Silicon Graphics workstation; this gives much better overall speedups. We are currently investigating whether the installation of newer versions of the Linux operating system kernel may help to overcome this communication bottleneck.

It is interesting to note that our implementation is based on parallelization constructs that correspond to those of the parallel computer algebra library PACLIB where a similar parallel version of the modular resultant algorithm was implemented in C [13]. Likewise this parallel algorithm was implemented in the para-functional language pD which was compiled to C code that used the PACLIB runtime system [5]. The PACLIB implementation on a shared memory multiprocessor (16 Intel386 at 20 Mhz) achieved a speedup of 11.5 for a problem whose sequential execution time was 180 seconds [13]. The pD implementation achieved a speedup of 11.5 for a problem whose execution time took 160 seconds.

We may compare these results with the resultant computation that arises in the plotting of curve 10-7-2 where the sequential Maple call takes 214 seconds and the parallel implementation in Distributed Maple on a heterogeneous computer network achieves a speedup of 8 with 16 processors and of 10 with 24 processors, respectively. We are not aware of any other reports in literature on speedups gained by parallel resultant computation in distributed environments.

Maintained by: Wolfgang Schreiner

Last Modification: April 22, 1999