#10140: Base sage.geometry.cone on the Parma Polyhedra Library (PPL)
------------------------------------------------+---------------------------
Reporter: vbraun | Owner: mhampton
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: geometry | Keywords: ppl
Work_issues: | Upstream: N/A
Reviewer: Andrey Novoseltsev, Volker Braun | Author: Volker
Braun, Andrey Novoseltsev
Merged: | Dependencies: #10039
------------------------------------------------+---------------------------
Old description:
> As a first useful application of the PPL Cython library interface I have
> changed `sage.geometry.cone.Cone` to use the PPL wrapper instead of
> `cddlib`. Here is a quick benchmark with a fan that was somewhat
> challenging:
> {{{
> sage: from sage.schemes.generic.toric_variety_library import
> toric_varieties_rays_cones
> sage: rays, cones = toric_varieties_rays_cones['BCdlOG']
> sage: timeit('Fan(cones,rays)')
> 5 loops, best of 3: 1.95 s per loop
> }}}
> With the old `Polyhedron`/`cddlib` interface, I got instead
> {{{
> 5 loops, best of 3: 42.1 s per loop
> }}}
>
> '''Apply'''
> 1. [attachment:trac_10140_sublattice_intersection.patch]
> 1. [attachment:trac_10140_base_cone_on_ppl_original.patch]
> 1. [attachment:trac_10140_reviewer.patch]
New description:
As a first useful application of the PPL Cython library interface I have
changed `sage.geometry.cone.Cone` to use the PPL wrapper instead of
`cddlib`. Here is a quick benchmark with a fan that was somewhat
challenging:
{{{
sage: from sage.schemes.generic.toric_variety_library import
toric_varieties_rays_cones
sage: rays, cones = toric_varieties_rays_cones['BCdlOG']
sage: timeit('Fan(cones,rays)')
5 loops, best of 3: 1.95 s per loop
}}}
With the old `Polyhedron`/`cddlib` interface, I got instead
{{{
5 loops, best of 3: 42.1 s per loop
}}}
'''Apply'''
1. [attachment:trac_10140_sublattice_intersection.patch]
1. [attachment:trac_10140_base_cone_on_ppl_original.patch]
1. [attachment:trac_10140_reviewer.patch]
1. [attachment:trac_10140_switch_point_containment_to_PPL.patch]
--
Comment(by novoselt):
One more patch: I was learning how to use PPL and trying to switch point
containment check in cones so that it does not call `polyhedron` method.
In the process I have discovered a bug with constructing cones without
rays, i.e. like `Cone([], lattice=N)`: the PPL representation in this case
didn't know the ambient space of this cone leading to mistakes. It is
fixed in the second hunk of the last patch.
Regarding original goal, here are the timings before
{{{
sage: timeit("c = Cone([(1,0), (0,1)]); (1,1) in c", number=1000)
1000 loops, best of 3: 27.8 ms per loop
sage: c = Cone([(1,0), (0,1)])
sage: timeit("(1,1) in c", number=1000)
1000 loops, best of 3: 729 µs per loop
}}}
and after
{{{
sage: timeit("c = Cone([(1,0), (0,1)]); (1,1) in c", number=1000)
1000 loops, best of 3: 2.3 ms per loop
sage: c = Cone([(1,0), (0,1)])
sage: timeit("(1,1) in c", number=1000)
1000 loops, best of 3: 290 µs per loop
}}}
As we see, even on very simple example we get 10x speedup for "single
checks" when most of the time is spent constructing different
representations of the cone. When everything is precached and we count
only actual containment, we have 3x speed up.
A more complicated example before:
{{{
sage: c = Cone([(4, 0, 1, 12, 1), (-2, -2, -73, 1, 0), (1, -2, 0, 1, -3),
(5, -1, -1,
sage: 1, 1), (-4, 5, 1, 2, 3), (0, -1, -23, 0, 1), (-2, 1, -1, 1, -1), (0,
2,
sage: -3, 1, 0), (-1, 3, 2, -1, 0), (0, 2, -1, 4, 15)])
sage: c.ray_matrix()
[ -4 -2 -2 -1 0 5 0 1]
[ 5 -2 1 3 -1 -1 2 -2]
[ 1 -73 -1 2 -23 -1 -1 0]
[ 2 1 1 -1 0 1 4 1]
[ 3 0 -1 0 1 1 15 -3]
sage: timeit("(1,2,3,4,5) in c", number=1000)
1000 loops, best of 3: 4.52 ms per loop
}}}
and after
{{{
sage: c = Cone([(4, 0, 1, 12, 1), (-2, -2, -73, 1, 0), (1, -2, 0, 1, -3),
(5, -1, -1,
sage: 1, 1), (-4, 5, 1, 2, 3), (0, -1, -23, 0, 1), (-2, 1, -1, 1, -1), (0,
2,
sage: -3, 1, 0), (-1, 3, 2, -1, 0), (0, 2, -1, 4, 15)])
sage: timeit("(1,2,3,4,5) in c", number=1000)
1000 loops, best of 3: 1.3 ms per loop
}}}
(I didn't bother with fresh start timing here.)
Conclusion: Volker's PPL wrapper rocks!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10140#comment:48>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
