Campus Event Calendar
Event Entry
What and Who
On Recent Progress in Solving Polynomial Equations - Part II
Michael Sagraloff
MMCI
AG1 Mittagsseminar (own work)
AG 1, RG1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 5 July 2016
13:00
30 Minutes
Warning: Date has changed!
E1 4
024
Saarbrücken
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
Michael Sagraloff
--email hidden
passcode not visible
logged in users only
Christina Fries, 06/21/2016 15:57
Christina Fries, 06/21/2016 10:32
Michael Sagraloff, 06/08/2016 15:21 -- Created document.
Christina Fries, 06/21/2016 10:32
Michael Sagraloff, 06/08/2016 15:21 -- Created document.