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.
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.
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:
Selected Recent Publications
- Cornelius Brand, Michael Sagraloff: On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection. International Symposium on Algorithms and Computation (ISSAC), 2016.
- Alexander Kobel, Fabrice Rouillier, Michael Sagraloff: Computing Real Roots of Real Polynomials ... and now for Real! International Symposium on Algorithms and Computation (ISSAC), 2016.
- Michael Sagraloff, Kurt Mehlhorn: Computing Real Roots of Real Polynomials. Journal of Symbolic Computation (JSC), 2016.
- Anurag Pandey, Nitin Saxena, Armit Sinhababu: Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits. Mathematical Foundations of Computer Science (MFCS), 2016.
- Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Polynomial-Sized Topological Approximations Using the Permutahedron. Symposium on Computational Geometry (SoCG), 2016.
- Alexander Kobel, Michael Sagraloff: On the Complexity of Computing with Planar Algebraic Curves. Journal of Complexity (JCOMP), 2015.
- Victor Alvarez, Karl Bringmann, Saurabh Ray, Raimund Seidel: Counting Triangulations and other Crossing-Free Structures Approximately. Computational Geometry (CGTA), 2015.
- Kurt Mehlhorn, Michael Sagraloff, Pengming Wang: From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition. Journal of Symbolic Computation (JSC), 2015.
- Karl Bringmann. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. Symposium on Foundations of Computer Science (FOCS), 2014.
- Markus Bläser, Gorav Jindal: A New Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation. International Symposium on Algorithms and Computation (ISAAC), 2014.
- Michael Sagraloff: A Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials. nternational Symposium on Algorithms and Computation (ISSAC), 2014.
- Eric Berberich, Pavel Emeliyanenko, Alexander Kobel, Michael Sagraloff: Exact Symbolic-Numeric Computation of Planar Algebraic Curves. Theoretical Computer Science (TCS 2013).
- Pavel Emeliyanenko: Computing resultants on Graphics Processing Units: Towards GPU-accelerated computer algebra. Journal of Parallel and Distributed Computing (PDC 2013).