Cythonize `LatticePolytope.normal_form(algorithm='palp_native')`, change to default, add as a `Polyhedron` method by mkoeppe · Pull Request #36031 · sagemath/sage

mkoeppe · 2023-08-03T20:00:34Z

The current default algorithm, using the external, unmaintained palp package, is unreliable.

Here, as a follow-up on #35997, we make the reimplementation of the PALP algorithm in Python (palp_native) suitable as the new default by speeding it up.

We also fix a bug in introduced in #35997.

We also make it available as a method of Polyhedron (for base ring ZZ).

@xuluze

📝 Checklist

The title is concise, informative, and self-explanatory.
The description explains in detail what this PR is about.
I have linked a relevant issue or discussion.
I have created tests covering the changes.
I have updated the documentation accordingly.

⌛ Dependencies

…nspose_left

…of_max

…of_max (fixup)

…of_max

…ut from .lattice_polytope

…tive'

…-style loop

mkoeppe · 2023-11-05T21:24:28Z

All taken care of; any other comments?

dimpase

apart from that missing trivial test, no problems

dimpase

LGTM, thanks

mkoeppe · 2023-11-22T23:56:24Z

Thanks

mkoeppe · 2023-11-22T23:57:45Z

Marking this as a blocker in the hope it can sneak into 10.2 with the other open blocker

@xuluze

sagemathgh-36031: Cythonize `LatticePolytope.normal_form(algorithm='palp_native')`, change to default, add as a `Polyhedron` method    The current default algorithm, using the external, unmaintained `palp` package, is unreliable. Here, as a follow-up on sagemath#35997, we make the reimplementation of the PALP algorithm in Python (`palp_native`) suitable as the new default by speeding it up. We also fix a bug in introduced in sagemath#35997. We also make it available as a method of `Polyhedron` (for base ring `ZZ`). @xuluze   ### 📝 Checklist     - [x] The title is concise, informative, and self-explanatory. - [ ] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies   URL: sagemath#36031 Reported by: Matthias Köppe Reviewer(s): Dima Pasechnik, Frédéric Chapoton, Matthias Köppe

tornaria · 2023-11-27T01:04:04Z

Marking this as a blocker in the hope it can sneak into 10.2 with the other open blocker

Why is this more worthy of "sneaking in" than e.g. #36551 ?

vbraun · 2023-11-27T20:53:01Z

Fails on 32-bit

**********************************************************************
File "src/sage/geometry/lattice_polytope.py", line 3141, in sage.geometry.lattice_polytope.LatticePolytopeClass.normal_form
Failed example:
    P.normal_form(algorithm="palp_modified")  # long time (22s)           # needs sage.groups
Exception raised:
    Traceback (most recent call last):
      File "sage/misc/cachefunc.pyx", line 1962, in sage.misc.cachefunc.CachedMethodCaller.__call__
        return cache[k]
    KeyError: (('palp_modified', False), ())
    During handling of the above exception, another exception occurred:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage_git/build/src/sage/doctest/forker.py", line 709, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage_git/build/src/sage/doctest/forker.py", line 1144, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.lattice_polytope.LatticePolytopeClass.normal_form[14]>", line 1, in <module>
        P.normal_form(algorithm="palp_modified")  # long time (22s)           # needs sage.groups
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "sage/misc/cachefunc.pyx", line 1967, in sage.misc.cachefunc.CachedMethodCaller.__call__
        w = self._instance_call(*args, **kwds)
      File "sage/misc/cachefunc.pyx", line 1842, in sage.misc.cachefunc.CachedMethodCaller._instance_call
        return self.f(self._instance, *args, **kwds)
      File "/var/lib/buildbot/slave/sage_git/build/src/sage/geometry/lattice_polytope.py", line 3204, in normal_form
        result = self._palp_modified_normal_form(permutation=permutation)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "/var/lib/buildbot/slave/sage_git/build/src/sage/geometry/lattice_polytope.py", line 3259, in _palp_modified_normal_form
        PM_max = PM.permutation_normal_form()
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "sage/matrix/matrix2.pyx", line 8637, in genexpr
        if not any(aN.is_permutation_of(j) for j in aM):
      File "sage/matrix/matrix2.pyx", line 8637, in genexpr
        if not any(aN.is_permutation_of(j) for j in aM):
      File "sage/matrix/matrix2.pyx", line 8792, in sage.matrix.matrix2.Matrix.is_permutation_of
        return N_B.is_isomorphic(M_B, certificate=False, edge_labels=True)
      File "/var/lib/buildbot/slave/sage_git/build/src/sage/graphs/generic_graph.py", line 23852, in is_isomorphic
        isom = isomorphic(GC, GC2, partition, partition2, (self._directed or self.has_loops()), 1)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "sage/groups/perm_gps/partn_ref/refinement_graphs.pyx", line 166, in sage.groups.perm_gps.partn_ref.refinement_graphs.isomorphic
        cdef bint isomorphic = double_coset(<void *>GS1, <void *>GS2, part, ordering, n, &all_children_are_equivalent, &refine_by_degree, &compare_graphs, NULL, NULL, output)
      File "sage/groups/perm_gps/partn_ref/double_coset.pyx", line 367, in sage.groups.perm_gps.partn_ref.double_coset.double_coset
        raise MemoryError
    MemoryError
**********************************************************************
1 item had failures:
   1 of  17 in sage.geometry.lattice_polytope.LatticePolytopeClass.normal_form
    [667 tests, 1 failure, 16.73 s]
**********************************************************************

…sted

mkoeppe · 2023-11-27T21:00:35Z

Sorry about this; I've disabled this example now (it's also too long on 64 bit even for # long)

github-actions · 2023-11-27T21:36:43Z

Documentation preview for this PR (built with commit f9aeca5; changes) is ready! 🎉

@xuluze

sagemathgh-36031: Cythonize `LatticePolytope.normal_form(algorithm='palp_native')`, change to default, add as a `Polyhedron` method    The current default algorithm, using the external, unmaintained `palp` package, is unreliable. Here, as a follow-up on sagemath#35997, we make the reimplementation of the PALP algorithm in Python (`palp_native`) suitable as the new default by speeding it up. We also fix a bug in introduced in sagemath#35997. We also make it available as a method of `Polyhedron` (for base ring `ZZ`). @xuluze   ### 📝 Checklist     - [x] The title is concise, informative, and self-explanatory. - [ ] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies   URL: sagemath#36031 Reported by: Matthias Köppe Reviewer(s): Dima Pasechnik, Frédéric Chapoton, Matthias Köppe

xuluze mentioned this pull request Sep 6, 2023

Crash example for palp algorithm and speed test for palp_native algorithm mkoeppe/sage#15

Merged

5 tasks

Matthias Koeppe and others added 29 commits September 24, 2023 15:25

LatticePolytope: Use experimental method PermutationGroupElement._tra…

4e9a8bd

…nspose_left

sage.geometry.palp_normal_form: Cythonized _palp_PM_max method

684f359

src/sage/geometry/palp_normal_form.pyx: More cythonization

26c8607

src/sage/geometry/palp_normal_form.pyx: Cython loop to replace index_…

e5d5935

…of_max

src/sage/geometry/palp_normal_form.pyx: Cython loop to replace index_…

1425cb1

…of_max (fixup)

src/sage/geometry/palp_normal_form.pyx: Do not keep first_row as a list

5fba248

src/sage/geometry/palp_normal_form.pyx: Replace another use of index_…

524c37c

…of_max

src/sage/groups/perm_gps/permgroup_element.pxd: Add cpdef

011f698

src/sage/geometry/palp_normal_form.pyx: Faster access to elements of PM

b15c25f

sage.geometry.palp_normal_form: Add _palp_canonical_order, factored o…

9ba1cd8

…ut from .lattice_polytope

Polyhedron_ZZ.normal_form: New

a47701b

fix bug

3411205

add the example

88ebcf7

Put new tests in TESTS sections

996191c

src/sage/geometry/lattice_polytope.py: Update copyright

d6e433f

src/sage/geometry/palp_normal_form.pyx: Add copyright

e241607

src/sage/geometry/palp_normal_form.pyx: One more use of _transpose_left

6f8769b

src/sage/geometry/palp_normal_form.pyx: Update # needs

48348b5

PermutationGroupElement._transpose_left: Generalize

63abe41

remove index_of_max

38da660

crash example

e5025ae

speed tests for palp_native

4e06ea9

Polyhedron_ZZ.normal_form: Reject unbounded polyhedra

137c848

Docstring/doctest cosmetics

26c89cf

Polyhedron_ZZ.normal_form: Add doc

7759c52

LatticePolytope.normal_form: Change the default to algorithm='palp_na…

ea4d857

…tive'

Add # needs sage.groups

05f8228

src/sage/geometry/polyhedron/base_ZZ.py: Update copyright

14a0fe4

src/sage/geometry/lattice_polytope.py: Update # needs

13dbc7e

fchapoton reviewed Nov 3, 2023

View reviewed changes

Comment thread src/sage/groups/perm_gps/permgroup_element.pyx Outdated

fchapoton reviewed Nov 3, 2023

View reviewed changes

Comment thread src/sage/geometry/polyhedron/base_ZZ.py

fchapoton reviewed Nov 3, 2023

View reviewed changes

Comment thread src/sage/geometry/polyhedron/base_ZZ.py

Matthias Koeppe added 3 commits November 3, 2023 11:35

src/sage/groups/perm_gps/permgroup_element.pyx: use a standard python…

e348fd9

…-style loop

src/sage/geometry/polyhedron/base_ZZ.py: Add more tests

8469a64

Merge branch 'develop' into palp_normal_form_cythonize

b4d016f

vbraun force-pushed the develop branch from 883e05f to e349b00 Compare November 12, 2023 16:25

Merge branch 'develop' into palp_normal_form_cythonize

c05ab9e

dimpase reviewed Nov 22, 2023

View reviewed changes

Comment thread src/sage/geometry/lattice_polytope.py

dimpase suggested changes Nov 22, 2023

View reviewed changes

src/sage/geometry/lattice_polytope.py: Add test

0bd2a93

dimpase approved these changes Nov 22, 2023

View reviewed changes

dimpase added s: positive review and removed s: needs review labels Nov 22, 2023

This was referenced Nov 27, 2023

Fix bug in QF.find_primitive_p_divisible_vector__next #36551

Merged

Do not fail when java is available but jmol is not. #36769

Merged

vbraun added s: needs work and removed p: blocker / 1 labels Nov 27, 2023

src/sage/geometry/lattice_polytope.py: Mark large example as # not te…

f9aeca5

…sted

vbraun merged commit c31f22e into sagemath:develop Dec 6, 2023

github-actions Bot removed the s: positive review label Dec 6, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Cythonize `LatticePolytope.normal_form(algorithm='palp_native')`, change to default, add as a `Polyhedron` method#36031

Cythonize `LatticePolytope.normal_form(algorithm='palp_native')`, change to default, add as a `Polyhedron` method#36031
vbraun merged 36 commits intosagemath:developfrom
mkoeppe:palp_normal_form_cythonize

mkoeppe commented Aug 3, 2023 •

edited

Loading

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mkoeppe commented Nov 5, 2023

Uh oh!

Uh oh!

dimpase left a comment

Uh oh!

dimpase left a comment

Uh oh!

mkoeppe commented Nov 22, 2023

Uh oh!

mkoeppe commented Nov 22, 2023

Uh oh!

tornaria commented Nov 27, 2023

Uh oh!

vbraun commented Nov 27, 2023

Uh oh!

mkoeppe commented Nov 27, 2023

Uh oh!

github-actions Bot commented Nov 27, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

Uh oh!

Conversation

mkoeppe commented Aug 3, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

📝 Checklist

⌛ Dependencies

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mkoeppe commented Nov 5, 2023

Uh oh!

Uh oh!

dimpase left a comment

Choose a reason for hiding this comment

Uh oh!

dimpase left a comment

Choose a reason for hiding this comment

Uh oh!

mkoeppe commented Nov 22, 2023

Uh oh!

mkoeppe commented Nov 22, 2023

Uh oh!

tornaria commented Nov 27, 2023

Uh oh!

vbraun commented Nov 27, 2023

Uh oh!

mkoeppe commented Nov 27, 2023

Uh oh!

github-actions Bot commented Nov 27, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

mkoeppe commented Aug 3, 2023 •

edited

Loading