#polynomial #solver #numeric

rust-poly

Numeric manipulation of real and complex polynomials

15 unstable releases (3 breaking)

0.4.2 Oct 11, 2024
0.3.0 Aug 24, 2024
0.2.0 May 4, 2024
0.1.13 Nov 1, 2023
0.1.1 Jul 30, 2023

#356 in Math

MIT license

160KB
3.5K SLoC

Rust Poly

Crates.io

Numeric manipulation of real and complex polynomials.

Note: this crate is still in development and might change in the future.

Basic Goals:

  • addition, subtraction and multiplication of complex and real univariate polynomials
  • long division of complex and real univariate polynomials
  • finding complex roots of polynomials
  • indexing, slicing and iterating
  • from/into traits
  • cross-compatibility with num types and others
    • primitive floats
    • Complex
    • Ratio
    • BigFloat
    • easily implementable traits for custom types

Future Goals:

  • Extremely fast polynomial evaluation (using parallelism and SIMD)
  • Ultra-high degree factorization using Lindsey-Fox
  • Fast fixed-size polynomials
  • More robust eigenvalue-based root finder using LAPACK bindings
  • Generating important polynomial sequences
    • Chebyshev type 1 polynomials
    • Chebyshev type 2 polynomials
    • Bessel polynomials
    • Reverse Bessel polynomials
    • Hermite polynomials
    • Lagrange polynomials
    • Bezier polynomials
    • Legendre polynomials
    • more to come...
  • Random integration
  • Real polynomial type
    • Real polynomial factoring
  • Rational functions
    • Simplification
  • Multivariate polynomials
  • Interpolation
  • Integer polynomials
  • Stabilize API
  • no_std support
  • Rayon support
  • Fixed point support
  • SIMD support
  • Make it go fast (fastest polynomial root finder?)
    • use GCD method for determining multiplicity of roots

Non-Goals:

  • Symbolic polynomial manipulation (use a symbolic algebra crate)

Contributing & Development

If you want to contribute to this project, please read CONTRIBUTING.md.

Before opening a pull request, make sure you have read DEVELOPMENT.md.

Licensing

This library is covered by the MIT license, see LICENSE.

Parts of the source code are based on the NumPy library for Python, used in accordance to the original license, see licenses/numpy/LICENSE.txt.

References

  • [Vestermark 2023]: Vestermark, Henrik. (2023). Practical Implementation of Polynomial Root Finders. DOI: 10.13140/RG.2.2.30423.34728.
  • [McNamee 2005] Mcnamee, J. and Olhovsky M. (2005) A comparison of a priori bounds on (real or complex) roots of polynomials.
  • [McNamee 2007 I]: McNamee, J.M. Numerical Methods for Roots of Polynomials - Part I. ISBN: 978-0-444-52729-5.
  • [McNamee 2007 II]: McNamee, J.M. Numerical Methods for Roots of Polynomials - Part II. ISBN: 978-0-444-52730-1.
  • [Lagouanelle 1966]: Lagouanelle, J.L. (1966) Sur Une Metode de Calcul de l’Ordre de Multiplicite des Zeros d’Un Polynome. Comptes Rendus de l'Académie des Sciences, 262, 626-627.
  • [Madsen 1973]: Madsen, K. (1973) A root-finding algorithm based on Newton's method. BIT 13, 71–75. DOI: 10.1007/BF01933524.
  • [Bini 1996]: Bini, D. A. (1996) Numerical computation of polynomial zeros by means of Aberth’s method. Numer Algor, vol. 13, no. 2, pp. 179–200. DOI: 10.1007/BF02207694.

Dependencies

~1.8–2.7MB
~57K SLoC