Go backward to Introduction Go up to Top Go 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 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].
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:
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]:
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.