Go backward to IntroductionGo up to TopGo forward to Distributed Maple

# CASA

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 y4 -96a2y2 +100a2x2 -x4 and of the space curve represented by y4-384 y2+400 x2-x4+z3, x2 + y2 +z2 -30, respectively. For a detailed description of CASA, see [1].

Plotting Algebraic Curves

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:

1. (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.
2. (Symbolic) For each simple path, find an initial point between its extrema for visualizing the curve.
3. (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]:

1. Compute the resultant C[x] of some polynomials A[x,y] and B[x,y] over the integers.
2. 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);
3. 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