Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On Recent Progress in Solving Polynomial Equations - Part II
Speaker:Michael Sagraloff
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, RG1
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 5 July 2016
Duration:30 Minutes
Building:E1 4
In my second talk, I will show how to efficiently compute the solutions of a given zero-dimensional polynomial system in d variables based on our fast methods for univariate root finding. A common approach for computing the set S of solutions is to first project S into one dimension (e.g. using resultant or Groebner Basis computation) and then to recover the solutions from the projections. The latter step turns out to be difficult if the projection direction l is not known to be separating for the solutions.

I will review a simple and efficient algorithm for the certified computation of S, which
only needs to compute projections of the solutions but no further algebraic manipulations.
It computes a separating direction l as well as isolating boxes for all solutions for the cost of O(d) projections of the solutions. It is worthwhile to remark that, for d=2, the worst case bit complexity of our method matches the current record bound as achieved by much more involved algorithms.

Name(s):Michael Sagraloff
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Michael Sagraloff, 06/08/2016 03:21 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Christina Fries, 06/21/2016 03:57 PM
  • Christina Fries, 06/21/2016 10:32 AM
  • Michael Sagraloff, 06/08/2016 03:21 PM -- Created document.