Opened 8 years ago

Closed 7 years ago

Last modified 5 years ago

#11634 closed enhancement (fixed)

Base Polyhedron on PPL (by default)

Reported by: vbraun Owned by: mhampton
Priority: major Milestone: sage-5.0
Component: geometry Keywords:
Cc: novoselt, dimpase Merged in: sage-5.0.beta10
Authors: Volker Braun Reviewers: Marshall Hampton, David Loeffler, Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12159, #11429 Stopgaps:

Description (last modified by vbraun)

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

Apply

Attachments (6)

trac_11634_pickling_for_PPL.patch (14.3 KB) - added by vbraun 8 years ago.
Initial patch
trac_11634_ppl_backend.patch (78.1 KB) - added by vbraun 8 years ago.
Updated patch
trac_11634_refactor_polyhedron.2.patch (523.9 KB) - added by vbraun 7 years ago.
Updated patch
trac_11634_refactor_polyhedron.patch (524.4 KB) - added by vbraun 7 years ago.
Updated patch
trac_11634-folded.patch (553.8 KB) - added by davidloeffler 7 years ago.
Apply only this patch. Patch against 5.0.beta7
trac_11634_fix_sage_5_beta8.patch (3.7 KB) - added by vbraun 7 years ago.
Initial patch

Download all attachments as: .zip

Change History (43)

comment:1 Changed 8 years ago by vbraun

  • Authors set to Volker Braun
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by vbraun

  • Cc novoselt added
  • Description modified (diff)

Changed 8 years ago by vbraun

Initial patch

comment:3 Changed 8 years ago by vbraun

  • Description modified (diff)

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

Changed 8 years ago by vbraun

Updated patch

comment:4 Changed 8 years ago by vbraun

  • Dependencies set to #12159

Through the triangulation of polytopes, this depends on #12159

comment:5 Changed 7 years ago by mhampton

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

comment:6 Changed 7 years ago by mhampton

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

comment:7 Changed 7 years ago by vbraun

  • Dependencies changed from #12159 to #12159, #11429

Yes, that one needs to be reviewed as well.

comment:8 Changed 7 years ago by mhampton

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.

comment:9 Changed 7 years ago by vbraun

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.

comment:10 Changed 7 years ago by mhampton

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.

comment:11 follow-up: Changed 7 years ago by mhampton

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

comment:12 in reply to: ↑ 11 Changed 7 years ago by novoselt

Replying to 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.

comment:13 Changed 7 years ago by dimpase

  • Cc dimpase added

comment:14 Changed 7 years ago by mhampton

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...

comment:15 Changed 7 years ago by mhampton

  • Status changed from needs_review to needs_info

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.

comment:16 Changed 7 years ago by vbraun

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.

Changed 7 years ago by vbraun

Updated patch

comment:17 Changed 7 years ago by vbraun

PS: #11429 is already reviewed ;-)

comment:18 Changed 7 years ago by mhampton

I get 0.8 as well on my mac (10.6.8). Its just that I am not sure what happens on other systems (solaris, mac ppc, whatever) so maybe leaving it as 0.8... is safer?

That's good that #11429 is done, I'll try to look at #12159 if I can find the time.

comment:19 Changed 7 years ago by vbraun

The way I understad it, #9958 changes the float printing to do the fuzzy zero automatically so its no longer necessary to add ellipsis.

comment:20 Changed 7 years ago by mhampton

OK, I guess its fine to change it back to a 0.8 then.

Changed 7 years ago by vbraun

Updated patch

comment:21 Changed 7 years ago by vbraun

  • Status changed from needs_info to needs_review

Updated patch for sage-5.0.beta4. I'm switching this back to "needs review" unless you think I haven't given enough info yet ;-)

comment:22 Changed 7 years ago by davidloeffler

Apply trac_11634_refactor_polyhedron.patch, trac_11634_pickling_for_PPL.patch, trac_11634_ppl_backend.patch

(for the patchbot)

comment:23 Changed 7 years ago by davidloeffler

Apply trac_11634_refactor_polyhedron.patch,trac_11634_pickling_for_PPL.patch,trac_11634_ppl_backend.patch

(for the patchbot, which is still not getting it)

comment:24 Changed 7 years ago by davidloeffler

Apply trac_11634_refactor_polyhedron.patch trac_11634_pickling_for_PPL.patch trac_11634_ppl_backend.patch

(it still doesn't seem to pick up the 2nd patch in the series)

comment:25 Changed 7 years ago by davidloeffler

Apply trac_11634_refactor_polyhedron.patch trac_11634_pickling_for_ppl.patch trac_11634_ppl_backend.patch 

Changed 7 years ago by davidloeffler

Apply only this patch. Patch against 5.0.beta7

comment:26 Changed 7 years ago by davidloeffler

  • Description modified (diff)

I couldn't get the patchbot to apply the three patches. Also, there seems to now be a consensus that code lines with trailing whitespace are a Bad Thing. So I've done a single qfolded patch which is equivalent to Volker's three patches but with all trailing whitespace removed.

Apply trac_11634-folded.patch

comment:27 Changed 7 years ago by mhampton

  • Reviewers set to Marshall Hampton, David Loeffler
  • Status changed from needs_review to positive_review

comment:28 Changed 7 years ago by mhampton

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.

comment:29 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:30 Changed 7 years ago by novoselt

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?

comment:31 Changed 7 years ago by vbraun

That must be new stuff that was merged in beta8

comment:32 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Needs to be rebased

comment:33 Changed 7 years ago by mhampton

Changed 7 years ago by vbraun

Initial patch

comment:34 Changed 7 years ago by vbraun

  • Description modified (diff)
  • Status changed from needs_work to needs_review

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

comment:35 Changed 7 years ago by novoselt

  • Reviewers changed from Marshall Hampton, David Loeffler to Marshall Hampton, David Loeffler, Andrey Novoseltsev
  • Status changed from needs_review to positive_review

Positive review to the new patch!

comment:36 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta10
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:37 Changed 5 years ago by kcrisman

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

Note: See TracTickets for help on using tickets.