Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Tuesday, 5 July 2016
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.

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

Created by:Michael Sagraloff, 06/08/2016 03:21 PMLast modified by: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.