Go backward to IntroductionGo up to TopGo forward to Distributed Maple |

The software library CASA is designed for computing with and reasoning about
objects in classical algebraic geometry (affine and projective algebraic
geometry over an algebraically closed field *F* of characteristic *0*). The
objects that CASA deals with are algebraic sets in various representations,
e.g., as the set of common zeros of a system of polynomial
equations. Algebraic sets in two variables represent curves in the plane;
algebraic sets in three variables represent surfaces in space (or
intersections of such, i.e. space curves). Figure * illustrates
plots of the planar curve represented by the polynomial *y ^{4} -96a^{2}y^{2}
+100a^{2}x^{2} -x^{4}* and of the space curve represented by

One important problem that CASA solves is the *reliable* plotting of
algebraic curves. Purely numerical methods may and often do yield
qualitatively wrong solutions, i.e., plots where some "critical points"
(e.g., singularities) disappear. The CASA functions `pacPlot`

for
plotting plane curves and `ssiPlot`

for plotting intersections of space
curves apply a hybrid combination of exact symbolic algorithms for the
computation of all critical points and of fast numerical methods for the
interpolation between these points [11]. However, the computation time
of the symbolic methods dominates the total plotting time and even on fast
workstations only curves with total degree up to 12 or so can be plotted by
CASA in a time acceptable for interactive usage.

Currently, we are working on the parallelization of the function
`pacPlot`

which operates in three phases:

- (Symbolic) Compute all extremal points (including singularities) of the
curve in direction
*x*. Each interval on the*x*-axis between two extremal points defines one or more "simple" paths of the curve. - (Symbolic) For each simple path, find an initial point between its extrema for visualizing the curve.
- (Numerical) Use Newton iteration to trace each simple path from its initial point in both directions towards the extremal points.

The first phase is by far the most time-consuming one accounting in most cases for more than 95% of the total computation time. It is beyond the scope of this paper to explain the detailed operation of this phase but its time-relevant steps are essentially [11]:

- Compute the resultant
*C[x]*of some polynomials*A[x,y]*and*B[x,y]*over the integers. - Isolate the real roots of
*C[x]*(i.e., determine a set of disjoint intervals such that each real root of*C[x]*is contained in one and only one interval); - For each real root
*r*of*C[x]*, isolate the real roots of*B[y <- r]*.

The structure of Step 3 lends itself immediately to a parallel implementation
which we have already adopted. The parallelization of the real root isolation
(Step 2 and within every task of Step 3) is currently under way. The resultant
computation in Step 1 remains the single most time time-consuming operation in
`pacPlot`

; we will describe in Section * in detail a
parallel solution to this problem. The seamless and efficient integration of
the various parallel algorithms and parallelization layers in
`pacPlot`

is our future concern.

Maintained by: Wolfgang Schreiner

Last Modification: April 22, 1999