Skip to content

Instantly share code, notes, and snippets.

@kvedala

kvedala/fast polynomial roots.ipynb

Last active April 29, 2020 03:02
Show Gist options
  • Save kvedala/9713842d5e264c94e293a930b479f597 to your computer and use it in GitHub Desktop.
Save kvedala/9713842d5e264c94e293a930b479f597 to your computer and use it in GitHub Desktop.
Download ZIP
Durand-Kerner Roots - Python
Display the source blob
Display the rendered blob
Raw
fast polynomial roots.ipynb
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
notebook.ipynb
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
@kvedala
Copy link
Author

kvedala commented Apr 9, 2020 •
edited

Performance improvement

Performing

polynom = polynom / polynom[0]

i.e., by ensuing the coefficient of the highest power of x to be 1 significantly improves the numerical stability.

For example, the above algorithm fails for:

# 1 - fail example:
polynom = np.array([4, 0, -1])
benchmark(polynom)
# 2 - fail example
polynom = np.array([2, 13, -7])
benchmark(polynom)

but the problem gets resolved when executing as such:

# 1 - fail example - resolved:
polynom = np.array([4, 0, -1])
polynom = polynom / polynom[0]
benchmark(polynom)
# 2 - fail example - resolved
polynom = np.array([2, 13, -7])
polynom = polynom / polynom[0]
benchmark(polynom)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment