Sage: Ticket #13358: package for fast polynomial evaluation
https://trac.sagemath.org/ticket/13358
<p>
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).
</p>
<p>
It could enhanced the fast_callable function for several types, and also enhances in general the evaluation of polynomials on polynomials.
</p>
<p>
To test it, you can install it as a standard sage package with:
</p>
<pre class="wiki">sage -i fast_polynomial-0.9.2.spkg
</pre><p>
Main features:
</p>
<ul><li>handles univariate and multivariate polynomials
</li><li>specialized for several low-level types (mpfi, mpz, mpq, boost::interval)
</li><li>different evaluation layouts (horner, estrin, expanded, ...)
</li><li>easily extensible:
<ul><li>add new types (see fast_polynomial/interfaces/README)
</li><li>add new layouts (see docstring of fast_polynomial.method)
</li></ul></li><li>handles generic python/sage objects
</li><li>can be multi-threaded
</li></ul><p>
Main limitations:
</p>
<ul><li>only handles polynomial (no evaluation of trigonometric functions,...)
</li><li>polynomial needs to be converted to a fast callable object before evaluation
(there is room for speed up on conversion time)
</li></ul><p>
Examples and benchmarks:
</p>
<pre class="wiki">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
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13358
Trac 1.1.6gmorozSat, 11 Aug 2012 01:43:58 GMTattachment set
https://trac.sagemath.org/ticket/13358
https://trac.sagemath.org/ticket/13358
<ul>
<li><strong>attachment</strong>
set to <em>fast_polynomial_src_2012_08_11_0341.tar.gz</em>
</li>
</ul>
<p>
fast_polynomial package compatible with sage >= 4.8
</p>
TicketgmorozMon, 03 Sep 2012 13:54:03 GMTattachment set
https://trac.sagemath.org/ticket/13358
https://trac.sagemath.org/ticket/13358
<ul>
<li><strong>attachment</strong>
set to <em>fast_polynomial-0.9.1.spkg</em>
</li>
</ul>
<p>
A minimal spkg (without boost dependency) to make the installation easier.
</p>
TicketgmorozFri, 14 Sep 2012 10:04:34 GMTstatus changed
https://trac.sagemath.org/ticket/13358#comment:1
https://trac.sagemath.org/ticket/13358#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketgmorozMon, 15 Oct 2012 15:21:59 GMTattachment set
https://trac.sagemath.org/ticket/13358
https://trac.sagemath.org/ticket/13358
<ul>
<li><strong>attachment</strong>
set to <em>fast_polynomial-0.9.2.spkg</em>
</li>
</ul>
<p>
bug fix and add changelog.txt file
</p>
TicketburcinWed, 14 Nov 2012 09:16:59 GMTcc changed
https://trac.sagemath.org/ticket/13358#comment:2
https://trac.sagemath.org/ticket/13358#comment:2
<ul>
<li><strong>cc</strong>
<em>burcin</em> added
</li>
</ul>
TicketdefeoThu, 15 Nov 2012 12:09:15 GMTcc changed
https://trac.sagemath.org/ticket/13358#comment:3
https://trac.sagemath.org/ticket/13358#comment:3
<ul>
<li><strong>cc</strong>
<em>defeo</em> added
</li>
</ul>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/13358#comment:4
https://trac.sagemath.org/ticket/13358#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/13358#comment:5
https://trac.sagemath.org/ticket/13358#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketrwsWed, 19 Feb 2014 15:21:48 GMTcomponent changed
https://trac.sagemath.org/ticket/13358#comment:6
https://trac.sagemath.org/ticket/13358#comment:6
<ul>
<li><strong>component</strong>
changed from <em>basic arithmetic</em> to <em>packages: optional</em>
</li>
</ul>
TicketgmorozFri, 25 Apr 2014 09:49:43 GMTdescription changed
https://trac.sagemath.org/ticket/13358#comment:7
https://trac.sagemath.org/ticket/13358#comment:7
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13358?action=diff&version=7">diff</a>)
</li>
</ul>
TicketvdelecroixSun, 27 Apr 2014 16:35:14 GMTcc changed
https://trac.sagemath.org/ticket/13358#comment:8
https://trac.sagemath.org/ticket/13358#comment:8
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> added
</li>
</ul>
<p>
Hello,
</p>
<p>
This would be a very nice addition in Sage!
</p>
<p>
First of all, I was not able to install your package on 6.2.rc0 with <code>sage -i</code>. On which version did you test it? It might come from the fact that the package structure has changed: did you have a look at the developer guide in Sage 6.2.rc0 and in particular the packaging section (it has been modified for the version 6.2.rc0 in the ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16048" title="defect: dev docs: Inclusion Procedure for New and Updated Packages (closed: fixed)">#16048</a>)?
</p>
<p>
The code you wrote looks like sage code but you wrote an external package. Was it on purpose that you did not write it directly inside Sage sources? It makes perfect sense to have an external package. But in that case, it should be relatively independent from Sage (I do not know if it is feasible, please tell me). There still might be some compilation options that depend on Sage (especially in the <code>interfaces</code> part).
</p>
<p>
Vincent
</p>
TicketgmorozSun, 27 Apr 2014 21:56:15 GMT
https://trac.sagemath.org/ticket/13358#comment:9
https://trac.sagemath.org/ticket/13358#comment:9
<p>
Hello,
</p>
<p>
Thanks for your interest. Indeed I only tested it for sage 5.9. I will look into the new package structure and update it.
</p>
<p>
About the package, I did write it as an external package such that it can easily be used directly within python only. All the code related to sage should in theory be in the interface directory only. The idea is that in order to use fast_polynomial with mpmath for example, it is only required to add a corresponding interface file in the interfaces directory (telling how to convert polynomials from mpmath to fast_polynomial) and tell in the setup.py file which interface to use. I must emphasize that this is in theory only, since I only wrote interface files for sage.
</p>
<p>
The other reason I wrote it as an external package is that some part also depends on the boost::interval library, that was not in sage at the time I started the project.
</p>
<p>
Guillaume
</p>
TicketvdelecroixTue, 29 Apr 2014 10:16:34 GMT
https://trac.sagemath.org/ticket/13358#comment:10
https://trac.sagemath.org/ticket/13358#comment:10
<p>
Salut Guillaume,
</p>
<p>
It seems that your package is less independent of Sage than what you said: you import some components of the Sage library in <code>fast_polynomial/generic/evaluation/graph.pyx</code> and <code>fast_polynomial/generic/polynomial.pyx</code>.
</p>
<p>
To my mind, it would be better (for your work and for Sage) to distribute your library independently of Sage. It can be on your webpage, github or whatever. That would be a Python library with its own testing module. Once the library is ready and run within pure Python, it will be trivial to build a Sage spkg. I think that your library might interest some other projects such as <a class="ext-link" href="https://store.continuum.io/cshop/anaconda/"><span class="icon"></span>Anaconda</a>, <a class="ext-link" href="http://gmpy.sourceforge.net/"><span class="icon"></span>GMPY</a> and <a class="ext-link" href="http://ipython.org/notebook.html"><span class="icon"></span>the Ipython notebook</a>.
</p>
<p>
All best,
Vincent
</p>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/13358#comment:11
https://trac.sagemath.org/ticket/13358#comment:11
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/13358#comment:12
https://trac.sagemath.org/ticket/13358#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketjdemeyerThu, 09 Apr 2015 08:20:41 GMTstatus changed
https://trac.sagemath.org/ticket/13358#comment:13
https://trac.sagemath.org/ticket/13358#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Note: I personally don't care at all about this, but you should make a new-style package, see <a href="http://www.sagemath.org/doc/developer/#packaging-third-party-code">http://www.sagemath.org/doc/developer/#packaging-third-party-code</a>
</p>
Ticket