Opened 9 years ago

Last modified 7 years ago

#13358 needs_work enhancement

package for fast polynomial evaluation — at Version 7

Reported by: gmoroz Owned by: AlexGhitza
Priority: major Milestone: sage-6.4
Component: packages: optional Keywords: polynomials
Cc: malb, zimmerma, burcin, defeo, vdelecroix Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: boost::interval (optional) Stopgaps:

Status badges

Description (last modified by gmoroz)

The attached package provides conversion of univariate and multivariate polynomials into object that are optimized for fast evaluation on python object or low-levels c++ classes (see examples at the end).

It could enhanced the fast_callable function for several types, and also enhances in general the evaluation of polynomials on polynomials.

To test it, you can install it as a standard sage package with:

sage -i fast_polynomial-0.9.2.spkg​

Main features:

  • handles univariate and multivariate polynomials
  • specialized for several low-level types (mpfi, mpz, mpq, boost::interval)
  • different evaluation layouts (horner, estrin, expanded, ...)
  • easily extensible:
    • add new types (see fast_polynomial/interfaces/README)
    • add new layouts (see docstring of fast_polynomial.method)
  • handles generic python/sage objects
  • can be multi-threaded

Main limitations:

  • only handles polynomial (no evaluation of trigonometric functions,...)
  • polynomial needs to be converted to a fast callable object before evaluation (there is room for speed up on conversion time)

Examples and benchmarks:

from fast_polynomial import *
R.<x> = ZZ[x]
p = R.random_element(500,-100,100)

# evaluation of polynomials
q = python_polynomial(p, mode='horner')
r = python_polynomial(p, mode='estrin')
%timeit p(x+1) #5 loops, best of 3: 40.3 ms per loop
%timeit q(x+1) #5 loops, best of 3: 40.3 ms per loop
%timeit r(x+1) #125 loops, best of 3: 2.26 ms per loop
%timeit python_polynomial(p)(x+1) #125 loops, best of 3: 3.2 ms per loop

# evaluation of long integers
q = mpz_polynomial(p, num_threads=1)
r = mpz_polynomial(p, num_threads=2)
%timeit p(100) #625 loops, best of 3: 50.4 µs per loop
%timeit q(100) #625 loops, best of 3: 48.1 µs per loop
%timeit r(100) #625 loops, best of 3: 34.9 µs per loop


# evaluation of mpfi interval with precision 1000
q = mpfi_polynomial(p, 1000)
e = RealIntervalField(1000)(2^500, 2^500+1)
cmp(p(e),q(e)) #0
%timeit p(e)   #125 loops, best of 3: 2.71 ms per loop
%timeit q(e)   #625 loops, best of 3: 513 µs per loop
%timeit mpfi_polynomial(p)(e) #125 loops, best of 3: 1.15 ms per loop

# evaluation of boost interval (précision 53)
q = boost_polynomial(p, mode='horner')
r = boost_polynomial(p, mode='balanced', num_threads=2)
f = fast_callable(p, domain=float)
e = RIF(0.01)
%timeit p(e)    #125 loops, best of 3: 2.14 ms per loop
%timeit f(0.01) #625 loops, best of 3: 9.54 µs per loop
%timeit q(e)    #625 loops, best of 3: 13.4 µs per loop
%timeit r(e)    #625 loops, best of 3: 11.7 µs per loop
# Note that boost_polynomial evaluation offers more guarantees than raw float evaluation

# multivariate polynomials
R20 = PolynomialRing(QQ, 20,'x')
p = R20.random_element(5,100)
q = mpq_polynomial(p)
%timeit p((2/3,)*20) #125 loops, best of 3: 2.06 ms per loop
%timeit q((2/3,)*20) #625 loops, best of 3: 178 µs per loop
%timeit mpq_polynomial(p) #125 loops, best of 3: 1.91 ms per loop

Change History (10)

Changed 9 years ago by gmoroz

fast_polynomial package compatible with sage >= 4.8

Changed 9 years ago by gmoroz

A minimal spkg (without boost dependency) to make the installation easier.

comment:1 Changed 9 years ago by gmoroz

  • Status changed from new to needs_review

Changed 9 years ago by gmoroz

bug fix and add changelog.txt file

comment:2 Changed 9 years ago by burcin

  • Cc burcin added

comment:3 Changed 9 years ago by defeo

  • Cc defeo added

comment:4 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 8 years ago by rws

  • Component changed from basic arithmetic to packages: optional

comment:7 Changed 8 years ago by gmoroz

  • Description modified (diff)
Note: See TracTickets for help on using tickets.