Base Polyhedron on PPL (by default)

[vbraun]

Rewrite the Polyhedron class to allow different backends for the computation and make PPL the default for polyhedra over QQ.

Apply

• attachment: trac_11634-folded.patch
• attachment: trac_11634_fix_sage_5_beta8.patch

Depends on #12159
Depends on #11429

CC: @novoselt @dimpase

Component: geometry

Author: Volker Braun

Reviewer: Marshall Hampton, David Loeffler, Andrey Novoseltsev

Merged: sage-5.0.beta10

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

[vbraun]

Author: Volker Braun

[vbraun]

Attachment: trac_11634_pickling_for_PPL.patch.gz

Initial patch

[vbraun]

comment:3

I've added pickling support to PPL, this is now part of this ticket.

[vbraun]

Updated patch

[vbraun]

Dependencies: #12159

[vbraun]

comment:4

Attachment: trac_11634_ppl_backend.patch.gz

Through the triangulation of polytopes, this depends on #12159

[sagetrac-mhampton]

comment:5

Volker, I'll try to review this this week if I can. If I forget feel free to ping me about it.

[sagetrac-mhampton]

comment:6

I'm having trouble applying your patches, it looks like this also depends on #11429.

[vbraun]

comment:7

Yes, that one needs to be reviewed as well.

[vbraun]

Changed dependencies from #12159 to #12159, #11429

[sagetrac-mhampton]

comment:8

I tried applying #11429, and then #12159, both of which worked fine, but I am unable to apply the patches from this ticket after that.

[vbraun]

comment:9

I have the following patches applied on top of sage-4.8.alpha6 without problems:

[vbraun@volker-laptop-two hg]$ hg qseries
trac_11429_native_enumeration_of_lattice_polytope_points.patch
trac_11429_cythonize_lattice_points.patch
trac_11429_fix_doctests.patch
trac_12159_separate_triangulation_file.patch
trac_12159_placing_triangulation.patch
trac_12159_normal_cone.patch
trac_11634_refactor_polyhedron.patch
trac_11634_pickling_for_PPL.patch
trac_11634_ppl_backend.patch

The patches might not apply cleanly older sage versions.

[sagetrac-mhampton]

comment:10

Thanks; I was working with an unoffical sage-4.8.rc1, I will switch to 4.8.alpha6 and try again in case that is the problem.

[sagetrac-mhampton]

comment:11

OK, I got it working now. Clearly PPL is much faster on some of my test examples, wow.

[novoselt]

comment:12

Replying to @sagetrac-mhampton:

OK, I got it working now. Clearly PPL is much faster on some of my test examples, wow.

Oh yeah, working with toric varieties got much better once most basic operations were switched to PPL!

I am also the offending reviewer on #11429, dropping off the radar half-way. Will try to remedy it shortly, without forgetting #11599.

[sagetrac-mhampton]

comment:14

For sage-5.0.beta1, the numerial noise fix from #9958 changes one line of polyhedra.py, which causes trac_11634_refactor_polyhedron.patch to fail to apply.

5866c5866
<             0.8
---
>             0.8000...

[sagetrac-mhampton]

comment:15

I'm a little confused by the above numerical noise issue. After changing so that the patch would apply, the doctest failed. If I switch it to

            sage: filled_poly.axes_width()
            0.8...

then it works. I'm not sure if the "0.800..." makes sense on some other system or not.

Apart from that I think this all looks good. There is one other doctest failure in integral_points.pyx resulting from the Python switch to 2.7, line 688 needs to be changed to

        OverflowError: Python int too large to convert to C long

instead of

        OverflowError: long int too large to convert to int

With those changes I would be happy to give a positive review.

I haven't looked at #11429 and #12159 by themselves, but it would be nice to get this ticket into sage-5.0. I don't have a lot of time in the coming weeks but if Andrey can't review those I would try to check them out too.

[vbraun]

comment:16

I already fixed the OverflowError error message in #11429. What output do you get for

filled_poly.axes_width()

the doctest works for me with 0.8.

[vbraun]

Updated patch

[sagetrac-mhampton]

comment:28

Thanks David, that made things simpler for me to look at. Volker, my apologies for taking so long on reviewing this. I think this should be a great addition to sage-5.0.

[novoselt]

comment:30

I am not entirely sure if something is wrong on my end, but when I apply the following patches to Sage-5.0.beta8

novoselt@sage ~/sage/devel/sage-main $ hg qapplied
trac_11599_no_circular_imports.patch
trac_11599_homset_new_coercion_model.patch
trac_11599_rename_morphisms.patch
trac_11599_toric_morphisms.patch
trac_11599_reviewer.patch
trac_11599_remove_class_suffix.patch
trac_11599_remaining_fixes.patch
trac_11599_numerical_noise.patch
trac_12159_separate_triangulation_file.patch
trac_12159_placing_triangulation.patch
trac_12159_normal_cone.patch
trac_11634-folded.patch

I get after trying to start Sage

----------------------------------------------------------------------
| Sage Version 5.0.beta8, Release Date: 2012-03-13                   |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
**********************************************************************
*                                                                    *
* Warning: this is a prerelease version, and it may be unstable.     *
*                                                                    *
**********************************************************************
/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/combinat/root_system/associahedron.py:22: DeprecationWarning: (Since Sage Version 4.8) The module sage.geometry.polyhedra has been removed, use sage.geometry.polyhedron instead.
  from sage.geometry.polyhedra import Polyhedron
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/IPython/ipmaker.pyc in force_import(modname, force_reload)
     61         reload(sys.modules[modname])
     62     else:
---> 63         __import__(modname)
     64         
     65 

/home/novoselt/sage-5.0.beta8/local/bin/ipy_profile_sage.py in <module>()
      5     preparser(True)
      6     
----> 7     import sage.all_cmdline
      8     sage.all_cmdline._init_cmdline(globals())
      9     

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/all_cmdline.py in <module>()
     12 try:
     13 
---> 14     from sage.all import *
     15     from sage.calculus.predefined import x
     16     preparser(on=True)

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/all.py in <module>()
     80 from sage.modules.all    import *
     81 from sage.monoids.all    import *
---> 82 from sage.algebras.all   import *
     83 from sage.modular.all    import *
     84 from sage.schemes.all    import *

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/algebras/all.py in <module>()
     34 from group_algebra_new import GroupAlgebra
     35 
---> 36 from iwahori_hecke_algebra import IwahoriHeckeAlgebraT
     37 from affine_nil_temperley_lieb import AffineNilTemperleyLiebTypeA
     38 from nil_coxeter_algebra import NilCoxeterAlgebra

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/algebras/iwahori_hecke_algebra.py in <module>()
     10 #*****************************************************************************
     11 from sage.categories.all import AlgebrasWithBasis, FiniteDimensionalAlgebrasWithBasis, CoxeterGroups
---> 12 import sage.combinat.root_system.cartan_type
     13 from sage.combinat.root_system.weyl_group import WeylGroup
     14 from sage.combinat.family import Family

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/combinat/root_system/__init__.py in <module>()
     11 import type_G
     12 
---> 13 import all
     14 
     15 

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/combinat/root_system/all.py in <module>()
----> 1 
      2 
      3 from associahedron import Associahedron
      4 from cartan_type import CartanType
      5 from dynkin_diagram import DynkinDiagram, dynkin_diagram
      6 from cartan_matrix import cartan_matrix
      7 from coxeter_matrix import coxeter_matrix

/home/novoselt/sage-5.0.beta8/local/lib/python2.7/site-packages/sage/combinat/root_system/associahedron.py in <module>()
     24 from sage.modules.free_module_element import vector
     25 
---> 26 class Associahedron(Polyhedron):
     27     r"""
     28     The generalized associahedron is a polytopal complex with vertices in one-to-one correspondence

TypeError: Error when calling the metaclass bases
    function() argument 1 must be code, not str
Error importing ipy_profile_sage - perhaps you should run %upgrade?
WARNING: Loading of ipy_profile_sage failed.

Is it because some new stuff merged in alpha8 uses old polyhedra code and was not converted?

[vbraun]

comment:31

That must be new stuff that was merged in beta8

[vbraun]

comment:32

Needs to be rebased

[sagetrac-mhampton]

comment:33

I think this must be from
#10817

[vbraun]

Initial patch

[vbraun]

comment:34

Attachment: trac_11634_fix_sage_5_beta8.patch.gz

I've added a patch that converts the new !Associahedron class to a PPL-based polyhedron

[novoselt]

comment:35

Positive review to the new patch!

[novoselt]

Changed reviewer from Marshall Hampton, David Loeffler to Marshall Hampton, David Loeffler, Andrey Novoseltsev

[jdemeyer]

Merged: sage-5.0.beta10

[kcrisman]

comment:37

Question (likely dumb): could the behavior at this ask.sagemath question be related to this change (or #14175)? Thanks!