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: |
Description (last modified by )
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
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Cc burcin added
comment:3 Changed 9 years ago by
- Cc defeo added
comment:4 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 8 years ago by
- Component changed from basic arithmetic to packages: optional
comment:7 Changed 8 years ago by
- Description modified (diff)
Note: See
TracTickets for help on using
tickets.
fast_polynomial package compatible with sage >= 4.8