Homepage

Michael Sagraloff

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Building 46.1, Room 306
Stuhlsatzenhausweg 85
66123 Saarbrücken
Germany

Email: Get my email address via email
Phone: +49 681 9325 106
Fax: +49 681 9325 199

Research Interests

(Real) Algebraic Geometry
Computer Algebra
Numerical Algebraic Computation
Exact Geometric Computing
Polynomial System Solving

Publications

Alexander Kobel, Michael Sagraloff.
Fast Approximate Polynomial Multipoint Evaluation and Applications. arXiv, 2013. (pdf)
Chee Yap, Michael Sagraloff, Vikram Sharma.
Analytic Root Clustering: A Complete Algorithm using Soft Zero Tests. to be presented at Computability in Europe (CIE), 2013. (pdf)
Kurt Mehlhorn, Michael Sagraloff, Pengming Wang.
From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition. to be presented at the International Symposium on Symbolic and Algebraic Computation (ISSAC), 2013. (pdf)
Pavel Emeliyanenko, Alexander Kobel, Eric Berberich, Michael Sagraloff.
Exact Symbolic-Numeric Computation of Planar Algebraic Curves. to appear in Theoretical Computer Science (TCS), 2013. (pdf)
Michael Sagraloff.
When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial. International Symposium on Symbolic and Algebraic Computation (ISSAC), 2012. (pdf)
Pavel Emeliyanenko, Michael Sagraloff.
On the Complexity of Solving a Bivariate Polynomial System. International Symposium on Symbolic and Algebraic Computation (ISSAC), 2012. (pdf).
Michael Kerber, Michael Sagraloff.
A Worst-case Bound for Topology Computation of Algebraic Curves. Journal of Symbolic Computations (JSC), Volume 47, Issue 3, 2012. (pdf).
Pavel Emeliyanenko, Alexander Kobel, Eric Berberich, Michael Sagraloff.
Arrangement Computation for Planar Algebraic Curves. In Symbolic Numeric Computation (SNC), 2011. (pdf)
Michael Kerber, Michael Sagraloff.
Efficient Real Root Approximation. In Symposium on Symbolic and Algebraic Computation (ISSAC), 2011. see (pdf) for an extended version.
Pavel Emeliyanenko, Eric Berberich, Michael Sagraloff.
An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks. In Algorithm Engineering and Experiments (ALENEX), 2011. (pdf)
Kurt Mehlhorn, Ralf Osbild, Michael Sagraloff.
A General Approach to the Analysis of Controlled Perturbation Algorithms. In Computational Geometry: Theory and Applications (CGTA), 2011. (pdf)
Michael Kerber, Michael Sagraloff.
A Note on the Complexity of Real Algebraic Hypersurfaces. In Graphs and Combinatorics, 2011. (pdf)
Michael Sagraloff, Chee K. Yap.
An Efficient and Exact Subdivision Algorithm for Isolating Complex Roots of a Polynomial and its Complexity Analysis. In Symposium on Symbolic and Algebraic Computation (ISSAC), 2011. (pdf)
Michael Sagraloff.
On the Complexity of Real Root Isolation. submitted, 2010. (pdf)
Michael Sagraloff.
A General Approach to Isolating Roots of a Bitstream Polynomial. In Mathematics in Computer Science (MCS), 2010. (pdf)
K. Mehlhorn, M. Sagraloff.
A Deterministic Descartes Algorithm for Real Polynomials.. In Journal of Symbolic Computation (JSC), 2010. (pdf).
Michael Sagraloff, Michael Kerber, Michael Hemmer.
Certified Complex Root Isolation via Adaptive Root Separation Bounds. In 9th Asian Symposium on Computer Mathematics (ASCM), 2009. (pdf)
Michael Kerber, Michael Sagraloff.
How Complex are Real Algebraic Objects?. In 7th Japan Conference on Computational Geometry and Graphs (JCCGG), 2009. (pdf)
P. Emeliyanenko, E. Berberich, M. Sagraloff.
Visualizing Arcs of Implicit Algebraic Curves, Exactly and Fast. In International Symposium for Visual Computing (ISVC), 2009. (pdf)
K. Mehlhorn, M. Sagraloff.
Isolating Real Roots of Real Polynomials.. In Symposium on Symbolic and Algebraic Computation (ISSAC), 2009, pp. 247-254.
E. Berberich and M. Sagraloff
A Generic and Flexible Framework for the Geometrical and Topological Analysis of (Algebraic) Surfaces. In Computer Aided Geometric Design (CAGD), Volume 26, Issue 6, pp. 615-724, 2009.
E. Berberich, M. Kerber, M. Sagraloff.
An Efficient Algorithm for the Stratification and Triangulation of an Algebraic Surface. In Computational Geometry: Theory and Applications (CGTA), Volume 43, Issue 3, pp. 257-278, 2009. (pdf).
E. Berberich, M. Kerber, M. Sagraloff.
Exact Geometric-Topological Analysis of Algebraic Surfaces. In Symposium on Computational geometry (SoCG), 2008, pp. 164-173. An extended abstract of this work was presented at the 24th European Workshop on Computational Geometry (pdf).
E. Berberich and M. Sagraloff
A Generic and Flexible Framework for the Geometrical and Topological Analysis of (Algebraic) Surfaces. In Symposium on Solid and Physical Modeling (SPM), 2008, pp. 171-182
Kurt Mehlhorn, Ralf Osbild, Michael Sagraloff.
Reliable and Efficient Computational Geometry via Controlled Perturbation. In International Colloquium on Automata, Languages and Programming (ICALP), volume 4051 of LNCS, pages 299-310, 2006.
Michael Sagraloff.
Syzygies and Special Linear Series of Canonical Curves of Genus 9.PhD Thesis at Saarland University, 2005.
Michael Sagraloff.
Quartiken als Summe von Potenzen im IP³. Master Thesis at University of Bayreuth, 2002.

Teaching

Lecture (Perspektivvorlesung) on ``Exact Geometric Computing'' in the winter term of 2013.

Lecture on "Computer Algebra" in the summer term of 2011.

Seminar on "Computational Geometry and Geometric Computing" (together with E. Berberich and B. Galehouse) in the summer term of 2010

Lecture on "Computational Geometry and Geometric Computing" (together with E. Berberich and K. Mehlhorn) in the winter term of 2009/2010

Lecture on "Nonlinear Computational Geometry" (together with Michael Hemmer) in the winter term of 2008/2009

Seminar on "Computational Topology" (together with Joachim Giesen) in the winter term of 2006/2007

Seminar on "Computational and Algebraic Geometry" in the winter term of 2005/2006

Recent Positions

Senior Researcher, Coordinator for Geometric Computing and Computer Algebra

PC member International Congress on Mathematical Software (ICMS) 2010, Kobe

Organization Workshop on Geometric Computing 2010, IIT Delhi

MPI site representative for the EU project ACS (Algorithms on Complex Shapes)

Organisation of the Max Planck summer school ADFOCS 2006

Education

2002 - 2005:
Ph. D. student in Mathematics (Algebraic Geometry) at the Universität des Saarlandes, Saarbrücken, Germany
Title of PhD Thesis (Dr. Arbeit): "Syzygies and Special Linear Series of Canonical Curves of Genus 9"' (supervisor: Prof. Dr. F.-O. Schreyer)
1998 - 2002:
Studies in Mathematics at the University of Bayreuth
Title of Master's Thesis (Diplomarbeit): "Quartiken als Summe von Potenzen im IP³"' (supervisor: Prof. Dr. F.-O. Schreyer)
1997:
Abitur at the Helene-Lange-Gymnasium, Fürth, 1997
Curriculum Vitae