search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

Base sage.geometry.cone on the Parma Polyhedra Library (PPL) #10140

Closed vbraun closed 13 years ago

vbraun commented 13 years ago

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
  2. attachment: trac_10140_base_cone_on_ppl_original.patch
  3. attachment: trac_10140_reviewer.patch
  4. attachment: trac_10140_switch_point_containment_to_PPL.patch

Apply trac_10140_sublattice_intersection.patch, trac_10140_base_cone_on_ppl_original.patch, trac_10140_reviewer.patch, trac_10140_switch_point_containment_to_PPL.patch

Depends on #10039

CC: @novoselt @nthiery

Component: geometry

Keywords: ppl

Author: Volker Braun, Andrey Novoseltsev

Reviewer: Andrey Novoseltsev, Volker Braun

Merged: sage-4.7.1.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/10140

novoselt commented 13 years ago
comment:44

Fan morphisms (will) use cones in sublattices: the kernel fan naturally lives either in the domain lattice or the kernel sublattice, which corresponds to different toric varieties.

I also suspect that while you were working on this patch zero rays passed to the cone constructor were breaking the code and that's why you have replaced the related doctests. However, there is now a catch for this case, so they should be fine. In general, I think it is important to allow zero rays in the input, e.g. if you are constructing a projected cone and some of the rays are mapped to the origin.

Anyway, I'll take care of sublattices and move here appropriate chunks from #10943, #10882, and #11200 (unless they get reviewed in the near future and can be left in front of this one ;-))

vbraun commented 13 years ago
comment:45

Either syntax for constructing the trivial cone is fine with me. Personally I prefer the one I used since it is a bit more obvious.

novoselt commented 13 years ago

Attachment: trac_10140_base_cone_on_ppl_original.patch.gz

Folded Volker's patches without some of the doctest fixes.

novoselt commented 13 years ago
comment:46

I have removed the first change of the trivial cone construction since it was in the place where two variants are explicitly described.

The new patch slightly changes the general method of intersection modules and adds an extending method to toric lattices. Now there is no need to check lattice compatibility in the cone intersection: it will fail if they are wrong.

Added #10882 as a dependency for now, but may remove it on the weekend by moving some code here. It is not difficult, but it will break my "thesis queue" so I want to do it carefully and take care of consequences.

novoselt commented 13 years ago

Description changed:

--- 
+++ 
@@ -12,8 +12,11 @@
 5 loops, best of 3: 42.1 s per loop

-Depends on #10039: Make Parma Polyhedra Library a standard library +Depends on +1. #10039: Make Parma Polyhedra Library a standard library +2. #10882: Add kernel fan to fan morphism

Apply -1. attachment: trac_10140_base_cone_on_ppl_original.patch -2. attachment: trac_10140_reviewer.patch +1. attachment: trac_10140_sublattice_intersection.patch +2. attachment: trac_10140_base_cone_on_ppl_original.patch +3. attachment: trac_10140_reviewer.patch

novoselt commented 13 years ago

Changed work issues from intersect sublattices to remove/review dependencies

novoselt commented 13 years ago

Changed author from Volker Braun to Volker Braun, Andrey Novoseltsev

novoselt commented 13 years ago

Changed reviewer from Andrey Novoseltsev to Andrey Novoseltsev, Volker Braun

novoselt commented 13 years ago

Description changed:

--- 
+++ 
@@ -12,10 +12,6 @@
 5 loops, best of 3: 42.1 s per loop

-Depends on -1. #10039: Make Parma Polyhedra Library a standard library -2. #10882: Add kernel fan to fan morphism

Apply

  1. attachment: trac_10140_sublattice_intersection.patch
  2. attachment: trac_10140_base_cone_on_ppl_original.patch
novoselt commented 13 years ago

Dependencies: #10039

novoselt commented 13 years ago

Changed work issues from remove/review dependencies to none

novoselt commented 13 years ago
comment:47

Attachment: trac_10140_sublattice_intersection.patch.gz

OK, the new patches apply cleanly to sage-4.7.alpha4 and pass all long tests, documentation builds without warnings. The first patch now includes some adjustments to lattice treatment, moved here from #10882 (I'll update the patch there shortly.)

Volker, if you are fine with my patches, please switch it to positive review!

novoselt commented 13 years ago

Description changed:

--- 
+++ 
@@ -16,3 +16,4 @@
 1. [attachment: trac_10140_sublattice_intersection.patch](https://github.com/sagemath/sage-prod/files/10651205/trac_10140_sublattice_intersection.patch.gz)
 2. [attachment: trac_10140_base_cone_on_ppl_original.patch](https://github.com/sagemath/sage-prod/files/10651204/trac_10140_base_cone_on_ppl_original.patch.gz)
 3. [attachment: trac_10140_reviewer.patch](https://github.com/sagemath/sage-prod/files/10651207/trac_10140_reviewer.patch.gz)
+4. [attachment: trac_10140_switch_point_containment_to_PPL.patch](https://github.com/sagemath/sage-prod/files/10651206/trac_10140_switch_point_containment_to_PPL.patch.gz)
novoselt commented 13 years ago
comment:48

Attachment: trac_10140_switch_point_containment_to_PPL.patch.gz

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!

vbraun commented 13 years ago
comment:49

I'm happy with the reviewer patch, so positive review alltogether ;-)

jdemeyer commented 13 years ago
comment:51

@ Andrey Novoseltsev: Can you upload your reviewer patch again using hg export tip? The user and date fields are missing.

novoselt commented 13 years ago
comment:52

Attachment: trac_10140_reviewer.patch.gz

Done!

jdemeyer commented 13 years ago

Merged: sage-4.7.1.alpha1

vbraun commented 13 years ago
comment:54

I'm adding an unformatted "Apply" section in the ticket description to help the patch buildbot figure out the correct patches.

vbraun commented 13 years ago

Description changed:

--- 
+++ 
@@ -17,3 +17,7 @@
 2. [attachment: trac_10140_base_cone_on_ppl_original.patch](https://github.com/sagemath/sage-prod/files/10651204/trac_10140_base_cone_on_ppl_original.patch.gz)
 3. [attachment: trac_10140_reviewer.patch](https://github.com/sagemath/sage-prod/files/10651207/trac_10140_reviewer.patch.gz)
 4. [attachment: trac_10140_switch_point_containment_to_PPL.patch](https://github.com/sagemath/sage-prod/files/10651206/trac_10140_switch_point_containment_to_PPL.patch.gz)
+
+
+Apply trac_10140_sublattice_intersection.patch, trac_10140_base_cone_on_ppl_original.patch, trac_10140_reviewer.patch, trac_10140_switch_point_containment_to_PPL.patch
+
vbraun commented 13 years ago
comment:55

Apply trac_10140_sublattice_intersection.patch, trac_10140_base_cone_on_ppl_original.patch, trac_10140_reviewer.patch, trac_10140_switch_point_containment_to_PPL.patch

dimpase commented 12 years ago
comment:56

How hard would it be to set up PPL to do Vrepresentation and Hrepresentation of Polyhedron?

novoselt commented 12 years ago
comment:57

Replying to @dimpase:

How hard would it be to set up PPL to do Vrepresentation and Hrepresentation of Polyhedron?

See #11634. Not easy, I guess, but Volker has done it.