#18029: speed up integral point enumeration
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-7.3
Component: geometry | Resolution:
Keywords: | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/geometry/speedup_integral_points-18029|
1e7e811a0ff797b2fb7665dc3a77a50a63a68583
Dependencies: #17562 | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Travis Scrimshaw', 'oldvalue': ''}):
* commit: => 1e7e811a0ff797b2fb7665dc3a77a50a63a68583
* author: => Travis Scrimshaw
* branch: => public/geometry/speedup_integral_points-18029
* milestone: sage-6.6 => sage-7.3
Comment:
I was able to get ~15% speedup:
{{{
sage: sage: ieqs = [(-1, -1, -1, -1, -1, -1, -1, -1, -1),
....: (0, -1, 0, 0, 0, 0, 0, 0, 0),
....: (0, -1, 0, 2, -1, 0, 0, 0, 0),
....: (0, 0, -1, -1, 2, -1, 0, 0, 0),
....: (0, 2, 0, -1, 0, 0, 0, 0, 0),
....: (0, 0, 0, 0, 0, 0, 0, -1, 2),
....: (1, 0, 2, 0, -1, 0, 0, 0, 0),
....: (0, 0, 0, 0, -1, 2, -1, 0, 0),
....: (0, 0, 0, 0, 0, 0, 0, 0, -1),
....: (0, 0, 0, 0, 0, -1, 2, -1, 0),
....: (0, 0, 0, 0, 0, 0, -1, 2, -1)]
sage: P = Polyhedron(ieqs=ieqs)
sage: %time len(P.integral_points())
CPU times: user 12.4 s, sys: 5 µs, total: 12.4 s
Wall time: 12.4 s
4
}}}
In the current version, this takes ~14s. There is also could be some
improvement for the simplex approach:
{{{
sage: from sage.geometry.integral_points import simplex_points
sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5),
(-2,-1,5,1)]
sage: simplex = Polyhedron(v); simplexA 4-dimensional polyhedron in ZZ^4
defined as the convex hull of 5 vertices
sage: %timeit len(simplex_points(simplex.vertices()))
100 loops, best of 3: 15.1 ms per loop
}}}
vs
{{{
10 loops, best of 3: 24.1 ms per loop
}}}
I used all the tricks that I know to squeeze speed out with doing any
rewrites. However, it would be better to implement/use a priority queue
(or linked list) data structure instead of a straight list for the
inequalities since we are often moving one to the front as part of the
algorithm.
Yet I think this is a good gain and should be included in the present
state (unless someone feels like doing something more invasive, which I
would then review).
----
New commits:
||[https://git.sagemath.org/sage.git/commit?id=1e7e811a0ff797b2fb7665dc3a77a50a63a68583
1e7e811]||{{{Optimizations and improve cython code for
integral_points.pyx.}}}||
--
Ticket URL: <https://trac.sagemath.org/ticket/18029#comment:4>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
