#13358: package for fast polynomial evaluation
----------------------------------------------+----------------------------
Reporter: gmoroz | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.2
Component: packages: optional | Resolution:
Keywords: polynomials | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: boost::interval (optional) | Stopgaps:
----------------------------------------------+----------------------------
Description changed by gmoroz:
Old description:
> 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 with: ./setup.py install
> This will install the package in $SAGE_ROOT/local/lib/python2.7/site-
> packages/
>
> 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
> }}}
New description:
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
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/13358#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
