A practical implementation has to balance two conflicting goals: efficiency and reliability. Roughly speaking, the algorithms must not be subject to failure and must find all the parts of the algebraic set. On the other hand, algorithms must be efficient enough so that interaction between a CAGD user and a CAGD system can be achieved. Typically, a numerical algorithm is efficient, but it is not reliable and may fail in certain cases, especially in areas near the singularities. On the other hand, algorithms based on exact arithmetic are reliable, but are normally slow and require a lot of memory space.
In spite of much effort, no present algorithm satisfies all those two main goals (see [22],[24],[25], [26]). Perhaps the goals of efficiency and reliability cannot be met simultaneously without some compromises. We propose to negotiate those compromises judiciously. That means that, we will tackle the problems by a hybrid symbolic-numerical approach and develop algorithms which should fit those three main goals.
We restrict attention to algebraic curves and surfaces. This restriction is reasonable in the sense that the class is very rich and includes most of the curves and surfaces used in, for instance, engineering design. In particular, this class includes all the major parametric surfaces used in geometric modeling, including Bezier surfaces, nonuniform rational B-spline (NURBS), and so on (see [22],[15],[19],[14], [17],[16],[13]). It does not include all space curves and surfaces, however. For example, the helix is not an algebraic space curve. In previous projects we have developed the system CASA for pure Symbolic Computation on algebraic curves and surfaces (see [28],[27]).
To support our goals, we would like to use new techniques, for example: combination of symbolic-numerical methods, parallel computation, multi-precision floating point arithmetic, multivariate resultants, Gröbner Basis with respect to the product term ordering, etc., in our research. Such techniques are not ready-to-use in any suitable system.
Therefore, together with the theoretical research, we also propose a project work which is directed towards designing software. The software - called HySaX (Hybrid Software for Algebraic Geometry in X-windows environment) - will aim at the implementation of hybrid symbolic-numerical algorithms for approximation and representation of algebraic sets in two and three dimensions. The software will be built as an enhancement of the traditional and widely used computer algebra system Maple. Therefore it can be benefited from a large number of already known algorithms which has been implemented in the library/share-library of Maple. Especially, it will succeed the CASA system, a computer algebra system for constructive algebraic geometry, which has been developed by the Computer Algebra group of RISC-Linz.