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 1
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, 21 June 2016
Duration:45 Minutes
Building:E1 4
The computation of the roots of a univariate polynomial is one of the best studied problems in the areas of computer algebra and numerical analysis. Nevertheless, until recently, there has still been a large discrepancy between methods that are considered to be efficient in practice and those that achieve good theoretical bounds.

I will review some recently developed algorithms for real and complex root finding, which are simple and practical and whose worst-case bit complexity matches that of the best methods in theory.
Combining our techniques with a classical approach that considers so-called fractional derivatives, we can further derive a polynomial-time algorithm to compute approximations of all real roots of a sparse polynomial with arbitrary real coefficients. For very sparse polynomials with integer coefficients, the method performs near-optimal.

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:16 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Michael Sagraloff, 06/08/2016 03:23 PM
  • Michael Sagraloff, 06/08/2016 03:16 PM -- Created document.