Computer Algebra and Geometric Computing

We work on efficient algorithms in the area of computer algebra with a view towards the design of exact methods for handling curves and surfaces defined by algebraic equations. A common theme of our research is the combination of symbolic and approximate computation without sacrificing exactness of the final result. We also make our algorithmic results available in mature software libraries as well as computer algebra systems such as CGAL and MAPLE.

Research Area

 

Our research covers a variety of problems in computer algebra and geometric computing. One common theme is the design of hybrid algorithms that combine approximate and symbolic computation. The major challenge within this approach is to still guarantee exactness of the final result, a crucial and central requirement that our algorithms have to meet. We further investigate the complexity analysis of our algorithms but also structural properties of geometric and topological structures, often in relation with upper and lower bounds of algorithmic approaches. At the same time, a substantial fraction of our work is devoted to applying our algorithms "in the field", that is, their implementation, their experimental evaluation, and their integration into mature software packages. 

Our current focus lies on the following topics:

  • Root Finding and Polynomial System Solving: Many problems from mathematics, engineering, computer science, and the natural sciences can be reduced to solving a system of polynomial equations, which in turn reduces to solving a polynomial equation in one variable by means of elimination techniques such as resultants or Gröbner Bases. We are looking for exact and complete algorithms to solve each of the corresponding sub-problems, that is, for computing elimination polynomials (e.g., via resultants or Gröbner Bases) as well as for isolating and approximating roots of a univariate polynomial and a polynomial systems. For the design of adaptive algorithms that are efficient in practice as well as in theory, we combine symbolic and numerical computation.

  • Exact (non-linear) geometric computing: We focus on the design, the analysis, and the implementation of algorithms to exactly compute with complex geometric objects such as (semi-)algebraic curves and surfaces. This comprises methods for computing the topology of algebraic curves and surfaces and for performing boolean set operations on such objects. For efficiency, our algorithms are designed in a way such that only a minimal amount of algebraic computation is used, which is achieved by replacing symbolic operations based on exact arithmetic over rational numbers by approximate but certified arithmetic. We consider our algorithms as a fundamental basis for the solution of many problems in computer-aided design, geometric modeling and robotics.

Software

A common theme in all considered projects is to measure the efficiency of an algorithm not only in terms of its O-complexity, but also with respect to their practical performance and to publish practically fast algorithms in mature software packages. We see this not just as a service for the community, but also as a way to stimulate new and exciting research questions for our group, for instance in understanding of robustness and degeneracy handling in geometric algorithms. Our contributions include:

  • We contribute to CGAL, the Computational Geometry Algorithms Library.

  • We contribute to MAPLE, one of the leading computer algebra systems.

  • We provide a webdemo that allows everybody to analyze algebraic curves and surfaces. Here are some illustrations that were produced with our software:

 

Arrangement of rotated algebraic curves
Boolean set operation on algebraic polygons
Arrangement on a cyclide
Triangulation of an algebraic surface

Selected Recent Publications