Opened 2 years ago

Closed 22 months ago

Last modified 21 months ago

#26887 closed enhancement (fixed)

Implement the class CombinatorialPolyhedron

Reported by: gh-kliem Owned by: gh-kliem
Priority: major Milestone: sage-8.9
Component: geometry Keywords: polytopes, FindPoly, f_vector, face lattice, edge graph, ridge graph
Cc: stumpc5, jipilab, tscrim Merged in:
Authors: Jonathan Kliem Reviewers: Jeroen Demeyer, Travis Scrimshaw, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 39a7099 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

We construct a class CombinatorialPolyhedron?, which collects several methods for polyhedra depending only on the combinatorial type. Actually, most of the methods will work for atomic, coatomic Eulerian lattices.

Computations can be much faster when avoiding creating explicitly the face lattice.

Example:

P = polytopes.permutahedron(6)
P.f_vector()

On my machine this takes over 8s, but it should be a matter of ms. For permutahedron(7) it takes forever and should also be a matter of ms.

Additionally, one can create the face_lattice much faster. The face_lattice of permutahedron(7) should only take few seconds. This is done by creating of lists of all faces and then quickly checking inclusions.

The crucial speed up is obtained by creating bit-vectors for the faces, each bit corresponding to a vertex. Intersection of faces is then only bitwise-and and subset check is (A & ~B == 0). Both steps only take one CPU step per 64/128/256 bits/vertices (depending on the processor). Otherwise the algorithm is pretty similar to current algorithm to create the hasse_diagram, except that it avoids double counting (and hence can calculate the f_vector) without an explicit list of all faces.

The ticket will prepare, but not use, SIMD-instructions. Enabling them will be a subject of #27103.

FOLLOW-UPS:

  • implement calculation of entries in the flag-vector, this might be better, than the calculation in the face_lattice
  • Improve the calculation of properties of polytopes that depend on the face-lattice (f-vector,edges, ridges, k-faces in general, edge-graph, etc.)
  • Enable SIMD-instructions.

Attachments (2)

Explanation.pdf (210.1 KB) - added by gh-kliem 2 years ago.
Brief description with pictures, how the algorithm works
runtime.pdf (123.3 KB) - added by gh-kliem 2 years ago.
Comparison of runtime in comparison to polymake, given only the vertex-facet incidence matrix

Download all attachments as: .zip

Change History (244)

comment:1 Changed 2 years ago by gh-kliem

  • Branch set to u/gh-kliem/improve_f_vector_etc__for_polytopes

comment:2 Changed 2 years ago by chapoton

  • Commit set to d0dba618e853d21724639c3e59964fa0f6610a11

the branch is almost empty (no meaningful changes)


New commits:

d0dba61first push test

comment:3 Changed 2 years ago by git

  • Commit changed from d0dba618e853d21724639c3e59964fa0f6610a11 to 3f1600e34b4415e95bb4db84cedb04089f8af677

Branch pushed to git repo; I updated commit sha1. New commits:

a596e0cCreated a class CombinatorialType which is a wrapper for a cpp class
3f1600eadded the files

comment:4 Changed 2 years ago by gh-kliem

  • Authors set to Jonathan Kliem
  • Owner changed from (none) to gh-kliem

comment:5 Changed 2 years ago by gh-kliem

  • Summary changed from Improve f_vector etc. for polytopes to Improve f_vector, edges, ridges, dimension for polyhedra

comment:6 Changed 2 years ago by gh-kliem

  • Keywords f_vector face_lattic added

comment:7 Changed 2 years ago by gh-kliem

  • Component changed from combinatorics to geometry

comment:8 Changed 2 years ago by git

  • Commit changed from 3f1600e34b4415e95bb4db84cedb04089f8af677 to 03fe21ff70eee06eb6dc2db477a003b58997d3d5

Branch pushed to git repo; I updated commit sha1. New commits:

3b10c24moved the files to the polyhedron folder
03fe21fadded the new files

comment:9 Changed 2 years ago by git

  • Commit changed from 03fe21ff70eee06eb6dc2db477a003b58997d3d5 to 24949d9b8cacba08e72b0c1c028e6a6b25f5c9ec

Branch pushed to git repo; I updated commit sha1. New commits:

99eda99Before Renaming CombinatorialType to CombinatorialPolytope
7efe6a2After Renaming CombinatorialType to CombinatorialPolytope
24949d9This should be mostly done now. Some minor changes are missing, also documentation needs to be done'

comment:10 Changed 2 years ago by git

  • Commit changed from 24949d9b8cacba08e72b0c1c028e6a6b25f5c9ec to 8c5d21aba0921aae210bd28cd2e9c212ec3c0920

Branch pushed to git repo; I updated commit sha1. New commits:

8c5d21asome minor changes

comment:11 Changed 2 years ago by git

  • Commit changed from 8c5d21aba0921aae210bd28cd2e9c212ec3c0920 to a63c68f1eb5212448fd7e949306fdd7c26f53ac2

Branch pushed to git repo; I updated commit sha1. New commits:

a63c68fPreparing a function to get all k-faces

comment:12 Changed 2 years ago by git

  • Commit changed from a63c68f1eb5212448fd7e949306fdd7c26f53ac2 to 580980bbe979925797b02063bd28321dbd17efbd

Branch pushed to git repo; I updated commit sha1. New commits:

580980bsome work on generating all k-faces of the polyhedron

comment:13 Changed 2 years ago by git

  • Commit changed from 580980bbe979925797b02063bd28321dbd17efbd to 591ed2645b71f532d253e9ff55c5c484d362f252

Branch pushed to git repo; I updated commit sha1. New commits:

591ed26hasse_diagram is mostly working now, it is much faster than the old hasse_diagram of polyhedron

comment:14 Changed 2 years ago by gh-kliem

  • Description modified (diff)
  • Keywords face lattice flag vector edge graph ridge grapg added; face_lattic removed

comment:15 Changed 2 years ago by git

  • Commit changed from 591ed2645b71f532d253e9ff55c5c484d362f252 to 576905d8901190c042bba4251bf80e2f2eb8ec0f

Branch pushed to git repo; I updated commit sha1. New commits:

576905dflag vectors seem to work now

comment:16 Changed 2 years ago by git

  • Commit changed from 576905d8901190c042bba4251bf80e2f2eb8ec0f to 4a4171152dbdec4340328a52cb2b50f121f11176

Branch pushed to git repo; I updated commit sha1. New commits:

4a41711changed the name from CombinatorialPolytope to CombinatorialPolyhedron

comment:17 Changed 2 years ago by git

  • Commit changed from 4a4171152dbdec4340328a52cb2b50f121f11176 to e3454704fe64cfadfb5c54897e60dde9d0ad4ed3

Branch pushed to git repo; I updated commit sha1. New commits:

e345470This should be ready for review

comment:18 Changed 2 years ago by gh-kliem

  • Status changed from new to needs_review

comment:19 Changed 2 years ago by gh-kliem

I'm not experienced at what point a ticket should change its status to "needs review". Of course there is still stuff that I can do by myself like documentation and comments.

I would definitely be grateful for comments and help at this point. At this point everything should work at least I'm not aware of any bugs.

comment:20 follow-up: Changed 2 years ago by vdelecroix

As a start you can write examples (see the developer guide).

Next, it is not a very often not a good idea to write Python in C. It is hard to read and often difficult to do right (e.g. check memory allocation, ensure compatibility Python2/Python3). You should use Cython for that purpose, unless there is a very good reason for that.

As you use advanced CPU instructions you should check very carefully that your code does work on all architectures (ie Intel since Pentium II as well as AMD).

comment:21 Changed 2 years ago by git

  • Commit changed from e3454704fe64cfadfb5c54897e60dde9d0ad4ed3 to d897cd16dfab25e20936b4d67b0b5f7c393a48a2

Branch pushed to git repo; I updated commit sha1. New commits:

d897cd1Added Examples, also fixed the empty Polyhedron

comment:22 in reply to: ↑ 20 ; follow-ups: Changed 2 years ago by gh-kliem

I added examples.

I tried Cython, but didn't get the desired speedup. It was much faster than what is implemented in Polyhedron though. I started doing it in cython, but I couldn't get array access (via pointers) in a speed even close to C. Now with using intrinsics I'm close to 4 times as fast then without intrinsics. The crucial step in the algorithm is subset check as A & ~B == 0 for long bit vectors A and B.

We want to build a Database for Polytopes (similar to FindStat?) and thus we want to be able to fastly compute f_vectors even for large polytopes. This is the f_vector of a 20-dimensional counter example to the Hirsch conjecture. It only takes about 3 minutes to calculate now:

(1, 36425, 364250, 1846226, 6234909, 15556845, 30191256, 46918071, 59410131, 61931131, 53428829, 38194318, 22569116, 10954980, 4322157, 1364130, 336525, 62752, 8419, 754, 40, 1)

In Cython I was able to calculate this vector (or more important the edge graph) in something like 3 hours, in C it took me 20 minutes. Then I started doing bitwise operations and intrinsics and it is now down to 3 minutes with AVX2.

As for the CPU instructions: I'm prechecking the compiler flags. So if nothing works it just falls back to computing with uint64_t which should work on any machine.

As for memory leaks: It seems to work fine now. Python calls the dealloc() function at closup and when deleting the class and clears all the alloced memeory in C.

Replying to vdelecroix:

As a start you can write examples (see the developer guide).

Next, it is not a very often not a good idea to write Python in C. It is hard to read and often difficult to do right (e.g. check memory allocation, ensure compatibility Python2/Python3). You should use Cython for that purpose, unless there is a very good reason for that.

As you use advanced CPU instructions you should check very carefully that your code does work on all architectures (ie Intel since Pentium II as well as AMD).

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:23 in reply to: ↑ 22 ; follow-up: Changed 2 years ago by vdelecroix

Replying to gh-kliem:

I added examples.

I tried Cython, but didn't get the desired speedup.

That means that you don't know how to use Cython. Any C code can be written in plain Cython. Though I never said that you should rewrite everything using Cython. I am sorry if it was unclear. I adviced you to to rewrite the Python <-> C gluing part. More precisely, the C code would better not involve any Python at all. And you may write an independent Cython file that will call the C code appropriately.

comment:24 in reply to: ↑ 23 Changed 2 years ago by gh-kliem

Replying to vdelecroix:

Replying to gh-kliem:

I added examples.

I tried Cython, but didn't get the desired speedup.

That means that you don't know how to use Cython. Any C code can be written in plain Cython.

That is correct. I'm mostly happy if anything works at all. Once this is the case, I try to make it somewhat nice. It looked to me as if one was supposed to use memoryviews in Cython. They where the fastest working with plain C arrays. But then I couldn't initialize an array in a size determined at runtime. Anyway, as I understand having the code in C is not the problem here.

Though I never said that you should rewrite everything using Cython. I am sorry if it was unclear. I adviced you to to rewrite the Python <-> C gluing part. More precisely, the C code would better not involve any Python at all. And you may write an independent Cython file that will call the C code appropriately.

This sounds very reasonable. I will do so. When I first started with this, I didn't use Cython in between, so my C code had to return a Python object. But it makes sense to build a Python object in an environment that was meant for this. Building tuples etc. was a pain in C and it did always feel like a workaround. I never gave it any second thought though.

comment:25 Changed 2 years ago by gh-kliem

  • Cc jipilab added

comment:26 Changed 2 years ago by git

  • Commit changed from d897cd16dfab25e20936b4d67b0b5f7c393a48a2 to bc21ffa2b7e4058f01da08ecc86911c7dfab538a

Branch pushed to git repo; I updated commit sha1. New commits:

bc21ffaWork toward cleaing up the Python <-> C gluing part

comment:27 Changed 2 years ago by gh-kliem

  • Milestone changed from sage-8.5 to sage-8.7

comment:28 Changed 2 years ago by vdelecroix

These doctests are not reproducible.

    sage: P = polytopes.permutahedron(6)
    sage: %time CombinatorialPolyhedron(P).face_lattice(vertices=False,facets=False)
    CPU times: user 400 ms, sys: 20 ms, total: 420 ms
    Wall time: 380 ms
    Finite lattice containing 4684 elements
    sage: %time CombinatorialPolyhedron(P).face_lattice(vertices=True,facets=True)
    CPU times: user 2.48 s, sys: 60 ms, total: 2.54 s
    Wall time: 2.4 s
    Finite lattice containing 4684 elements
    sage: %time CombinatorialPolyhedron(P).face_lattice(vertices=True,facets=False) #default
    CPU times: user 1.87 s, sys: 48 ms, total: 1.92 s
    Wall time: 1.76 s
    Finite lattice containing 4684 elements

You should check that tests pass using sage -t --long FILENAME.

comment:29 Changed 2 years ago by vdelecroix

  • Status changed from needs_review to needs_work

The function CombinatorialPolyhedron::get_flag_number(PyObject* py_tuple) and many others are very likely to crash Sage (e.g. you do not take care of any error handling). I strongly advice you to avoid any Python in C/C++. The conversion tuple -> C++ vector is very easily done in Cython which automatically handles conversions and errors.

comment:30 Changed 2 years ago by git

  • Commit changed from bc21ffa2b7e4058f01da08ecc86911c7dfab538a to 152db94b0d7f496a7efab3f5afe33395e1e3baf1

Branch pushed to git repo; I updated commit sha1. New commits:

d20baa4Flag-vector: Fixed C <-> Python gluing
febaa72face and incidences: fixed Python <-> C gluing
152db94fixed Polyhedra with no facets

comment:31 Changed 2 years ago by git

  • Commit changed from 152db94b0d7f496a7efab3f5afe33395e1e3baf1 to b78d53372e111e7a34f77aea3735effd66cd2b09

Branch pushed to git repo; I updated commit sha1. New commits:

b78d533Initialization: Fixed Python <-> C gluing

comment:32 follow-up: Changed 2 years ago by jhpalmieri

This doesn't build for me on OS X:

gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -I./sage/geometry/polyhedron/combinatorial_polyhedron -I/Users/jpalmier/Desktop/Sage/git/sage/local/include -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 -I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/site-packages/numpy/core/include -I/Users/jpalmier/Desktop/Sage/git/sage/src -I/Users/jpalmier/Desktop/Sage/git/sage/src/sage/ext -Ibuild/cythonized -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 -c sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc -o build/temp.macosx-10.9-x86_64-2.7/sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/m4ri -I/Users/jpalmier/Desktop/Sage/git/sage/local/include -g -fPIC -Wall -O2 -mmmx -msse -msse2 -msse3 -O3 -march=native -std=c++11
In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:3:
In file included from /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/Python.h:88:
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:534:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj,     /* Object */
    ^~~~~~~~~
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:553:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj      /* Object */
    ^~~~~~~~~
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:575:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register const wchar_t *w,  /* wchar_t buffer */
    ^~~~~~~~~
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/unicodeobject.h:593:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register wchar_t *w,        /* wchar_t buffer */
    ^~~~~~~~~
In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:3:
In file included from /Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/Python.h:97:
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/stringobject.h:173:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj,     /* string or Unicode object */
    ^~~~~~~~~
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/stringobject.h:174:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register char **s,          /* pointer to buffer variable */
    ^~~~~~~~~
/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7/stringobject.h:175:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register Py_ssize_t *len    /* pointer to length variable or NULL
    ^~~~~~~~~
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:129:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(edges);
    ^
          []
./sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.h:95:32: note: allocated with 'new[]' here
        unsigned int **edges = new unsigned int *[maxnumberedges];
                               ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:130:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(ridges);
    ^
          []
./sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.h:96:33: note: allocated with 'new[]' here
        unsigned int **ridges = new unsigned int *[maxnumberedges];
                                ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:131:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(incidences);
    ^
          []
./sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.h:97:38: note: allocated with 'new[]' here
        unsigned long **incidences = new unsigned long *[maxnumberincidences]();
                                     ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:123:20: warning: unused variable 'j' [-Wunused-variable]
    unsigned int i,j;
                   ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:123:18: warning: unused variable 'i' [-Wunused-variable]
    unsigned int i,j;
                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:194:18: warning: unused variable 'dim' [-Wunused-variable]
    unsigned int dim = get_dimension();
                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:272:18: warning: unused variable 'dim' [-Wunused-variable]
    unsigned int dim = get_dimension();
                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:428:19: warning: unused variable 'n' [-Wunused-variable]
    unsigned long n;
                  ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:443:19: warning: unused variable 'n' [-Wunused-variable]
    unsigned long n;
                  ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:532:22: error: variable-sized object may not be initialized
    int addfacearray[lenfaces] = { };
                     ^~~~~~~~
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:585:32: error: use of undeclared identifier 'aligned_alloc'
        nextfaces_creator[i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8);
                               ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:607:32: error: use of undeclared identifier 'aligned_alloc'
        nextfaces_creator[i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8);
                               ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:655:20: warning: unused variable 'j' [-Wunused-variable]
    unsigned int i,j;
                   ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:689:20: warning: unused variable 'j' [-Wunused-variable]
    unsigned int i,j;
                   ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:733:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(array);
    ^
          []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:722:23: note: allocated with 'new[]' here
    uint64_t *array = new uint64_t [size_array]();
                      ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:719:20: warning: unused variable 'j' [-Wunused-variable]
    unsigned int i,j;
                   ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:720:18: warning: unused variable 'entry' [-Wunused-variable]
    unsigned int entry, position, value;
                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:791:9: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
        delete(saverarray);
        ^
              []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:773:34: note: allocated with 'new[]' here
    unsigned long **saverarray = new unsigned long *[const_len];
                                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:800:13: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
            delete(saverarray);
            ^
                  []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:773:34: note: allocated with 'new[]' here
    unsigned long **saverarray = new unsigned long *[const_len];
                                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:834:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete (saverarray);
    ^
          []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:773:34: note: allocated with 'new[]' here
    unsigned long **saverarray = new unsigned long *[const_len];
                                 ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:883:9: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
        delete(old_facets_walker);
        ^
              []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:867:43: note: allocated with 'new[]' here
        unsigned int *old_facets_walker = new unsigned int [size_three]();
                                          ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:967:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(array);
    ^
          []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:954:23: note: allocated with 'new[]' here
    uint64_t *array = new uint64_t [size_array]();
                      ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:993:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(array);
    ^
          []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:979:23: note: allocated with 'new[]' here
    uint64_t *array = new uint64_t [size_array]();
                      ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1026:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(array);
    ^
          []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1014:23: note: allocated with 'new[]' here
    uint64_t *array = new uint64_t [size_array]();
                      ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1049:5: warning: 'delete' applied to a pointer that was allocated with 'new[]'; did you mean 'delete[]'? [-Wmismatched-new-delete]
    delete(array);
    ^
          []
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1039:23: note: allocated with 'new[]' here
    uint64_t *array = new uint64_t [size_array]();
                      ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1163:31: error: use of undeclared identifier 'aligned_alloc'
        facets_allocator[i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8);
                              ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1188:33: error: use of undeclared identifier 'aligned_alloc'
        vertices_allocator[i] = aligned_alloc(chunksize/8,length_of_face_in_facet_repr*chunksize/8);
                                ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1220:40: error: use of undeclared identifier 'aligned_alloc'
            newfaces_allocator[i][j] = aligned_alloc(chunksize/8,length_of_face*chunksize/8);
                                       ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1270:64: error: use of undeclared identifier 'aligned_alloc'
                allfaces_allocator[dimension_to_allocate][i] = aligned_alloc(chunksize/8,length_of_face*chunksize/8);
                                                               ^
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:1272:75: error: use of undeclared identifier 'aligned_alloc'
                allfaces_facet_repr_allocator[dimension_to_allocate][i] = aligned_alloc(chunksize/8,length_of_face_in_facet_repr*chunksize/8);
                                                                          ^
29 warnings and 8 errors generated.

comment:33 in reply to: ↑ 32 Changed 2 years ago by gh-kliem

Thanks for going through the effort of building that on your machine.

It seems to me that there are the following issues:

  • aligned_alloc as used by me only works for C++11 and needs a different header in C++17
  • #include <Python.h> doesn't work at all, which it should, so this seems to be a seperate problem, this will go out, as all the functions requiring python objects where replaced
  • new/delete works differently on C++17 or my version is just not clean, I will take a look at whats going on

Replying to jhpalmieri:

This doesn't build for me on OS X:

comment:34 Changed 2 years ago by git

  • Commit changed from b78d53372e111e7a34f77aea3735effd66cd2b09 to dc0455d6a48a040fffe6f70f2d1082e96855c4c3

Branch pushed to git repo; I updated commit sha1. New commits:

73fac0eremoved Python in C, aligned_alloc should now work in C++17
2ffc402corrected deletion of arrays
dc0455dremoved unused variables, all errors and warnings reported by jhpalmieri should be gone now

comment:35 Changed 2 years ago by gh-kliem

I should have checked first..., this doesn't work

comment:36 Changed 2 years ago by git

  • Commit changed from dc0455d6a48a040fffe6f70f2d1082e96855c4c3 to 80f4e33dcecef1034f7edce36c112513b245d59d

Branch pushed to git repo; I updated commit sha1. New commits:

7557ecdfixing the calculation of the dimension
e32d0f6changed names of variables to not overload dimension of CombinatorialPolyhedron
80f4e33Fixed issue: edges, ridges and incidences should be initialized in order for delete to work properly

comment:37 Changed 2 years ago by git

  • Commit changed from 80f4e33dcecef1034f7edce36c112513b245d59d to a89c37b4519548bb512dd5f9b6934cce0772b250

Branch pushed to git repo; I updated commit sha1. New commits:

a89c37bMore work with trivial Polyehedra, they should work now

comment:38 Changed 2 years ago by chapoton

++ EXAMPLE::

should be

++ EXAMPLES::

comment:39 Changed 2 years ago by git

  • Commit changed from a89c37b4519548bb512dd5f9b6934cce0772b250 to 0eedbb966da75f6f11bb0b03ff19dfe6a93cb4fb

Branch pushed to git repo; I updated commit sha1. New commits:

0eedbb9fixed an issue with unbounded Polyhedra and CombinatorialPolyhedron.faces(0), also fixed Halfspaces

comment:40 Changed 2 years ago by git

  • Commit changed from 0eedbb966da75f6f11bb0b03ff19dfe6a93cb4fb to b37feb7c30468705d151fb58c501968ce07b2371

Branch pushed to git repo; I updated commit sha1. New commits:

b37feb7all tests passed, however there are still examples missing starting at the function faces

comment:41 Changed 2 years ago by git

  • Commit changed from b37feb7c30468705d151fb58c501968ce07b2371 to 829ec2acbfbf3360c8b94184935a097541a744ef

Branch pushed to git repo; I updated commit sha1. New commits:

d8223e7Added a roughly equivalent Algorithm to f_vector, more examples
829ec2aDocumentation in base.pyx done

comment:42 Changed 2 years ago by git

  • Commit changed from 829ec2acbfbf3360c8b94184935a097541a744ef to b513eb2a0e9b547297ef5c6ac4b9f95c1f1a184b

Branch pushed to git repo; I updated commit sha1. New commits:

70b5a7aremoved all examples at beginning of file
c339851added a face_iterator
b513eb2CombinatorialPolyhedron inherits from SageObject now

comment:43 Changed 2 years ago by git

  • Commit changed from b513eb2a0e9b547297ef5c6ac4b9f95c1f1a184b to a176af156c820c31791e1dcef05b3e62e70e5b25

Branch pushed to git repo; I updated commit sha1. New commits:

4b7948fadded a __reduce__ function to pickle/unpickle correctly,
a176af1added copyright license in hasse_diagram.cc

comment:44 Changed 2 years ago by git

  • Commit changed from a176af156c820c31791e1dcef05b3e62e70e5b25 to a2f90adfbeba067766b7538cadd50830015eda41

Branch pushed to git repo; I updated commit sha1. New commits:

a2f90adcorrected edges and ridges a polyhedron with two vertices

comment:45 Changed 2 years ago by git

  • Commit changed from a2f90adfbeba067766b7538cadd50830015eda41 to 46f95556da205a8b2cfe28c4aeeff807321714c1

Branch pushed to git repo; I updated commit sha1. New commits:

46f9555added a macro to ensure aligned_alloc exists,

comment:46 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:47 follow-up: Changed 2 years ago by jhpalmieri

Still doesn't build on OS X:

gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -I./sage/geometry/polyhedron/combinatorial_polyhedron -I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include -I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7 -I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/lib/python2.7/site-packages/numpy/core/include -I/Users/palmieri/Desktop/Sage_stuff/git/sage/src -I/Users/palmieri/Desktop/Sage_stuff/git/sage/src/sage/ext -Ibuild/cythonized -I/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7 -c sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc -o build/temp.macosx-10.9-x86_64-2.7/sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -O3 -march=native -std=c++11
In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:13:
In file included from /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/Python.h:88:
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:534:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj,     /* Object */
    ^~~~~~~~~
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:553:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj      /* Object */
    ^~~~~~~~~
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:575:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register const wchar_t *w,  /* wchar_t buffer */
    ^~~~~~~~~
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/unicodeobject.h:593:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register wchar_t *w,        /* wchar_t buffer */
    ^~~~~~~~~
In file included from sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:13:
In file included from /Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/Python.h:97:
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/stringobject.h:173:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj,     /* string or Unicode object */
    ^~~~~~~~~
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/stringobject.h:174:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register char **s,          /* pointer to buffer variable */
    ^~~~~~~~~
/Users/palmieri/Desktop/Sage_stuff/git/sage/local/include/python2.7/stringobject.h:175:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register Py_ssize_t *len    /* pointer to length variable or NULL
    ^~~~~~~~~
sage/geometry/polyhedron/combinatorial_polyhedron/hasse_diagram.cc:717:22: error: variable-sized object may not be initialized
    int addfacearray[constlenfaces] = { };
                     ^~~~~~~~~~~~~
7 warnings and 1 error generated.

Cython would be so much easier.

comment:48 Changed 2 years ago by git

  • Commit changed from 46f95556da205a8b2cfe28c4aeeff807321714c1 to 1971dd77286848ccb7f069c3b0f71feb7c197272

Branch pushed to git repo; I updated commit sha1. New commits:

6ae3dd4Fixed issue with PopCount, PopCount requires header immintin, which was only included when AVX2 was availabe
05635c9replace iterator.next() by next(iterator) in test for Python 3
1971dd7removed geometry/all.py from ticket, removed geometry/polyhedron/base.py from ticket

comment:49 Changed 2 years ago by git

  • Commit changed from 1971dd77286848ccb7f069c3b0f71feb7c197272 to de57d7f3af7eb52f8ed2cee17184a6cbec3fb134

Branch pushed to git repo; I updated commit sha1. New commits:

ae0d131removed commend in module-list.py, march=native is needed
f27a2efremoved Python.h
de57d7ffixed headers, removed Python.h, moved declaration of constlenfaces to the beginning of function

comment:50 in reply to: ↑ 47 Changed 2 years ago by gh-kliem

Should be fixed.

I don't know why I didn't remove Python.h, it sure wasn't needed anymore. (Except that it included stdint). However, the pure inclusion of the Python module in C should not give an error.

Replying to jhpalmieri:

Still doesn't build on OS X:

Cython would be so much easier.

For me, Cython was not easier. I couldn't get the things done the way I wanted. Once you know what should be done in C exactly, then it is probably easier. Now that I have written the code in C++, I could probably do it in Cython as well. When I searched for specific questions in Cython, I just couldn't get any result, but in C or C++ there are tons of helps on the web that helped me. I am a complete newbie in programming. It feels to me that I aquired at least half of my knowledge through this project. From Cython to C/C++ I had a speedup of about 20 on large Polytopes, probably just because translating it to pure C/C++ helped me better understand what the machine is doing and can be doing.

comment:51 Changed 2 years ago by git

  • Commit changed from de57d7f3af7eb52f8ed2cee17184a6cbec3fb134 to 882ce7189a0a1b4c6d29baaa6c01e13bb16f5c71

Branch pushed to git repo; I updated commit sha1. New commits:

882ce71Interchanged long tests

comment:52 Changed 2 years ago by git

  • Commit changed from 882ce7189a0a1b4c6d29baaa6c01e13bb16f5c71 to f5c87d83fc288f0cde3767e39713a957dfbfa270

Branch pushed to git repo; I updated commit sha1. New commits:

f5c87d8I missed a polytopes.Polyhedron(7), this was taken out now

comment:53 Changed 2 years ago by git

  • Commit changed from f5c87d83fc288f0cde3767e39713a957dfbfa270 to de03b8be97be9e77bfdbc27b142509cec353b947

Branch pushed to git repo; I updated commit sha1. New commits:

ee86475this should work on 32bit now, I replaced uint64_t by a macro, which first determines wether we are 64 or 32bi,
de03b8badded doctest to _repr_ and _record_all_faces

comment:54 Changed 2 years ago by gh-kliem

  • Description modified (diff)
  • Summary changed from Improve f_vector, edges, ridges, dimension for polyhedra to Implement the class CombinatorialPolyhedron

comment:55 follow-up: Changed 2 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Some purely technical points about the programming:

  1. We generally discourage putting Extension parameters in module_list.py. Better use # distutils declarations in Cython files. See https://cython.readthedocs.io/en/latest/src/userguide/source_files_and_compilation.html#source-files-and-compilation for examples.
  1. -march=native is not acceptable since we want to distribute binaries. Moreover, it makes no sense to compile just this specific file with -march=native. If you want to add -march=native, it should probably be added as compilation flag for all packages (or at least for Python, such that it applies to all Python packages). If you want to go through with this, you should open a new ticket for that. Also note that the option -march=native itself is not portable: there be a check that the compiler actually understands it.
  1. The -O3 option is the default, so that's redundant.
  1. You have very long lines in your sources. You should try to wrap them to less than 80 characters per line.
  1. You're adding a lot of C/Cython code without a single sig_on/sig_check. That's suspicious as such code cannot be interrupted. See https://cysignals.readthedocs.io/en/latest/interrupt.html#interrupt-handling
  1. While you're at it, you could also use the cysignals memory allocation functions instead of PyMem_....
  1. hasse_diagram.cc contains various trivial functions which could easily be replaced by Cython. For example, the various accessor functions could be replaced by just accessing the attributes in Cython (this requires that the class CombinatorialPolyhedron is actually declared in Cython). Also delete_CombinatorialPolyhedron(C) could be replaced by just del C.
  1. This is just advice: it's also possible to just include the .cc file in the .pyx file using cdef extern from "hasse_diagram.cc". That way, you can avoid the .h file and you give more optimization opportunities to the compiler, since everything is compiled in one C++ file.
  1. I'm very worried about portability: you seem to be using a lot of compiler-specific and CPU-specific code. I don't know whether anything will actually break, but there is a substantial risk.
  1. Typo: memomory -> memory
Last edited 2 years ago by jdemeyer (previous) (diff)

comment:56 in reply to: ↑ 22 Changed 2 years ago by jdemeyer

Replying to gh-kliem:

In Cython I was able to calculate this vector (or more important the edge graph) in something like 3 hours, in C it took me 20 minutes.

Just to add to what Vincent said: if your Cython code is substantially slower than your C/C++ code, you're doing it wrong. When using Cython properly, it should have the same speed as pure C/C++.

That being said, I'm not saying that you should use Cython instead of C++, just that you could.

comment:57 follow-up: Changed 2 years ago by jdemeyer

Another minor comment: uint64_t_or_uint32_t is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type like unsigned long or size_t?

Last edited 2 years ago by jdemeyer (previous) (diff)

comment:58 Changed 2 years ago by git

  • Commit changed from de03b8be97be9e77bfdbc27b142509cec353b947 to 2df5d2ef760981ae2cddc4e23b87021aeb6f20e4

Branch pushed to git repo; I updated commit sha1. New commits:

7904eabLots of comments for hasse_diagram.pxd as on how to use the functions
2df5d2esome remark for later, edges of an unbounded polyhedron needs to figured out yet

comment:59 Changed 2 years ago by git

  • Commit changed from 2df5d2ef760981ae2cddc4e23b87021aeb6f20e4 to 0a95629eb7adeede726a1fdd1d8993ba72ff5eb6

Branch pushed to git repo; I updated commit sha1. New commits:

0a95629corrected multiline comment

comment:60 Changed 2 years ago by git

  • Commit changed from 0a95629eb7adeede726a1fdd1d8993ba72ff5eb6 to 96c0a3551f09a96a6edd79a8eaccad846991e3f5

Branch pushed to git repo; I updated commit sha1. New commits:

96c0a35Removed Compile arguments from module_list,

comment:61 Changed 2 years ago by git

  • Commit changed from 96c0a3551f09a96a6edd79a8eaccad846991e3f5 to ae08e2588ba48d1b36d2b34ff87f0689f9418ef9

Branch pushed to git repo; I updated commit sha1. New commits:

ae08e25corrected memory

comment:62 in reply to: ↑ 57 ; follow-ups: Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Another minor comment: uint64_t_or_uint32_t is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type like unsigned long or size_t?

Any suggestions? Maybe 'uint64/32_t'? I don't like the name either...

Also, on 64bit machines, I really need to know that this is uint64_t. On 32-bit machines that it is uint32_t. As far as I understand size_t can be anything. Also unsigned long should usually be uint64_t, but there is no guarantee on it. Is there?

comment:63 in reply to: ↑ 62 ; follow-up: Changed 2 years ago by vdelecroix

Replying to gh-kliem:

Replying to jdemeyer:

Another minor comment: uint64_t_or_uint32_t is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type like unsigned long or size_t?

Any suggestions? Maybe 'uint64/32_t'? I don't like the name either...

Also, on 64bit machines, I really need to know that this is uint64_t. On 32-bit machines that it is uint32_t. As far as I understand size_t can be anything. Also unsigned long should usually be uint64_t, but there is no guarantee on it. Is there?

There is no guaranty at all (e.g. look at the header of gmp where they define mp_limb_t). I don't understand what is the problem with uint64_t and uint32_t... These are supposed to be standard and portable. Contrarily to unsigned long or size_t. Though I wonder why gmp avoid using them...

comment:64 in reply to: ↑ 55 ; follow-up: Changed 2 years ago by gh-kliem

Thanks for the comments and help.

Replying to jdemeyer:

Some purely technical points about the programming:

  1. We generally discourage putting Extension parameters in module_list.py. Better use # distutils declarations in Cython files. See https://cython.readthedocs.io/en/latest/src/userguide/source_files_and_compilation.html#source-files-and-compilation for examples.

Done. Once I knew what to look for, I found a good example (combinat/partitions.pyx).

  1. -march=native is not acceptable since we want to distribute binaries. Moreover, it makes no sense to compile just this specific file with -march=native. If you want to add -march=native, it should probably be added as compilation flag for all packages (or at least for Python, such that it applies to all Python packages). If you want to go through with this, you should open a new ticket for that. Also note that the option -march=native itself is not portable: there be a check that the compiler actually understands it.

It took be a bit to figure this one out. A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).

If compiled by GCC >= 6 there would be multiple versions of the code available. At runtime the decision is made according to availability of the intrinsics. This way a build be used by different machines (e.g. Network Versions of it or binaries).

At compile time we can then decide for 64 or 32 bits and check wether it is compiled with GCC >= 6.

  1. The -O3 option is the default, so that's redundant.

Done.

  1. You have very long lines in your sources. You should try to wrap them to less than 80 characters per line.

I will take care of that.

  1. You're adding a lot of C/Cython code without a single sig_on/sig_check. That's suspicious as such code cannot be interrupted. See https://cysignals.readthedocs.io/en/latest/interrupt.html#interrupt-handling

combinat/partitions.pyx seems to be a good example. There this is done as well. I noticed this problem. When doing long calculations I had to kill sage the hard way, when I wanted to do so.

  1. While you're at it, you could also use the cysignals memory allocation functions instead of PyMem_....
  1. hasse_diagram.cc contains various trivial functions which could easily be replaced by Cython. For example, the various accessor functions could be replaced by just accessing the attributes in Cython (this requires that the class CombinatorialPolyhedron is actually declared in Cython). Also delete_CombinatorialPolyhedron(C) could be replaced by just del C.

I honestly don't know how to do this. At the moment I am thinking about actually importing the class CombinatorialPolyhedron? in C++ a number of times with different macros. This way I avoid the multi-version function being decided on a low level, which would slow things done a lot and would break in-lines etc. I could define the functions in the class a number of times, but this would make it even less readable.

Anyway, I'm still thinking about it and trying to figure out what to do.

  1. This is just advice: it's also possible to just include the .cc file in the .pyx file using cdef extern from "hasse_diagram.cc". That way, you can avoid the .h file and you give more optimization opportunities to the compiler, since everything is compiled in one C++ file.

Great, I like this much better. For the extension thing, one was supposed to use a header. But now I'm able to work without it. I always found it a pain to work with header and cc.

  1. I'm very worried about portability: you seem to be using a lot of compiler-specific and CPU-specific code. I don't know whether anything will actually break, but there is a substantial risk.

See above. GCC sets up multiple functions and at runtime the correct function is being called. If one does not compile with GCC >= 6 then I suggest not using intrinsics at all.

There are not too many scenarios:

  • AVX2 (maybe delete this, if there are no substantial losses doing it with AVX-only, however the instructions are easier with AVX2.)
  • AVX, but not AVX2
  • popcnt, but not AVX
  • SSE4.1
  • default

This is 64-bit. I have to check out the scenarios for 32-bit yet.

  1. Typo: memomory -> memory

Done.

comment:65 in reply to: ↑ 63 Changed 2 years ago by gh-kliem

Replying to vdelecroix:

Replying to gh-kliem:

Replying to jdemeyer:

Another minor comment: uint64_t_or_uint32_t is a very clunky type name. Couldn't you use a more descriptive name? Or use a standard type like unsigned long or size_t?

Any suggestions? Maybe 'uint64/32_t'? I don't like the name either...

Also, on 64bit machines, I really need to know that this is uint64_t. On 32-bit machines that it is uint32_t. As far as I understand size_t can be anything. Also unsigned long should usually be uint64_t, but there is no guarantee on it. Is there?

There is no guaranty at all (e.g. look at the header of gmp where they define mp_limb_t). I don't understand what is the problem with uint64_t and uint32_t... These are supposed to be standard and portable. Contrarily to unsigned long or size_t. Though I wonder why gmp avoid using them...

I wasn't sure whether uint64_t is always available on 32-bit machines. If this is the case, I can of course use it. In order to do popcount I need to do a pointer typecast, but that should be fine and the only problem then. Some patchbot gave me an error message about _mm_popcnt_u64 not being defined, which seems to be the case, if the machine is 32-bit.

comment:66 Changed 2 years ago by jhpalmieri

You probably know this, but just in case: on OS X, clang is used, not gcc.

comment:67 in reply to: ↑ 62 Changed 2 years ago by jdemeyer

Replying to gh-kliem:

Also, on 64bit machines, I really need to know that this is uint64_t.

What's your definition of a 64-bit machine (or 32-bit machine)?

comment:68 follow-up: Changed 2 years ago by jdemeyer

A more or less equivalent question: why do you really need to know that the type is uint64_t on a 64-bit machine and uint32_t on a 32-bit machine?

Last edited 2 years ago by jdemeyer (previous) (diff)

comment:69 in reply to: ↑ 64 ; follow-ups: Changed 2 years ago by jdemeyer

Replying to gh-kliem:

A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).

That's overthinking it for a generic math package like Sage. Almost all casual Sage users are not going to care how fast this code really runs.

But you probably misunderstood me: I didn't mean that -march=native was a bad idea, just that it should be enabled more carefully. And also not for this one specific file only, that would be just strange.

comment:70 in reply to: ↑ 68 ; follow-up: Changed 2 years ago by gh-kliem

Replying to jdemeyer:

A more or less equivalent question: why do you really to know that the type is uint64_t on a 64-bit machine and uint32_t on a 32-bit machine?

#if INTPTR_MAX == INT64_MAX

This is what I read somewhere. If this is for some reason is not set at all, it uses uint32_t and more important it will not call _mm_popcnt_u64, which does not seem to be defined for 32bit machines, even if the processor has POPCNT. I figured this is why the following patchbot run failed:

https://patchbot.sagemath.org/log/26887/Ubuntu/14.04/i686/3.13.0-164-generic/arando/2019-01-22%2009:12:47?short

comment:71 in reply to: ↑ 69 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Replying to gh-kliem:

A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).

That's overthinking it for a generic math package like Sage. Almost all casual Sage users are not going to care how fast this code really runs.

Probably. The more important question is whether something can be calculated or not. If one then wants to generate e.g. the face_lattice from the CombinatorialPolyhedron, initalizing this is much slower than anything in this module.

But you probably misunderstood me: I didn't mean that -march=native was a bad idea, just that it should be enabled more carefully. And also not for this one specific file only, that would be just strange.

So what you are suggesting is the following(?): Leave it as it is and delete -march=native. This should then somehow be added to Sage's build process (as an option?), so that one can build a more effective version, if one wants to. The pre-build binaries might then take 4-times as long, but are stable.

This would then also be a portable way of using intrinsics, such that when in any other module it seems helpful, one can just copy-paste from this code.

comment:72 in reply to: ↑ 70 ; follow-up: Changed 2 years ago by jdemeyer

Replying to gh-kliem:

Replying to jdemeyer:

A more or less equivalent question: why do you really to know that the type is uint64_t on a 64-bit machine and uint32_t on a 32-bit machine?

#if INTPTR_MAX == INT64_MAX

That solves your problem: in that case, the type uint64_t_or_uint32_t that you're looking for is uintptr_t.

comment:73 in reply to: ↑ 72 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Replying to gh-kliem:

Replying to jdemeyer:

A more or less equivalent question: why do you really to know that the type is uint64_t on a 64-bit machine and uint32_t on a 32-bit machine?

#if INTPTR_MAX == INT64_MAX

That solves your problem: in that case, the type uint64_t_or_uint32_t that you're looking for is uintptr_t.

When googling something as uintptr_t, it seems like nothing is guaranteed. Also it seems like uint64_t is always available. The only problem was with the _mm_popcnt_u64. Maybe I just do a typecast there and replace uint64_t_or_uint32_t by uint64_t again.

comment:74 in reply to: ↑ 69 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Replying to gh-kliem:

A solution would be to use function multiversioning as available in GCC >= 6 (https://hannes.hauswedell.net/post/2017/12/09/fmv/).

That's overthinking it for a generic math package like Sage. Almost all casual Sage users are not going to care how fast this code really runs.

But you probably misunderstood me: I didn't mean that -march=native was a bad idea, just that it should be enabled more carefully. And also not for this one specific file only, that would be just strange.

The question wether -march=native can be included is now subject of the ticket #27122.

comment:75 Changed 2 years ago by git

  • Commit changed from ae08e2588ba48d1b36d2b34ff87f0689f9418ef9 to 61dae2c3ff721a0d8a3619f7d43f8dd2fb8bacc3

Branch pushed to git repo; I updated commit sha1. New commits:

61dae2cConverted base.pyx to PEP 8

comment:76 Changed 2 years ago by gh-kliem

  • Description modified (diff)
  • Keywords grapg removed

comment:77 Changed 2 years ago by gh-kliem

I suppose it makes sense to disable all the intrinsics for this ticket (not done yet) and enable them later (#27103). This way this ticket does not depend on #27122.

Also, if there is anything not working with CombinatorialPolyhedron once -march=native gets enabled, this would produce an error message for ticket #27122, which I would like to prevent from happening.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:78 Changed 2 years ago by git

  • Commit changed from 61dae2c3ff721a0d8a3619f7d43f8dd2fb8bacc3 to 95ac8adf2689c6dd1cebffc015038db35cddc141

Branch pushed to git repo; I updated commit sha1. New commits:

95ac8adremoved Header file hasse_diagram.cc

comment:79 Changed 2 years ago by git

  • Commit changed from 95ac8adf2689c6dd1cebffc015038db35cddc141 to 759e024e429805d9e07431c207879d555449e1e1

Branch pushed to git repo; I updated commit sha1. New commits:

759e024actual remove in git

comment:80 Changed 2 years ago by git

  • Commit changed from 759e024e429805d9e07431c207879d555449e1e1 to 6fd5f55050fc2383848a0cc1d1591ddcda0bcd3f

Branch pushed to git repo; I updated commit sha1. New commits:

0878d97simplified get_next_level
8f291e9There is now an independent face_iterator
6fd5f55reduced other functions to face iterator

comment:81 Changed 2 years ago by gh-kliem

It seems like everything boils down to a face iterator.

At least in C++ there doesn't seems to be a difference between the previous f_vector calculation and the calculation now being done by iterating over all faces and then adding at the correct dimension.

I guess the correct 'subclass' of CombinatorialPolyhedron should then be an iterator and not a copy of itself in C++.

I guess I could do it all in Cython using PyMem_Malloc etc. However, as this does not support any overalignment, the iterator would need more memory then needed. But this seems to be ok. About 30kB extra memory for the iterator over a 20-dimensional Polyhedron with 40 facets. However, when recording all faces of this, the overhead might be almost as big as the actual data size. Then again, why would you want a list of 400 million faces, if you have an iterator.

comment:82 Changed 2 years ago by git

  • Commit changed from 6fd5f55050fc2383848a0cc1d1591ddcda0bcd3f to 34bec35a724be4a00c044d44a89ccf66dadb071d

Branch pushed to git repo; I updated commit sha1. New commits:

34bec35the index of the faces changed, so the doctest needs an update

comment:83 Changed 2 years ago by git

  • Commit changed from 34bec35a724be4a00c044d44a89ccf66dadb071d to cf249ff788fb9972e59f51f8ff2753fa47b5edf5

Branch pushed to git repo; I updated commit sha1. New commits:

c04f83cprepared a face iterator that works mostly in cython
40e4b5fadded the cc-file
cf249ffdimension and f_vector work with the new iterator now

comment:84 Changed 2 years ago by git

  • Commit changed from cf249ff788fb9972e59f51f8ff2753fa47b5edf5 to 6751885eba7ae1713085bc8e562345a54c1c616a

Branch pushed to git repo; I updated commit sha1. New commits:

6751885the user can now correctly interupt

comment:85 Changed 2 years ago by git

  • Commit changed from 6751885eba7ae1713085bc8e562345a54c1c616a to abe18eb43a601863cbff7ac8587b2915c780069c

Branch pushed to git repo; I updated commit sha1. New commits:

abe18ebsome work towards replacing ridges

comment:86 Changed 2 years ago by git

  • Commit changed from abe18eb43a601863cbff7ac8587b2915c780069c to b14909932d9529794a223b198febca9f0fbebf91

Branch pushed to git repo; I updated commit sha1. New commits:

b149099calculation of the f_vector is now done mostly in main class `CombinatorialPolyhedron`

comment:87 Changed 2 years ago by git

  • Commit changed from b14909932d9529794a223b198febca9f0fbebf91 to 6ce801cb4bfb7f0738c32507158612eeed6f3717

Branch pushed to git repo; I updated commit sha1. New commits:

0b76897edges updated
ef84927updated calculating the ridges
c1cac5cTests added, that edges() and ridges() can indeed be interrupted
0b80d3fadded calculation of f_vector while doing the edges
b46b81eimproved speed of getting vertex repr by only considering non-zero entries
6ce801cupgraded the face iterator

comment:88 Changed 2 years ago by git

  • Commit changed from 6ce801cb4bfb7f0738c32507158612eeed6f3717 to f3b95783ef8610eaf27d6425eb7e4fe4139ddb33

Branch pushed to git repo; I updated commit sha1. New commits:

cc96f9fDimension can be interrupted correctly, this ensure that getnextlevel() can be computed in reasonable time
f3b9578Created a `ListOfAllFaces` in Cython, preparing final steps to get rid of hasse_diagramm.cc

comment:89 Changed 2 years ago by git

  • Commit changed from f3b95783ef8610eaf27d6425eb7e4fe4139ddb33 to 6ac0773f5486a5d1cb68635edb0c893ca7fb980a

Branch pushed to git repo; I updated commit sha1. New commits:

8809294A list of allfaces works correctly now
0e98ab6renaming classes
6ac0773can now get incidences of faces

comment:90 Changed 2 years ago by git

  • Commit changed from 6ac0773f5486a5d1cb68635edb0c893ca7fb980a to c3f4ef19796738befea316a0bf9162a74bb422d9

Branch pushed to git repo; I updated commit sha1. New commits:

c3f4ef1the FaceLattice works now, also removed CombinatorialPolyhedron.flag() for later ticket

comment:91 Changed 2 years ago by gh-kliem

  • Description modified (diff)
  • Keywords flag vector removed

New commits:

c3f4ef1the FaceLattice works now, also removed CombinatorialPolyhedron.flag() for later ticket

comment:92 Changed 2 years ago by git

  • Commit changed from c3f4ef19796738befea316a0bf9162a74bb422d9 to 2ce8561b52996dcffc3e8b5aa77303acafb889ea

Branch pushed to git repo; I updated commit sha1. New commits:

dea4f5bI never used the Bitrepresentation of the vertices, so I got rid of it
3832480replaced versions of faces(-1) and faces(dimension), also the Bitrepresentation of vertices stays in for returning the vertices
422e2earemoved the cpp-CombinatorialPolyhedron from CombinatorialPolyhedron
e61dbfdremoved hasse_diagram.cc
2ce8561simplified helper.cc

comment:93 Changed 2 years ago by gh-kliem

This ticket is now pretty much where I want it to be. I still need to go through everything and make comments and clean up.

Even though everything got longer now, I think the structure is a lot easier. There is two main tools now:

A FaceIterator. This is not a proper iterator, as I want it to be flexible with the output. But basically it iterates over all faces and for each face one can get output like its dimension or facet-representation. The FaceIterator is used to calculate the f_vector, edges, ridges etc. Also it calculates ListOfAllFaces.

ListOfAllFaces is a list of all faces ordered by dimension. Once all faces are initialized, one can sort the level-sets, as to calculated quickly the actual face-lattice.

There are some more classes like ListOfFaces. This can be used to e.g. store all facets in Bit-Representation. The nice thing about it is, that it automatically takes care of the memory allocated. So when creating a ListOfFaces, one can use void ** without having to worry about the memory allocation.

The methods actually defined in C++ now, should be easy to understand. There are mostly there, because C I can do something as #define chunktype uint64_t and C will not complain about an unknown data-type chunktype.

comment:94 Changed 2 years ago by stumpc5

  • Cc tscrim added

It might be worth adding some timings against the current state-of-the-art implementation in polymake to show how fast this implementation really is. One striking example is

    sage: P = polytopes.permutahedron(7)
    sage: P1 = CombinatorialPolyhedron(P)
    sage: facets_lst = map(list,P1.facets(names=False))
    sage: P2 = polymake("my $P = new Polytope(VERTICES_IN_FACETS=>%s);"%facets_lst)
    sage: %time P1.f_vector()
    CPU times: user 125 ms, sys: 0 ns, total: 125 ms
    Wall time: 125 ms
    (1, 5040, 15120, 16800, 8400, 1806, 126, 1)
    sage: %time P2.F_VECTOR
    CPU times: user 39 ms, sys: 4.71 ms, total: 43.7 ms
    Wall time: 13.4 s
    5040 15120 16800 8400 1806 126

This is, of course, just a workaround to access polymake directly from within sage (it requires the experimental package polymake to be installed). The same computation in a freshly installed polymake-3.2 took roughly the same time.

I am not sure how to include this into the doctests because the difference only becomes strikingly visible when polymake takes at least seconds.

@Travis: I would appreciate if you could have a look at this ticket and the implementation in C / Cython :-)

comment:95 follow-ups: Changed 2 years ago by tscrim

A very general question: How much of this are you actually using stuff that is within Sage (and Cython)? In particular, I am wondering if there is a benefit to separating this out into a little standalone package that gets included in Sage with some linking. To me, you could leave the features that use parts of Sage, e.g., ridge_graph, in the Sage implementation part, but have a good part of it independent.

typo? partitions_c.cc -> hasse_diagram.cc?

# The actual algorithm is implemented in the C++ file partitions_c.cc

typo: (Knwon (also that parenthetical should not be its own sentence but combined with the previous one).

Name conflict:

from cpython cimport array
import array

For _data and _memory, could you be more specific than a void pointer?

In ListOfFaces, self.data() -> self._data, especially since it is internal (and data() is not inlined, but it should be, as with any cdef simple accessors).

Do you really need the class ListOfListOfFaces? That seems like a bit of overkill as it only is used in 1 place and not for anything useful.

Python convention for error messages should be start with a lowercase letter and no full-stop/period at the end.

You should not have get_next_level wrapped in a sig_on/sig_off. That should do its own signal handling.

Instead of blank catching of exceptions to return -2, you should use the builtin Cython syntax to raise errors: e.g., in integer.pyx:

cpdef int _cmp_(left, right) except -2:

I do not think how you are handling the memory is the best way. For example, let us consider _calculate_f_vector. Instead of catching an exception raised by that function (which you would make it return an int and have except -1:) in f_vector and letting that code free the memory before propagating the error up, you have a big try/except inside the _calculate_f_vector, which then returns okay, and have f_vector create a new error.

Any cdef that is a void cannot raise an error; see the parenthetical above.

You should make a .pxd file with the relevant cdef class and methods set there. It works like a header file and allows people to cimport objects. So that way people can make subclasses in different files.

I might have more comments, but these are what I got from a quick lookover.

comment:96 Changed 2 years ago by git

  • Commit changed from 2ce8561b52996dcffc3e8b5aa77303acafb889ea to 7e7147d6d1543459011517017820083e902e08cc

Branch pushed to git repo; I updated commit sha1. New commits:

b391911removed some outdated remarks
7e7147dremoved hasse_diagram.cc, which is no longer needed

comment:97 Changed 2 years ago by git

  • Commit changed from 7e7147d6d1543459011517017820083e902e08cc to 1e0f36f94fced98928c556b872a58888584e737e

Branch pushed to git repo; I updated commit sha1. New commits:

1e0f36ffixed the order of facets in __reduce__(), fixed a bug in face_iter for some polyhedra

comment:98 follow-up: Changed 2 years ago by jdemeyer

I agree with Travis that error checking could be much improved: use error return values.

Also, instead of using sig_malloc and then checking for NULL, use check_malloc which automatically does that check. Even better, replace sig_malloc(a * sizeof(T)) by check_allocarray(a, sizeof(T)).

comment:99 in reply to: ↑ 95 ; follow-up: Changed 2 years ago by jdemeyer

Replying to tscrim:

Name conflict:

from cpython cimport array
import array

As far as I can tell, this isn't even used anywhere.

comment:100 in reply to: ↑ 99 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Replying to tscrim:

Name conflict:

from cpython cimport array
import array

As far as I can tell, this isn't even used anywhere.

Yes, this can go out now. I copied this from the documentation: https://cython.readthedocs.io/en/latest/src/tutorial/array.html.

comment:101 in reply to: ↑ 95 Changed 2 years ago by gh-kliem

Replying to tscrim:

For _data and _memory, could you be more specific than a void pointer?

I can do so. This was due to a wrong assumption. It turns out (not suprisingly I guess) that

_mm256_testc_si256((two),(one));

takes just as long as

one = _mm256_load_si256((const __m256i*)&(A));
two = _mm256_load_si256((const __m256i*)&(B));
_mm256_testc_si256((two),(one));

So I can use uint64_t until I actually need registers and than load them directly. This also explains, why people out there don't save stuff in formats like __m256i *.

comment:102 follow-up: Changed 2 years ago by jdemeyer

Also, this ListOfListOfPointers and ListOfFaces stuff seems to be reinventing the wheel. For example, since you're using C++ anyway, you could use std::vector<> or whatever. There is also sage.ext.memory_allocator.MemoryAllocator which seems to have some overlap with what you need.

comment:103 follow-up: Changed 2 years ago by jdemeyer

I consider these small accessor methods unpythonic:

    cdef size_t nr_lists(self):
        return self._nr_lists

What's wrong with just calling the attribute nr_lists and accessing that directly?

comment:104 in reply to: ↑ 103 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

I consider these small accessor methods unpythonic:

    cdef size_t nr_lists(self):
        return self._nr_lists

What's wrong with just calling the attribute nr_lists and accessing that directly?

This is what I wanted to do from the start. But it didnt' work. No idea why. I probably had some mistake, which I corrected when setting up those small accessors. Now I removed all small accessors and everything works great.

comment:105 Changed 2 years ago by git

  • Commit changed from 1e0f36f94fced98928c556b872a58888584e737e to 0edfd3f2a3b8c3b76f997ed20f46dd9048a5ade9

Branch pushed to git repo; I updated commit sha1. New commits:

0edfd3fremoved small accessors

comment:106 Changed 2 years ago by jdemeyer

Replace

from libc cimport stdint
ctypedef stdint.uint64_t uint64_t

by

from libc.stdint cimport uint64_t

comment:107 in reply to: ↑ 102 ; follow-ups: Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Also, this ListOfListOfPointers and ListOfFaces stuff seems to be reinventing the wheel. For example, since you're using C++ anyway, you could use std::vector<> or whatever. There is also sage.ext.memory_allocator.MemoryAllocator which seems to have some overlap with what you need.

I need 32-byte aligned memory for ListOfFaces. I actually don't need it exactly for this ticket, as I want to disable intrinsics for now, but eventually I want it.

sage.ext.memory_allocator.MemoryAllocator seems to be great for ListOfPointers. I couldn't get 32-byte aligned to work with any prebuild solution. This doesn't mean anything of course.

I had the impression that its somehow nice to allocate the memory in cython instead of some extern C file.

comment:108 Changed 2 years ago by git

  • Commit changed from 0edfd3f2a3b8c3b76f997ed20f46dd9048a5ade9 to f15883df872cb694d6f6aa33c59f256b671681e3

Branch pushed to git repo; I updated commit sha1. New commits:

71d9467replaced all PyMem calls
f15883dupdated import of uint64_t

comment:109 in reply to: ↑ 107 Changed 2 years ago by jdemeyer

Replying to gh-kliem:

I had the impression that its somehow nice to allocate the memory in cython instead of some extern C file.

Yes indeed. But you can use the standard C++ library in Cython: https://cython.readthedocs.io/en/latest/src/userguide/wrapping_CPlusPlus.html#standard-library

I'm not saying that this is a good or bad solution. Just that it's possible.

comment:110 in reply to: ↑ 107 ; follow-up: Changed 2 years ago by jdemeyer

Replying to gh-kliem:

sage.ext.memory_allocator.MemoryAllocator seems to be great for ListOfPointers. I couldn't get 32-byte aligned to work with any prebuild solution.

If MemoryAllocator works great except for the alignment, you could add alignment support to MemoryAllocator.

comment:112 follow-up: Changed 2 years ago by jdemeyer

Since you're using divisions, I strongly recommend to add

from __future__ import division

to make sure that your code works fine when using Python 3 divisions.

comment:113 in reply to: ↑ 110 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Replying to gh-kliem:

sage.ext.memory_allocator.MemoryAllocator seems to be great for ListOfPointers. I couldn't get 32-byte aligned to work with any prebuild solution.

If MemoryAllocator works great except for the alignment, you could add alignment support to MemoryAllocator.

I should do this. I already love MemoryAllocator. It's so easy. Then again, I might only appreciate it, because I though about what needs to be done.

comment:114 Changed 2 years ago by git

  • Commit changed from f15883df872cb694d6f6aa33c59f256b671681e3 to f534fae3c98b7e0ac5f6912924e9ddc0060b44f5

Branch pushed to git repo; I updated commit sha1. New commits:

e6f782eremoved ListOfPointers, added __future__ division
3a0337faltered aligned_malloc to work with MemoryAllocator instead)
f534faereplaced sig_malloc by MemoryAllocator.malloc in many instances

comment:115 Changed 2 years ago by git

  • Commit changed from f534fae3c98b7e0ac5f6912924e9ddc0060b44f5 to f3fe6988308c7b0ea333b837e482d46feedac185

Branch pushed to git repo; I updated commit sha1. New commits:

f3fe698removed ListOfListOfFaces

comment:116 Changed 2 years ago by git

  • Commit changed from f3fe6988308c7b0ea333b837e482d46feedac185 to 887db29d8c5f120fc210ec0db1fd73097c8871ed

Branch pushed to git repo; I updated commit sha1. New commits:

887db29actually removed the class ListOfListOfFaces, not just all instances,

comment:117 Changed 2 years ago by git

  • Commit changed from 887db29d8c5f120fc210ec0db1fd73097c8871ed to f10c90ab6e2bf65bd71dc55ec0d9a5520c0d2d1c

Branch pushed to git repo; I updated commit sha1. New commits:

087957dreplaced void * by uint64_t *
70559eemoved is_equal from helper.cc to base.pyx
6691d1eadded tests for face_lattice
bf2a8afmoved find_face to cython
98048e6moved sort from helper.cc to base.pyx
f10c90aPreparing: Filling Bit-Representations of Vertices and Facets in Cython, this makes it a lot easier

comment:118 in reply to: ↑ 98 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

I agree with Travis that error checking could be much improved: use error return values.

Also, instead of using sig_malloc and then checking for NULL, use check_malloc which automatically does that check. Even better, replace sig_malloc(a * sizeof(T)) by check_allocarray(a, sizeof(T)).

In char_from_incidence and get_vertices_from_incidence_matrix2 I have tried doing it correctly. char_from_incidence returns 1 on success and 0 means that something went wrong. get_vertices_from_incidence_matrix2 returns a Cython-Object and so it es okay not to do the except?

comment:119 Changed 2 years ago by jdemeyer

For anything returning a Python object, you cannot add an except value. That's only for C return types.

comment:120 Changed 2 years ago by git

  • Commit changed from f10c90ab6e2bf65bd71dc55ec0d9a5520c0d2d1c to 22026c6c2c1865381732e50171a8265bdf4f3abb

Branch pushed to git repo; I updated commit sha1. New commits:

4b37efbmoved construction of bit-representation to base.pyx
22026c6moved everything from vertex_to_bit_dictionary from helper.cc to base.pyx, now helper.cc only contains functions using intrinsics

comment:121 Changed 2 years ago by git

  • Commit changed from 22026c6c2c1865381732e50171a8265bdf4f3abb to c012d0c1e9618adc06f4f99c26f6599ead639676

Branch pushed to git repo; I updated commit sha1. New commits:

d9cc21aUpdated the face_length/length_of_face, it is now in terms of uint64_t, which should be more natural, also base.pyx knows almost nothing about chunksize now
828689bface_length and length_of_face are now face_length
c012d0cImproved errors, Keyboard interrupt should work fine now

comment:122 in reply to: ↑ 95 ; follow-up: Changed 2 years ago by gh-kliem

Replying to tscrim:

You should not have get_next_level wrapped in a sig_on/sig_off. That should do its own signal handling.

How am I going to do this? I changed it to do its own signal handling, but that made everything slow down. To be more precise: Calculating the f_vector of the 20-dimensional counterexample now takes 3m 39s instead of 2m 57s. Just adding

#include <csignal>

and

void inline signalHandler( int signum ) {
    // setting a variable, so I can catch the signal later
    interrupt = 1;
}

and

signal(SIGINT, signalHandler);

(I commented out the check for interrupt, to be certain its just this.) What am I doing wrong? What is the advantage of this approach over sig_on/sig_off thats worth this increase in time?

comment:123 in reply to: ↑ 112 ; follow-up: Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Since you're using divisions, I strongly recommend to add

from __future__ import division

to make sure that your code works fine when using Python 3 divisions.

Good thing I checked, what this actually means. I do want floor division. So this is not what I want, is it? Instead I should us // for "floor division"? I don't think there is a single instance, where I use "true division".

comment:124 in reply to: ↑ 122 ; follow-up: Changed 2 years ago by jdemeyer

Replying to gh-kliem:

Replying to tscrim:

You should not have get_next_level wrapped in a sig_on/sig_off. That should do its own signal handling.

I'm also confused with the comment by Travis. get_next_level is implemented in C, so I do think that using sig_on and sig_off (like it used to be) makes sense.

Last edited 2 years ago by jdemeyer (previous) (diff)

comment:125 in reply to: ↑ 123 Changed 2 years ago by jdemeyer

Replying to gh-kliem:

Instead I should us // for "floor division"?

If you need floor division, then you should use // indeed. You should still keep the from __future__ import division to catch mistakes (if you mistakenly use / instead of // it will behave the same on Python 2 and Python 3).

comment:126 Changed 2 years ago by git

  • Commit changed from c012d0c1e9618adc06f4f99c26f6599ead639676 to a1aa1c8f941e966d82a9efd522753d1334b71e90

Branch pushed to git repo; I updated commit sha1. New commits:

a1aa1c8Documentation + updated division to be floor division

comment:127 Changed 2 years ago by git

  • Commit changed from a1aa1c8f941e966d82a9efd522753d1334b71e90 to d31bd2bc702919d65fb1e6fa879e312f033a976d

Branch pushed to git repo; I updated commit sha1. New commits:

d31bd2badded base.pyx

comment:128 Changed 2 years ago by git

  • Commit changed from d31bd2bc702919d65fb1e6fa879e312f033a976d to e5346e5233406369d86fd4f61e5b04460e341f5d

Branch pushed to git repo; I updated commit sha1. New commits:

e5346e5saved base.pyx

comment:129 in reply to: ↑ 124 Changed 2 years ago by tscrim

Replying to jdemeyer:

Replying to gh-kliem:

Replying to tscrim:

You should not have get_next_level wrapped in a sig_on/sig_off. That should do its own signal handling.

I'm also confused with the comment by Travis. get_next_level is implemented in C, so I do think that using sig_on and sig_off (like it used to be) makes sense.

What Jeroen initially said was correct, I meant for it to have sig_on/sig_off inside the function, but I misread that it was implemented in C. So you can disregard that comment.

(Sorry for my delayed response, I have been traveling and busy.)

comment:130 Changed 2 years ago by git

  • Commit changed from e5346e5233406369d86fd4f61e5b04460e341f5d to 1d74cf81ad85fcbe0ac008c0c07d54173f3f3399

Branch pushed to git repo; I updated commit sha1. New commits:

1d74cf8Updated error messages

comment:131 Changed 2 years ago by git

  • Commit changed from 1d74cf81ad85fcbe0ac008c0c07d54173f3f3399 to 143cb5af73761dfc13a9a8fdc8c56dd9d5914b95

Branch pushed to git repo; I updated commit sha1. New commits:

7a75a6bUpdated a test
4bb83f0updated print functions to python3-compatible
b0d988fremoved macros from helper.cc and replaced them by methods
143cb5aadding `memcpy` and `memcmp`, no need to reinvent the wheel...

comment:132 Changed 2 years ago by git

  • Commit changed from 143cb5af73761dfc13a9a8fdc8c56dd9d5914b95 to 621f2c3a082b8417c26bf4e34821c28bc7f0b364

Branch pushed to git repo; I updated commit sha1. New commits:

1ff32ebcleaned up the intrinsics a bit more
621f2c3more documentation

comment:133 Changed 2 years ago by git

  • Commit changed from 621f2c3a082b8417c26bf4e34821c28bc7f0b364 to b9ffa15788e3429cb2e4290c46ec5e247fe47429

Branch pushed to git repo; I updated commit sha1. New commits:

b9ffa15checking for NULL, when adding a face

comment:134 Changed 2 years ago by git

  • Commit changed from b9ffa15788e3429cb2e4290c46ec5e247fe47429 to ce1789e8eae99847f3665d73cd9ede600e46998d

Branch pushed to git repo; I updated commit sha1. New commits:

ce1789ecoding conventions

comment:135 Changed 2 years ago by git

  • Commit changed from ce1789e8eae99847f3665d73cd9ede600e46998d to c16fccc35175e67b05261a02b913b3ae29baade2

Branch pushed to git repo; I updated commit sha1. New commits:

c16fcccone / too much

comment:136 follow-up: Changed 2 years ago by jdemeyer

Two general comments:

  1. You have a huge number of commits. At some point, it would be good to squash everything into one commit.
  1. Don't forget to set the ticket back to needs_review if you want it reviewed.

comment:137 Changed 2 years ago by git

  • Commit changed from c16fccc35175e67b05261a02b913b3ae29baade2 to deb5977d117ec4c4be1cc5bfac9e6fda85633387

Branch pushed to git repo; I updated commit sha1. New commits:

deb5977it should be mostly clean now

comment:138 Changed 2 years ago by gh-kliem

  • Branch changed from u/gh-kliem/improve_f_vector_etc__for_polytopes to public/26887
  • Commit changed from deb5977d117ec4c4be1cc5bfac9e6fda85633387 to b73c335e50ab93c8ec5ba2a96c4198b9d589f478

New commits:

b73c335added a class class CombinatorialPolyhedron

comment:139 in reply to: ↑ 136 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Two general comments:

  1. You have a huge number of commits. At some point, it would be good to squash everything into one commit.
  1. Don't forget to set the ticket back to needs_review if you want it reviewed.

Wasn't sure how to exactly squash pushed commits, but I guess restarting a clean branch does the job.

comment:140 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:141 Changed 2 years ago by git

  • Commit changed from b73c335e50ab93c8ec5ba2a96c4198b9d589f478 to f1ad61b753d526049013ec2d61a762e7576ae15e

Branch pushed to git repo; I updated commit sha1. New commits:

f1ad61bcorrected blocks

comment:142 Changed 2 years ago by gh-kliem

How come that patchbots use completely different versions of the files then claimed?

I keep getting messages containing errors with chunktype in helper.cc. I removed this a while ago and the current branch shouldn't even know that chunktype ever existed.

BuildFailed? 8.7.beta4 Ubuntu/18.04/x86_64/3.13.0-123-generic/44e979ad077a 2019-02-18 20:09:03 log shortlog

comment:143 Changed 2 years ago by jdemeyer

The patchbot page contains all builds for a particular ticket, even old ones. I agree that it's not obvious to see whether a patchbot run is from the current commit or an earlier one.

comment:144 Changed 2 years ago by jdemeyer

  • Dependencies set to #27292

This should eventually use the functions added by #27292.

comment:145 follow-ups: Changed 2 years ago by jdemeyer

  • Status changed from needs_review to needs_work

I have lots of small comments while reading this code:

  1. It would makes things easier to understand if you really removed the vectorization stuff instead of just commenting it out. That way, we can completely focus the review on the generic code (without needing the worry about the commented-out parts). More generally, remove commented-out code like # cdef tuple lists_facet_repr #might need this for flag-vector
  1. It's really hard to understand what all the code does: I'm missing some kind of "big picture" documentation to explain what this is all about. For example, when I see
    cdef class FaceIterator:
        cdef uint64_t *face
        cdef int current_dimension, dimension, record_dimension, lowest_dimension
        cdef MemoryAllocator _mem
        cdef uint64_t ***newfaces2
        cdef tuple newfaces_lists
        cdef uint64_t ***newfaces
        cdef uint64_t **forbidden
        cdef size_t *nr_faces
        cdef size_t *nr_forbidden
        cdef int *first_time
        cdef size_t yet_to_yield, face_length, nr_facets, nr_vertices
        cdef size_t *output1
        cdef size_t *output2
        cdef int nr_lines
    

I don't want to review this anymore. You really need to add a lot more comments.

  1. The Cython doctests are hard to read: all the output just comes at the end and it's difficult to see which code produced it. You could instead define a bunch of test functions (either in the doctest or in the Cython sources) and then call those from Python.
  1. I sometimes wonder if it wouldn't be easier to abstract some things in C++ or Python classes, for example using something like std::vector<uint64_t> or array.array instead of uint64_t*.
  1. Do you really need vertex_to_bit_dictionary? It's probably more efficient to replace vertex_to_bit_dictionary[i] by an inline function
    cdef inline uint64_t vertex_to_bit_dictionary(int i):
        return (<uint64_t>1) << (64 - i - 1)
    
  1. In char_from_tuple (and other similar functions), please use except -1 for exceptions and return 0 in the non-exceptional case. Then you don't even need to write return 0 since that's the default.
  1. Typos lenght -> length
  1. In various places, you use int as indices while most other places use size_t. Is there a reason for that? Note that Python typically uses Py_ssize_t for loops like that.
  1. return int(bitcount) is converting a C size_t to a Python int to a C int. Just return bitcount should be sufficient.
  1. There is no point at all to put sig_check() right after sig_off() or right before sig_on().
  1. Is there a good reason to implement face_iter and faces separately? Isn't it sufficient to have the iterator only?

comment:146 in reply to: ↑ 145 ; follow-up: Changed 2 years ago by gh-kliem

Thanks for the comments.

Replying to jdemeyer:

I have lots of small comments while reading this code:

  1. It would makes things easier to understand if you really removed the vectorization stuff instead of just commenting it out. That way, we can completely focus the review on the generic code (without needing the worry about the commented-out parts). More generally, remove commented-out code like # cdef tuple lists_facet_repr #might need this for flag-vector

Ok, I will do that. In #27103 I already added that code as a comment. I just did some timings comparing the current sage, polymake and the new code with intrinsics and without: Yes the intrinsics are nice, as they give a speedup of a factor of 2-3 for the iterator. But its nothing in comparison to the gain of that ticket without intrinsics in comparison to standing algorithms.

  1. It's really hard to understand what all the code does: I'm missing some kind of "big picture" documentation to explain what this is all about. For example, when I see
    cdef class FaceIterator:
        cdef uint64_t *face
        cdef int current_dimension, dimension, record_dimension, lowest_dimension
        cdef MemoryAllocator _mem
        cdef uint64_t ***newfaces2
        cdef tuple newfaces_lists
        cdef uint64_t ***newfaces
        cdef uint64_t **forbidden
        cdef size_t *nr_faces
        cdef size_t *nr_forbidden
        cdef int *first_time
        cdef size_t yet_to_yield, face_length, nr_facets, nr_vertices
        cdef size_t *output1
        cdef size_t *output2
        cdef int nr_lines
    

I don't want to review this anymore. You really need to add a lot more comments.

In CombinatorialPolyhedron.f_vector there is a small description of the basic algorithm. Maybe it is of help. I will add comments to all those variable declarations.

  1. The Cython doctests are hard to read: all the output just comes at the end and it's difficult to see which code produced it. You could instead define a bunch of test functions (either in the doctest or in the Cython sources) and then call those from Python.

I just saw, how you did that in #27292. Makes sense.

  1. I sometimes wonder if it wouldn't be easier to abstract some things in C++ or Python classes, for example using something like std::vector<uint64_t> or array.array instead of uint64_t*.

Without intrinsics this seems to be a good approach. However, I have now idea how to force array.array or vector to keep alignment. Also I never change the size of the uint64_t*.

  1. Do you really need vertex_to_bit_dictionary? It's probably more efficient to replace vertex_to_bit_dictionary[i] by an inline function
    cdef inline uint64_t vertex_to_bit_dictionary(int i):
        return (<uint64_t>1) << (64 - i - 1)
    
  1. In char_from_tuple (and other similar functions), please use except -1 for exceptions and return 0 in the non-exceptional case. Then you don't even need to write return 0 since that's the default.
  1. Typos lenght -> length
  1. In various places, you use int as indices while most other places use size_t. Is there a reason for that? Note that Python typically uses Py_ssize_t for loops like that.

I got a warning about comparison of unsigned and signed integer. This is how I "solved" it. Cython seems to translate len() to a signed integer, then I get warnings. So Py_ssize_t is a good type for an index in there? Or just leave it up to the compiler?

  1. return int(bitcount) is converting a C size_t to a Python int to a C int. Just return bitcount should be sufficient.
  1. There is no point at all to put sig_check() right after sig_off() or right before sig_on().

Didn't know if sig_on() whould catch an already existing Interrupt.

  1. Is there a good reason to implement face_iter and faces separately? Isn't it sufficient to have the iterator only?

I don't care. I just figured, that people want a faces() anyway. To me, there is no need to that function. Partly, its there because of historic reasons.

comment:147 in reply to: ↑ 146 ; follow-up: Changed 2 years ago by jdemeyer

Replying to gh-kliem:

So Py_ssize_t is a good type for an index in there?

Py_ssize_t is the type of len(something) in Python. So, if you're doing something like for i in range(len(something)), then indeed use cdef Py_ssize_t i.

I don't care. I just figured, that people want a faces() anyway.

What if you're looking for one face with a specific property, or counting each face with a given property? Then you don't need to generate a list of all faces.

In general, Python seems to move away from returning lists of things to returning views/iterators. For example, range() is an iterator in Python 3 but a list in Python 2.

comment:148 in reply to: ↑ 147 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Replying to gh-kliem:

So Py_ssize_t is a good type for an index in there?

Py_ssize_t is the type of len(something) in Python. So, if you're doing something like for i in range(len(something)), then indeed use cdef Py_ssize_t i.

I don't care. I just figured, that people want a faces() anyway.

What if you're looking for one face with a specific property, or counting each face with a given property? Then you don't need to generate a list of all faces.

I am aware of advantages of an iterator.

This raises again the question of wether my construction makes sense and I am almost certain, there is a better way of doing so:

So I have a FaceIterator that can swiftly go to next face (and return its dimension on default). Before jumping to the next face, we can also grab the vertex-representation, facet-representation. In the future it might be nice to add more functions, but so much for now.

At the moment I have a complicated method CombinatorialPolyhedron.face_iter() that yields information of each face depending on a bunch of arguments. But I am almost certain, that this is not a good way of doing it. Probably I should return FaceIterator, which is an iterator. What's a good way of implementing an iterator, that can return various outputs? I'm thinking of something like

sage: cython('''                            
....: from sage.rings.integer import Integer
....: cdef class FaceIterator:
....:     cdef size_t nr_faces
....:     cdef size_t i
....:     def __init__(self, number):
....:         self.nr_faces = number
....:         self.i = 0
....:     
....:     def __iter__(self):
....:         return self
....:     
....:     def __next__(self):
....:         current = Integer(self.i)
....:         self.i += 1
....:         if self.i > self.nr_faces:
....:             raise StopIteration
....:         else:
....:             return Integer(current)
....:             
....:     next = __next__
....:     
....:     def give_facet_repr(self):
....:         # some actual calculation happening here
....:         return 'this is the facet repr of the current face'
....:         
....:     def give_vertex_repr(self):
....:         # some calculation here
....:         return 'this is the vertex_repr'
....:         
....:     def skip_a_face(self):
....:         # what I'm thinking about is the option
....:         # of not visiting any faces of the current face 
....:         self.i += 1
....: ''')
sage: a = FaceIterator(20)
sage: next(a)
0
sage: next(a)
1
sage: a.skip_a_faces()
sage: a.skip_a_faces()
sage: next(a)
4
sage: a.give_facet_repr()
'this is the facet repr of the current face'
sage: a.give_vertex_repr()
'this is the vertex_repr'

I guess I know how to do this, but I don't know, if this any good.

This way the user would actually be able to use the face iterator + I don't have to think of all possible outputs when creating CombinatorialPolyhedron.face_iter(). One can easily add more outputs like constructing the facets of the current face, or return a CombinatorialPolyhedron which is the current face etc.

At the moment, such extensions would be hard to do.

One could also yield a something like CombinatorialFace, but I'm a bit worried about the overhead. Also things like "do not revisit subfaces" (i.e. when the face is simplicial and there is really no point in doing so) or setting a maximal dimension etc. are not possible.

In general, Python seems to move away from returning lists of things to returning views/iterators. For example, range() is an iterator in Python 3 but a list in Python 2.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:149 Changed 2 years ago by gh-kliem

Another thing I could do to make life easier: Split this ticket in a number of tickets as good as possible.

So for this ticket there could be "only" the class CombinatorialPolyhedron with a FaceIterator that calculates the f_vector.

Follow up tickets would be

  • edges and ridges
  • hasse_diagram/face_lattice
  • maybe even all those accesors in FaceIterator

How about it? This would remove at least 1000 lines in the current code for later.

comment:150 Changed 2 years ago by git

  • Commit changed from f1ad61b753d526049013ec2d61a762e7576ae15e to 71c6d7a400c3c7db3f1c27be559a5d50619fe56d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

596c345added realloc, reallocarray, aligned_malloc
61ad091Clean up and optimize
34f1beaadded a class class CombinatorialPolyhedron
71c6d7acorrected blocks

comment:151 Changed 2 years ago by tscrim

Can you still have meaningful tests here with it being split? Although I think we have mostly gone through the code currently here already. So I am not sure there will be too much merit in splitting it, but maybe someone else has a different idea.

comment:152 Changed 2 years ago by gh-kliem

Ok, I leave the stuff in there.

I will however return FaceIterator with the method face_iter(). This should make it much easier.

Also the dual/polar decision will be on call of face_iter.

comment:153 Changed 2 years ago by git

  • Commit changed from 71c6d7a400c3c7db3f1c27be559a5d50619fe56d to 6052b6138d488608c5ba11ea05525648aea1b4ee

Branch pushed to git repo; I updated commit sha1. New commits:

6052b61FaceIterator is an actual iterator now

comment:154 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

Mainly I just changed FaceIterator to be an iterator. This also helped my remove most cython examples.

FaceIterator and ListOfAllFaces should take care of the special cases themselves now.

CombinatorialPolyhedron almost doesn't know anything about dual anymore. This is a way to initialize FaceIterator.

comment:155 Changed 2 years ago by git

  • Commit changed from 6052b6138d488608c5ba11ea05525648aea1b4ee to c30e60d74f700fc389e2e2b36a2ce005ca44f02d

Branch pushed to git repo; I updated commit sha1. New commits:

c30e60dfixed allocation of array

comment:156 Changed 2 years ago by git

  • Commit changed from c30e60d74f700fc389e2e2b36a2ce005ca44f02d to e8309e4c706335d981a70ed67bdaa7ea96a3ca13

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e8309e4fixed allocation of array

comment:157 Changed 2 years ago by chapoton

Please do not use

++        sage: it.next()

but next(it) for compatibility with python3.

comment:158 follow-up: Changed 2 years ago by jdemeyer

Do you recommend to also remove next = __next__ then?

comment:159 Changed 2 years ago by git

  • Commit changed from e8309e4c706335d981a70ed67bdaa7ea96a3ca13 to 6a55fa5dadad4d97182d55334a985bdab6e34f37

Branch pushed to git repo; I updated commit sha1. New commits:

6a55fa5it.next() -> next(it), also fixed face_lattice_facet_repr for trivial cases

comment:160 in reply to: ↑ 158 Changed 2 years ago by gh-kliem

Replying to jdemeyer:

Do you recommend to also remove next = __next__ then?

I guess Cython takes care of that automatically. I read somewhere, that one should do that and indeed this seems to be true for defining a Python iterator class.

comment:161 follow-up: Changed 2 years ago by tscrim

I am going through the doc right now.

A general issue I noticed:

 INPUT:
 
-- `foo` -- lorem ipsum
+- ``foo`` -- lorem ipsum

so it is formatted as code and not latex. There might be other cases in the docstrings themselves that should be code formatted. These bullet points for INPUT: do not, by general Sage convention, end in a period/full-stop.

Another general issue, three .'s are needed here:

         Traceback (most recent call last):
-        ..
+        ...
         ValueError: entries of `tup` are not distinct

Typo: `ouput`

Instead of doing the next(it) a bunch of times, how about doing

sage: [next(it) for _ in range(14)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
     The algorithm to visit all proper faces exactly once is roughly
-    equivalent to:
+    equivalent to::
 
-    faces = [set(facet) for facet in self.facets()]
-    ComputeNextStep(facets, [])
+        faces = [set(facet) for facet in self.facets()]
+        ComputeNextStep(facets, [])

(This will not be executed as code as there is no leading sage:.) Similar comment for the ALGORITHM: block in FaceIterator's class-level docstring.

You can use bint for dual in FaceIterator.__init__.

I would drop the An from the repr of FaceIterator (this is another general convention we mostly stick to).

-raise StopIteration()
+raise StopIteration
-Returns the length of the vertex_repr.
+Return the length of the :meth:`vertex_repr`.

and similar for facet_repr.

You should use Return instead of Returns (I think the former is called the definitive form of the verb). (I think this is a PEP8 thing; at the very least it is a Sage convention.)

The tests for vertex_repr_length and facet_repr_length I would say are not so meaningful. I think better tests would be to check it against it.length_vertex_repr() == len(it.vertex_repr()).

You might find the .. WARNING:: environment useful for the next_face() docstring.

It is good to add a TestSuite(foo).run() call in the __init__ method doctests.

This is malformatted:

       * ``nr_lines`` -- for bounded Polyhedra, this should be the
-      default: ``None``. For unbounded Polyhedra, this needs to be set
-      to the correct nr of lines, i.e. the the maximum nr of lines with
-      linearly independent directions in the Polyehdron.
+        default: ``None``. For unbounded Polyhedra, this needs to be set
+        to the correct nr of lines, i.e. the the maximum nr of lines with
+        linearly independent directions in the Polyehdron.
       * ``unbounded`` -- for bounded Polyhedra, this should be the
-      default ``None``. For unbounded Polyhedra, this needs to be set
-      to the correct nr of lines, i.e. the the maximum nr of lines with
-     linearly independent directions in the Polyehdron.
+        default ``None``. For unbounded Polyhedra, this needs to be set
+        to the correct nr of lines, i.e. the the maximum nr of lines with
+        linearly independent directions in the Polyehdron.

It is good to spell things out in the doc IMO:

-Specifying the nr of lines is important::
+Specifying the number of lines is important::

There's a few places you use f_vector that is plain formatted. I think you either should use `f`-vector/f-vector or ``f_vector``.

-If `names` is set to True, then names of the vertices are used.
+If ``names`` is ``True``, then names of the vertices are used.

In general, do not feel the need to stick to 80 chars/line in code for things like

                self._f_vector = \
                    tuple(Integer(f_vector[dim+1-i]) for i in range(dim+2))

as I think it makes the code harder to read.

I might have more comments later, but that is what I got for now.

Last edited 2 years ago by tscrim (previous) (diff)

comment:162 follow-up: Changed 2 years ago by jhpalmieri

According to the patchbots, the build is failing on a few different platforms.

comment:163 in reply to: ↑ 162 ; follow-up: Changed 2 years ago by gh-kliem

Replying to jhpalmieri:

According to the patchbots, the build is failing on a few different platforms.

The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring lenfaces as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere #include "Python.h." gives trouble on OS X with C++17. Now its only a warning and not an error though.

Both Ubuntu patchbots (44e979ad077a and quasar) use an old version of the files. I don't know why. chunktype has long been removed from helper.cc.

comment:164 Changed 2 years ago by git

  • Commit changed from 6a55fa5dadad4d97182d55334a985bdab6e34f37 to 9f421825ae6eaa4bc800b978ba7e9d529434a0fc

Branch pushed to git repo; I updated commit sha1. New commits:

9f42182improved documentation mostly

comment:165 in reply to: ↑ 161 Changed 2 years ago by gh-kliem

Thanks, went through the entire document and tried to fix all of those issues.

Replaced int by bint wherever I use only True and False anyway.

Added __reduce__ with and NotImplementedError to the ListOfFaces, FaceIterator and ListOfAllFaces. One could try to implement that, but I don't see an advantage of that.

Replying to tscrim:

I am going through the doc right now.

comment:166 in reply to: ↑ 163 ; follow-up: Changed 2 years ago by jhpalmieri

Replying to gh-kliem:

Replying to jhpalmieri:

According to the patchbots, the build is failing on a few different platforms.

The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring lenfaces as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere #include "Python.h." gives trouble on OS X with C++17. Now its only a warning and not an error though.

I'm confused: if it's fixed, why does the build fail?

Executing 21 commands (using 1 thread)
[ 1/21] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -Isage/geometry/polyhedron/combinatorial_polyhedron -I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/site-packages/cysignals -I/Users/jpalmier/Desktop/Sage/git/sage/local/include -I/Users/jpalmier/Desktop/Sage/git/sage/src/sage/ext -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 -I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/site-packages/numpy/core/include -Ibuild/cythonized -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 -c build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp -o build/temp.macosx-10.9-x86_64-2.7/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -std=c++11
In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:47:
In file included from ../local/include/python2.7/Python.h:88:
../local/include/python2.7/unicodeobject.h:534:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj,     /* Object */
    ^~~~~~~~~
../local/include/python2.7/unicodeobject.h:553:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj      /* Object */
    ^~~~~~~~~
../local/include/python2.7/unicodeobject.h:575:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register const wchar_t *w,  /* wchar_t buffer */
    ^~~~~~~~~
../local/include/python2.7/unicodeobject.h:593:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register wchar_t *w,        /* wchar_t buffer */
    ^~~~~~~~~
In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:47:
In file included from ../local/include/python2.7/Python.h:97:
../local/include/python2.7/stringobject.h:173:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register PyObject *obj,     /* string or Unicode object */
    ^~~~~~~~~
../local/include/python2.7/stringobject.h:174:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register char **s,          /* pointer to buffer variable */
    ^~~~~~~~~
../local/include/python2.7/stringobject.h:175:5: warning: 'register' storage class specifier is deprecated and incompatible with C++17 [-Wdeprecated-register]
    register Py_ssize_t *len    /* pointer to length variable or NULL
    ^~~~~~~~~
In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:3621:
build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/helper.cc:207:22: error: variable-sized object may not be initialized
    int addfacearray[constlenfaces - 1] = { };
                     ^~~~~~~~~~~~~~~~~
7 warnings and 1 error generated.
[ 2/21] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -I./sage/cpython -I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/site-packages/cypari2 -I./sage/libs/ntl -I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/site-packages/cysignals -I/Users/jpalmier/Desktop/Sage/git/sage/local/include -I/Users/jpalmier/Desktop/Sage/git/sage/src/sage/ext -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 -I/Users/jpalmier/Desktop/Sage/git/sage/local/lib/python2.7/site-packages/numpy/core/include -Ibuild/cythonized -I/Users/jpalmier/Desktop/Sage/git/sage/local/include/python2.7 -c build/cythonized/sage/rings/complex_arb.c -o build/temp.macosx-10.9-x86_64-2.7/build/cythonized/sage/rings/complex_arb.o -fno-strict-aliasing -DCYTHON_CLINE_IN_TRACEBACK=1 -std=c99
error: command 'gcc' failed with exit status 1
make[4]: *** [sage] Error 1

comment:167 in reply to: ↑ 166 ; follow-up: Changed 2 years ago by gh-kliem

Replying to jhpalmieri:

Replying to gh-kliem:

Replying to jhpalmieri:

According to the patchbots, the build is failing on a few different platforms.

The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring lenfaces as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere #include "Python.h." gives trouble on OS X with C++17. Now its only a warning and not an error though.

I'm confused: if it's fixed, why does the build fail?

In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:3621:
build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/helper.cc:207:22: error: variable-sized object may not be initialized
    int addfacearray[constlenfaces - 1] = { };

This line is not part of helper.cc anymore. I have no idea, why the patchbot uses an old version.

comment:168 follow-up: Changed 2 years ago by gh-kliem

Running doctests with ID 2019-02-27-15-17-15-308038d2.
Git branch: patchbot/ticket_merged
Using --optional=ccache,dochtml,memlimit,mpir,python2,sage
Doctesting entire Sage library.
Sorting sources by runtime so that slower doctests are run first....
Doctesting 3799 files using 2 threads.
sage -t --long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pxd
    [0 tests, 0.00 s]
sage -t --long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx
**********************************************************************
File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 736, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension
Failed example:
    calculate_dimension(facets)
Exception raised:
    Traceback (most recent call last):
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1095, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension[4]>", line 1, in <module>
        calculate_dimension(facets)
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 723, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6467)
        cpdef int calculate_dimension(ListOfFaces faces) except -2:
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 783, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6419)
        return calculate_dimension_loop(faces.data, nr_faces, faces.face_length)
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 838, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6675)
        return calculate_dimension_loop(newfaces2data, new_nr_faces, face_length) + 1
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 830, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6648)
        sig_on()
    SignalError: Segmentation fault
**********************************************************************
File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 738, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension
Failed example:
    calculate_dimension(vertices)
Exception raised:
    Traceback (most recent call last):
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1095, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension[5]>", line 1, in <module>
        calculate_dimension(vertices)
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 723, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6467)
        cpdef int calculate_dimension(ListOfFaces faces) except -2:
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 783, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6419)
        return calculate_dimension_loop(faces.data, nr_faces, faces.face_length)
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 838, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6675)
        return calculate_dimension_loop(newfaces2data, new_nr_faces, face_length) + 1
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 830, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6648)
        sig_on()
    SignalError: Segmentation fault
**********************************************************************
File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 766, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension
Failed example:
    for _ in range(10):
        points = tuple(tuple(randint(-1000,1000) for _ in range(10))
                       for _ in range(randint(3,15)))
        P = Polyhedron(vertices=points)
        facets = get_facets_from_incidence_matrix(P.incidence_matrix())
        vertices = get_vertices_from_incidence_matrix(P.incidence_matrix())
        d1 = P.dimension()
        d2 = calculate_dimension(facets)
        d3 = calculate_dimension(vertices)
        if not d1 == d2 == d3:
            print('calculation_dimension() seems to be incorrect')
Exception raised:
    Traceback (most recent call last):
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 671, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1095, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension[8]>", line 8, in <module>
        d2 = calculate_dimension(facets)
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 723, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6467)
        cpdef int calculate_dimension(ListOfFaces faces) except -2:
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 783, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6419)
        return calculate_dimension_loop(faces.data, nr_faces, faces.face_length)
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 838, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6675)
        return calculate_dimension_loop(newfaces2data, new_nr_faces, face_length) + 1
      File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 830, in sage.geometry.polyhedron.combinatorial_polyhedron.base.calculate_dimension_loop (build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:6648)
        sig_on()
    SignalError: Segmentation fault
    Killed due to segmentation fault
**********************************************************************

This has me wondering, what went wrong.

Probably, I should have included

#include <cstdlib>
using namespace std;

in helper.cc in order for calloc to work the way I use it. Also I should probably return -1 if calloc returns NULL and add except -1 to get_next_level. Woudn't give a nice error message yet, but at least prevent thing from crashing if calloc returns NULL.

Alternatively I could still try to allocate the memory with int ommitfacearray[lenfaces-1] and pass lenfaces to get_next_level as const size_t.

A third way would be to allocate the memory with int *ommitfacearray = new int[lenfaces-1] and still have lenfaces be of type const size_t.

A fourth way, would be to allocate the memory in Cython and pass it to the function. Then one could also allocate the array only once for an entire FaceIterator.

Is my guess for the Segmentation fault even likely?

comment:169 Changed 2 years ago by git

  • Commit changed from 9f421825ae6eaa4bc800b978ba7e9d529434a0fc to 687d0032794306c563430f03391fac3ba7bf9419

Branch pushed to git repo; I updated commit sha1. New commits:

687d003replaced calloc by new[]

comment:170 in reply to: ↑ 168 ; follow-up: Changed 2 years ago by gh-kliem

new[] worked fine before, so I tried that. I hope this solves the issue.

I did some googling and got the impression, that calloc etc. is not really the C++ way of doing it.

Btw, helper.cc doesn't use anything C++-specific anymore, so if necessary I could switch to C again. At the moment I don't think it matters.

Replying to gh-kliem:

comment:171 in reply to: ↑ 170 Changed 2 years ago by tscrim

Replying to gh-kliem:

new[] worked fine before, so I tried that. I hope this solves the issue.

I did some googling and got the impression, that calloc etc. is not really the C++ way of doing it.

Yes, that is my understanding: you should use new[] and delete[] in C++.

Btw, helper.cc doesn't use anything C++-specific anymore, so if necessary I could switch to C again. At the moment I don't think it matters.

My understanding is that it does make some minor differences (with compile time, optimization, standards, etc.), but usually not anything noticeable at this scale. Although if it is all pure C except for the malloc vs. new[], I might consider going back to pure C. Yet I have not been in the C/C++ game for a little while and would never classify myself as an expert, so someone who is more knowledgeable in that realm, please correct me if I am wrong.

comment:172 Changed 2 years ago by gh-kliem

One of my colleges just gave me some input on readability.

I will go through the code again and improve readability.

comment:173 Changed 2 years ago by gh-kliem

  • Status changed from needs_review to needs_work

As mentioned above, I will try to make the comments more readable. (Writing complete English sentences. More intuitive positions of comments. Etc.)

I will probably also change a few names as facet_repr() -> set_facet_repr() and then call the corresponding attribute maybe just facet_repr. Maybe add _current_face to both.

I have no intentions of changing any actual code, other than renaming (if I think a new name is more descriptive). Maybe I should create a mapping table of renamings?

comment:174 in reply to: ↑ 167 Changed 2 years ago by gh-kliem

Replying to gh-kliem:

Replying to jhpalmieri:

Replying to gh-kliem:

Replying to jhpalmieri:

According to the patchbots, the build is failing on a few different platforms.

The fail on Darwin is due to an issue, I fixed already (comment 156). Declaring lenfaces as constant at function call, might have solved it as well. Also this build issues number of warnings due to python2.7/Python.h being incompatible with C++17. We had those problems before, where a mere #include "Python.h." gives trouble on OS X with C++17. Now its only a warning and not an error though.

I'm confused: if it's fixed, why does the build fail?

In file included from build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.cpp:3621:
build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/helper.cc:207:22: error: variable-sized object may not be initialized
    int addfacearray[constlenfaces - 1] = { };

This line is not part of helper.cc anymore. I have no idea, why the patchbot uses an old version.

It looks like I stumbled over the same problem at my machine. I changed function names in helper.cc and sage build would completely ignore those changes. Meaning I couldn't use the functions by their new names, but I could use them by their old names.

Somewhere helper.cc was cached and it was constantly taken from there.

Deleting the cashed files in

src/build/cythonized/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron and sage/src/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron

seems to be the solution. The patchbots don't do that I assume.

What's going on?

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:175 Changed 2 years ago by jhpalmieri

I saw this, too, and after deleting those files, this built on my OS X box. I don't know if they are supposed to be cleaned up automatically somehow or not.

comment:176 in reply to: ↑ 145 Changed 2 years ago by gh-kliem

There seem to be scenarios where KeyboardInterrupt cause sage to crash. It will not use CPU anymore, so somehow it seems to work. But it will look exactly like a failed interrupt, so nothing works anymore in that session.

It seems to happen between 0--10 percent of the time, when trying to interrupt:

sage: from itertools import combinations
sage: N = combinations(range(200),199)
sage: C = CombinatorialPolyhedron(N)
sage: C.dimension()
199
sage: C.f_vector()

https://patchbot.sagemath.org/log/26887/debian/9.8/x86_64/4.9.0-8-amd64/zancara/2019-03-03%2002:41:50?short

I have tried to figure it out, but I have no idea, what could have happened.

Last edited 2 years ago by gh-kliem (previous) (diff)

comment:177 Changed 2 years ago by git

  • Commit changed from 687d0032794306c563430f03391fac3ba7bf9419 to f8a201e41ffc28d9903499988aed2f86db2dee17

Branch pushed to git repo; I updated commit sha1. New commits:

f8a201eImproved comments all through base.pyx

comment:178 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

I hope this is easier to read now. I actually went through all the files.

At the moment the tests with alarm are unstable.

I don't know why. Can anyone figure it out. Or should I just remove them? Especially CombinatorialPolyhedron.f_vector() seems to be pretty easy to trace.

If anyone cares, here is a list of some of the more important renamings I did:

CountFaceBits                           ->  count_atoms
facet_repr_from_bitrep                  ->  bit_repr_to_coatom_repr
char_from_tuple                         ->  vertex_list_to_bit_repr
char_from_incidence                     ->  incidences_to_bit_repr
forbidden                               ->  visited_all
nr_forbidden                            ->  nr_visited_all
get_facets_from_incidence_matrix        ->  incidence_matrix_to_bit_repr_of_facets
get_vertices_from_incidence_matrix      ->  incidence_matrix_to_bit_repr_of_vertices
get_facets_bitrep_from_facets_tuple     ->  facets_tuple_to_bit_repr_of_facets
get_vertices_bitrep_from_facets_tuple   ->  facets_tuple_to_bit_repr_of_vertices
vertex_repr_from_bitrep                 ->  bit_repr_to_vertex_list
FaceIterator.record_dimension           ->  FaceIterator.request_dimension
FaceIterator.yet_to_yield               ->  FaceIterator.yet_to_visit
FaceIterator.atom_repr_face             ->  FaceIterator.atom_repr
FaceIterator.coatom_repr_face           ->  FaceIterator.coatom_repr
FaceIterator.atom_repr                  ->  FaceIterator.set_atom_repr
FaceIterator.coatom_repr                ->  FaceIterator.set_coatom_repr
ListOfAllFaces.atom_repr_face           ->  ListOfAllFaces.atom_repr
ListOfAllFaces.coatom_repr_face         ->  ListOfAllFaces.coatom_repr
ListOfAllFaces.atom_repr                ->  ListOfAllFaces.set_atom_repr
ListOfAllFaces.coatom_repr              ->  ListOfAllFaces.set_coatom_repr
ListOfAllFaces.incidence_is_initialized ->  ListOfAllFaces.is_incidence_initialized

comment:179 Changed 2 years ago by git

  • Commit changed from f8a201e41ffc28d9903499988aed2f86db2dee17 to df43a2d5391a8c78db78e66a6ab3556a1e1b8689

Branch pushed to git repo; I updated commit sha1. New commits:

df43a2dimproved pseudo-code Algorithm in ``FaceIterator``

comment:180 Changed 2 years ago by git

  • Commit changed from df43a2d5391a8c78db78e66a6ab3556a1e1b8689 to b73e53c9b172eb0b53b0895f49f79b5c6eaac65e

Branch pushed to git repo; I updated commit sha1. New commits:

b73e53cCorrected a mathematical error in explonation.

comment:181 follow-up: Changed 2 years ago by gh-kliem

Is there anything else I should do at this point?

For some reason, I accidentally added my notes and old files. I removed them in git again. But I don't think its worth a push for now.

I see two open problems at the moment:

  1. Unstable interrupts in the tests. Remove the tests or fix it. Maybe this issue of an interrupt not completing might not even be caused by me.
  2. The C++ files are not recompiled when they change (at least not always). I can add a syntax error and the compiler will not notice.

I was thinking about changing the way, I get all the incidences again. This wouldn't be a mayor change, but still a change. Right now, I'm intersecting every face with every facet to get all incidences. It would suffice to intersect every face with all "siblings" of some fixed parent. Then again, the examples I could compute with 30GB of RAM all took less than 10 minutes. And then it seems to me, it is almost impossible to obtain any useful information from a Hasse diagram of that size. So I'm not sure, if there is even use to optimization at this end. Unless, somebody thinks this should be optimized if possible, I'll leave it as it is. It's at least almost as fast in creating the face lattice as polymake the way it is.

comment:182 in reply to: ↑ 181 Changed 2 years ago by jdemeyer

Replying to gh-kliem:

The C++ files are not recompiled when they change (at least not always). I can add a syntax error and the compiler will not notice.

This is a known bug: #27389

comment:183 Changed 2 years ago by git

  • Commit changed from b73e53c9b172eb0b53b0895f49f79b5c6eaac65e to 12038d392fc1dba2a34fe27ce0732eb2481104d9

Branch pushed to git repo; I updated commit sha1. New commits:

12038d3removed notes and old files again

Changed 2 years ago by gh-kliem

Brief description with pictures, how the algorithm works

Changed 2 years ago by gh-kliem

Comparison of runtime in comparison to polymake, given only the vertex-facet incidence matrix

comment:184 Changed 2 years ago by gh-kliem

I gave a talk today in the seminar of Michael Joswig's work group.

I added the explanation of the algorithm in pictures. Maybe this is of help. I think it is much better to comprehend than my pseudo code.

I also added the runtime comparison to polymake from the vertex-facet incidences matrix.

I would be thankful for a review and/or comments on what to improve.

Btw, the tests involving alarm are still unstable and sometimes fail. Maybe the interrupt is just not stable. But, maybe I also did some mistake. I don't know. There is no desperate need for the tests from my perspective.

comment:185 Changed 2 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:186 Changed 2 years ago by stumpc5

@jdemeyer, @tscrim: I would appreciate this ticket to be merged soon so that we can move forward with the project. Do you have any additional critiques to be taken into account or is this ready to go?

Anyway, thanks a lot for your previous work on this ticket!

comment:187 follow-ups: Changed 2 years ago by vdelecroix

Main comment:

  • the file base.pyx is huge. It would be nice to split it.

Technical comments

  • no need to inherit from SageObject (this is useful if you want your objects to interact with other Sage objects which is is not the case)
  • why calculate_dimension is not a method of ListOfFaces?
  • nr_vertices sometimes return a SageInteger and sometimes a Python int (because len(X) returns a Python integer)
  • set_request_dimension is a weird name
  • Are we supposed to change set_request_dimension during iteration as follows
    sage: P = polytopes.cuboctahedron()
    sage: C = CombinatorialPolyhedron(P)
    sage: it = C.face_iter()
    sage: next(it)
    0
    sage: it.set_request_dimension(2)
    sage: next(it)
    2
    sage: it.set_request_dimension(1)
    sage: next(it)
    1
    
    if not this request_dimension would better be set in the constructor (__init__), if yes then it should be documented what does this do.
  • get_dimension is a weird name. It would better be more explicit current_face_dimension or something similar (no need for the word get)

doc of combinatorial_polyhedron/base.pyx

  • the first line would better be the title of the module (eg look like rings/integer.pyx)
  • [...] works on every lattice that is obtained by from [...]
  • Could you precise what the sentence Representations in this module: mean. Do you mean that it is the terminology you use in this module?
  • The first bit represent -> represents
  • we started with -> we started from
  • I would rather use compute rather than calculate
  • polyhedron used as a noun as no need to be upper cased Polyhedron -> polyhedron

comment:188 follow-up: Changed 2 years ago by vdelecroix

small optimization: use smallInteger instead of Integer (this does not create new integer objects but rather uses preallocated small integer objects)

comment:189 Changed 2 years ago by vdelecroix

  • Might be faster then -> Might be faster than

comment:190 Changed 2 years ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:191 Changed 2 years ago by git

  • Commit changed from 12038d392fc1dba2a34fe27ce0732eb2481104d9 to db48cb0226defdd76dbdc2d7e316a284b9b4fde4

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

9a97096corrected blocks
a3672a1FaceIterator is an actual iterator now
3fae342fixed allocation of array
32eb8d4it.next() -> next(it), also fixed face_lattice_facet_repr for trivial cases
08d49c0improved documentation mostly
2223ce5replaced calloc by new[]
a9a052eImproved comments all through base.pyx
ef7af54improved pseudo-code Algorithm in ``FaceIterator``
4a09a21Corrected a mathematical error in explonation.
db48cb0removed notes and old files again

comment:192 in reply to: ↑ 188 ; follow-up: Changed 2 years ago by gh-kliem

This is doing a typecast, as it assumes (signed) long as input.

I'm using size_t in most cases. But I guess for my use case this is just fine.

Replying to vdelecroix:

small optimization: use smallInteger instead of Integer (this does not create new integer objects but rather uses preallocated small integer objects)

comment:193 in reply to: ↑ 187 ; follow-up: Changed 2 years ago by gh-kliem

Replying to vdelecroix:

Technical comments

  • no need to inherit from SageObject (this is useful if you want your objects to interact with other Sage objects which is is not the case)

"All objects in Sage should derive from the Cython extension class SageObject" http://doc.sagemath.org/html/en/developer/coding_in_python.html?highlight=sageobject

Now I'm a bit confused. The way I understand this now, is that any class a user is intended to see needs to be a SageObject. Some Cython class way in the background does not need that.

In my case CombinatorialPolyhedron and FaceIterator should be SageObjects, but other classes do not have to be?

comment:194 in reply to: ↑ 193 Changed 2 years ago by vdelecroix

Replying to gh-kliem:

Replying to vdelecroix:

Technical comments

  • no need to inherit from SageObject (this is useful if you want your objects to interact with other Sage objects which is is not the case)

"All objects in Sage should derive from the Cython extension class SageObject" http://doc.sagemath.org/html/en/developer/coding_in_python.html?highlight=sageobject

This is a very naive generality, I opened #27683

Now I'm a bit confused. The way I understand this now, is that any class a user is intended to see needs to be a SageObject. Some Cython class way in the background does not need that.

In my case CombinatorialPolyhedron and FaceIterator should be SageObjects, but other classes do not have to be?

The SageObject is indeed good for user-visible classes.

comment:195 in reply to: ↑ 192 Changed 2 years ago by vdelecroix

Replying to gh-kliem:

This is doing a typecast, as it assumes (signed) long as input.

I'm using size_t in most cases. But I guess for my use case this is just fine.

Indeed, for the range of integers you look at you are very far from the overflow.

comment:196 Changed 2 years ago by git

  • Commit changed from db48cb0226defdd76dbdc2d7e316a284b9b4fde4 to 1a128f25dbabf6aab69fc37e4e20f7141ce8f3cb

Branch pushed to git repo; I updated commit sha1. New commits:

1a128f2split the file

comment:197 in reply to: ↑ 187 ; follow-up: Changed 2 years ago by gh-kliem

Replying to vdelecroix:

Main comment:

  • the file base.pyx is huge. It would be nice to split it.

Done.

Technical comments

  • no need to inherit from SageObject (this is useful if you want your objects to interact with other Sage objects which is is not the case)
  • why calculate_dimension is not a method of ListOfFaces?
  • nr_vertices sometimes return a SageInteger and sometimes a Python int (because len(X) returns a Python integer)
  • set_request_dimension is a weird name
  • Are we supposed to change set_request_dimension during iteration as follows
    sage: P = polytopes.cuboctahedron()
    sage: C = CombinatorialPolyhedron(P)
    sage: it = C.face_iter()
    sage: next(it)
    0
    sage: it.set_request_dimension(2)
    sage: next(it)
    2
    sage: it.set_request_dimension(1)
    sage: next(it)
    1
    
    if not this request_dimension would better be set in the constructor (__init__), if yes then it should be documented what does this do.

I guess this has to go there.

  • get_dimension is a weird name. It would better be more explicit current_face_dimension or something similar (no need for the word get)

doc of combinatorial_polyhedron/base.pyx

  • the first line would better be the title of the module (eg look like rings/integer.pyx)

should I name the module geometry/polyhedron/combinatorial_polyhedorn/combinatorial_polyhedron.pyx then?

comment:198 in reply to: ↑ 197 Changed 2 years ago by vdelecroix

Replying to gh-kliem:

doc of combinatorial_polyhedron/base.pyx

  • the first line would better be the title of the module (eg look like rings/integer.pyx)

should I name the module geometry/polyhedron/combinatorial_polyhedorn/combinatorial_polyhedron.pyx then?

The name of the file is fine. I was referring to the first line in the file

+CombinatorialPolyhedron gathers several algorithms of Polyhedra depending only
+on the vertex-facet incidences.

that should be

Combinatorial polyhedron

This module gathers algorithms for polyhedra that only depends on the
vertex-facet incidences.
Last edited 2 years ago by vdelecroix (previous) (diff)

comment:199 Changed 2 years ago by git

  • Commit changed from 1a128f25dbabf6aab69fc37e4e20f7141ce8f3cb to 9b69f506441ea60af9a6c3c078359c533def1a13

Branch pushed to git repo; I updated commit sha1. New commits:

fd1adf9split list_of_faces, fixed imports etc.
9b69f50added documentation and examples to each module

comment:200 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:201 Changed 2 years ago by git

  • Commit changed from 9b69f506441ea60af9a6c3c078359c533def1a13 to 4e8fd8c582f29960f6fcf5808a0cab0d0daf5b57

Branch pushed to git repo; I updated commit sha1. New commits:

4e8fd8ccorrect hyperlinks

comment:202 Changed 2 years ago by gh-kliem

How do I check if all links in the docstrings work?

comment:203 follow-up: Changed 2 years ago by vdelecroix

  • Branch changed from public/26887 to public/26887-bis
  • Commit changed from 4e8fd8c582f29960f6fcf5808a0cab0d0daf5b57 to 611099f6ebb69e71dc590af00f150bc2e154a116
  • Status changed from needs_review to needs_work

This comment concerns only CombinatorialPolyhedron in base.pxd and base.pyx

I added a small commit on top of your branch which just consists of documentation modifications. You might want to review my changes. When they are important, I discuss them below. In a second commit I upgraded the method facets to avoid iterating twice through the faces. You are free to use the commit as you wish and I put them an a distinct branch.

The sentence

    # Edges, ridges and incidences are stored in a pointer of pointers.
    # This number determines how many edges are stored in ``edges[0]``,
    # how many ridges are stored in ``ridges[0]`` etc.
    cdef size_t _length_edges_list

is a bit unclear. Do you mean that the arrays pointed at _edges[0], _ridges[0] and _face_lattice_incidences[0] have the same length?

The attribute _mem_tuple is not used. What is it inteded for?

Why this very ambiguous terminology

- Vertices              -- ``[vertices, rays, lines]`` of the polyhedron.

In PPL the use the word *generators* for this (as opposed to *constraints* for equalities and inequalities).

This is very cryptic

:class:`~sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator`::

    sage: C.face_iter()
    Iterator over the proper faces of a polyhedron of dimension 4

    sage: C.face_iter(2)
    Iterator over the 2-faces of a polyhedron of dimension 4

The above doctest is mostly intended for a user reading the documentation. As a user, I tried the naive

sage: P = polytopes.hypercube(4)
sage: C = CombinatorialPolyhedron(P)
sage: for f in C.face_iter():
....:     print(f)

and was quite disappointed to see a list of integers. I think that at this point in the documentation, it is much better to provide a concrete example of computations. If the access to face_iter is already for an advanced user then you can just remove the example.

In the documentation of the ComintorialPolyhedron class you had three examples dealing with the fact that nr_lines is mandatory. I removed the two last and made them inside TESTS. You can freely remove them if you feel they are useless.

is_Polyhedron (line 275) and is_LatticePolytope (line 288) are old style coding from when Sage was created. Just use straight isinstance.

At lines 299

        else:
            # Input is different from ``Polyhedron`` and ``LatticePolytope``.
            if nr_lines is None:
                # bounded polyhedron

it is possible that the user specified nr_lines=0 in which case you might also want to set self._unbounded = False. Also, when nr_lines < 0 you would better raise a ValueError.

At line 324, the sentence is incomplete

# At the moment this test only works for input being

At line 346, the following test is not exhaustive enough

elif isinstance(data, Integer):

as it will not catch Python integers

sage: CombinatorialPolyhedron(3r)
Traceback (most recent call last):
...
TypeError: argument 2 to map() must support iteration

You should be using

sage: import numbers
sage: isinstance(3r, numbers.Integral)
True
sage: isinstance(3, numbers.Integral)
True

On the class Polyhedron the how-many-are-there methods are called n_vertices, n_rays, n_lines, n_inequalities (with alias n_facets), n_equations while you choose nr_vertices, nr_facets. Why this difference?

line 625-627

            return Integer(self._length_Vrep)
        else:
            return Integer(len(self.vertices()))

line 737

        return Integer(self._nr_facets)

you can use smallInteger


New commits:

72ac3b0documentation fix
611099fDo not iterate twice for CombinatorialPolyhedron.facets()

comment:204 Changed 2 years ago by gh-kliem

  • Branch changed from public/26887-bis to public/26887

Looks good to me.

comment:205 in reply to: ↑ 203 Changed 2 years ago by gh-kliem

Thanks.

About names: There are a number of names that should probably changed to be consistent with the (up to date) naming conventions.

How do I call the methods that get the vertices/rays/lines of a face? How do I call the method that gets the facets it is contained in?

I will change nr_... to n_... all through the files eventually.

Replying to vdelecroix:

This comment concerns only CombinatorialPolyhedron in base.pxd and base.pyx

I added a small commit on top of your branch which just consists of documentation modifications. You might want to review my changes. When they are important, I discuss them below. In a second commit I upgraded the method facets to avoid iterating twice through the faces. You are free to use the commit as you wish and I put them an a distinct branch.

The sentence

    # Edges, ridges and incidences are stored in a pointer of pointers.
    # This number determines how many edges are stored in ``edges[0]``,
    # how many ridges are stored in ``ridges[0]`` etc.
    cdef size_t _length_edges_list

is a bit unclear. Do you mean that the arrays pointed at _edges[0], _ridges[0] and _face_lattice_incidences[0] have the same length?

I will make this more precise. _edges[0][0] represents the first index of the first edge _edges[0][1] the second of the first _edges[1][0] the first of the second and so on. _edges[0] stores a total of up _length_edges_list length.

I want to avoid jumping through memory like crazy, but I also want to avoid using too large chunks of continuous memory. Hence this intermediate solution.

The attribute _mem_tuple is not used. What is it inteded for?

It is used. The MemoryAllocators? that store edges, ridges and face_lattice_incidences get put there. The module first calculates the edges and on success copies the data. Only then does it also copy the MemoryAllocator?. Otherwise, the memory is free again.

Why this very ambiguous terminology

- Vertices              -- ``[vertices, rays, lines]`` of the polyhedron.

In PPL the use the word *generators* for this (as opposed to *constraints* for equalities and inequalities).

In FaceIterator I use atoms (which might be generators or constraints depending on whether we do the dual approach or not). I was thinking about this and then figured that Vrepresentation is a pretty bad name for [vertices, rays, lines] anyway. I don't care. I can change this at some point.

This is very cryptic

:class:`~sage.geometry.polyhedron.combinatorial_polyhedron.face_iterator.FaceIterator`::

    sage: C.face_iter()
    Iterator over the proper faces of a polyhedron of dimension 4

    sage: C.face_iter(2)
    Iterator over the 2-faces of a polyhedron of dimension 4

The above doctest is mostly intended for a user reading the documentation. As a user, I tried the naive

sage: P = polytopes.hypercube(4)
sage: C = CombinatorialPolyhedron(P)
sage: for f in C.face_iter():
....:     print(f)

and was quite disappointed to see a list of integers. I think that at this point in the documentation, it is much better to provide a concrete example of computations. If the access to face_iter is already for an advanced user then you can just remove the example.

No it was not intended to be for an advanced user. I will try setting up the result of the iterater as a class CombinatorialFace just like with Polyhedron.faces. If this does not have a noticable effect on runtime, I think this is the much better solution. This would also make FaceIterator smaller.

In the documentation of the ComintorialPolyhedron class you had three examples dealing with the fact that nr_lines is mandatory. I removed the two last and made them inside TESTS. You can freely remove them if you feel they are useless.

is_Polyhedron (line 275) and is_LatticePolytope (line 288) are old style coding from when Sage was created. Just use straight isinstance.

What do I do for matrix? isinstance(M,sage.matrix.matrix0.Matrix)?

At lines 299

        else:
            # Input is different from ``Polyhedron`` and ``LatticePolytope``.
            if nr_lines is None:
                # bounded polyhedron

it is possible that the user specified nr_lines=0 in which case you might also want to set self._unbounded = False. Also, when nr_lines < 0 you would better raise a ValueError.

By nr_lines=0, I mean that the Polyhedron is unbounded. Maybe this is not a good choice and I should put unbounded as an extra argument for the input.

At line 324, the sentence is incomplete

# At the moment this test only works for input being

At line 346, the following test is not exhaustive enough

elif isinstance(data, Integer):

as it will not catch Python integers

sage: CombinatorialPolyhedron(3r)
Traceback (most recent call last):
...
TypeError: argument 2 to map() must support iteration

You should be using

sage: import numbers
sage: isinstance(3r, numbers.Integral)
True
sage: isinstance(3, numbers.Integral)
True

Thanks. I wasn't aware of this at all. In particual I didn't know of the nice solution. Somewhere else I do a try: if a == Integer(a)...

On the class Polyhedron the how-many-are-there methods are called n_vertices, n_rays, n_lines, n_inequalities (with alias n_facets), n_equations while you choose nr_vertices, nr_facets. Why this difference?

Historic. I changed at at findpoly.org now to be consistent with Polyhedron. I should change this.

line 625-627

            return Integer(self._length_Vrep)
        else:
            return Integer(len(self.vertices()))

line 737

        return Integer(self._nr_facets)

you can use smallInteger


New commits:

72ac3b0documentation fix
611099fDo not iterate twice for CombinatorialPolyhedron.facets()

comment:206 Changed 2 years ago by git

  • Commit changed from 611099f6ebb69e71dc590af00f150bc2e154a116 to d38e1300355722815880dbd633863dd4d1b54173

Branch pushed to git repo; I updated commit sha1. New commits:

d38e130added combinatorial face

comment:207 Changed 2 years ago by git

  • Commit changed from d38e1300355722815880dbd633863dd4d1b54173 to ca606656ddadfd4da9f98a74d0406b967a825698

Branch pushed to git repo; I updated commit sha1. New commits:

ca60665improved docstring in list_of_all_faces

comment:208 Changed 2 years ago by gh-kliem

  • Status changed from needs_work to needs_review

I moved some of the methods to CombinatorialFace now. This should be much nicer for a regular user to handle. The iterator returns something that one can use.

comment:209 Changed 2 years ago by chapoton

does not build, see patchbot reports

comment:210 Changed 2 years ago by git

  • Commit changed from ca606656ddadfd4da9f98a74d0406b967a825698 to abe00b66751c26f756b7b247064f8db01d5b0f0e

Branch pushed to git repo; I updated commit sha1. New commits:

abe00b6fixed small issues

comment:211 follow-ups: Changed 23 months ago by vdelecroix

Just some small things. I am likely to accept a positive review on next round.

  • You use custom bitsets. Why not using the one provided in SageMath sage.data_structures/bitest.[pxi,pxd]? Most of it already uses optimized routines from GMP.
  • The name ListOfAllFaces sounds really strange.
  • It would be good to simplfy and uniformize string representations
    • CombinatorialPolyhedron
      Combinatorial type of a polyhedron of dimension 4 with 16 vertices
      
      would better be
      A 4-dimensional combinatorial polyhedron with 16 vertices
      
    • FaceIterator
      Iterator over the 2-faces of a polyhedron of dimension 4
      
      would better be
      Iterator over the 2-faces of a 4-dimensional combinatorial polyhedron
      
    • CombinatorialFace
      Combinatorial type of a 2-dimensional face of a 3-dimensional polyhedron
      
      would better be
      A 2-dimensional face of 3-dimensional combinatorial polyhedron
      
  • in face_iterator.pyx and list_of_faces.pyx there is no need to redefine the terminology already used in base.pyx. Just make a reference to the module.
  • If the error at line 2012 in of base.pyx can happen in a normal run it should be doctested. If not, replace it with a RuntimeError.
  • The module title should be words (not ListOfAllFaces or ListOfFaces)

comment:212 in reply to: ↑ 211 Changed 23 months ago by gh-kliem

Replying to vdelecroix:

Just some small things. I am likely to accept a positive review on next round.

  • You use custom bitsets. Why not using the one provided in SageMath sage.data_structures/bitest.[pxi,pxd]? Most of it already uses optimized routines from GMP.

I wasn't aware of this at all. At some point I was looking for it but didn't find it.

To compute the f-vector etc. very fast, it seems to be important to not allocate any memory at all during the iteration (I actually should move the one alloc in get_next_level to a global property in FaceIterator as it will speed things up by about 4 percent).

In order to make this all work, I would have to use bitset_t directly.

I guess I could. At the moment, it doesn't seem to me that the code will get a lot easier. Instead of allocating my memory with MemoryAllocator I would then allocate it with Bitset. The advantage of reinventing the wheel is that I could later enable intrinsics, which would give a speedup of at least 2 on many computers. I don't know how important this is.

  • The name ListOfAllFaces sounds really strange.
  • It would be good to simplfy and uniformize string representations
    • CombinatorialPolyhedron
      Combinatorial type of a polyhedron of dimension 4 with 16 vertices
      
      would better be
      A 4-dimensional combinatorial polyhedron with 16 vertices
      
    • FaceIterator
      Iterator over the 2-faces of a polyhedron of dimension 4
      
      would better be
      Iterator over the 2-faces of a 4-dimensional combinatorial polyhedron
      
    • CombinatorialFace
      Combinatorial type of a 2-dimensional face of a 3-dimensional polyhedron
      
      would better be
      A 2-dimensional face of 3-dimensional combinatorial polyhedron
      
  • in face_iterator.pyx and list_of_faces.pyx there is no need to redefine the terminology already used in base.pyx. Just make a reference to the module.
  • If the error at line 2012 in of base.pyx can happen in a normal run it should be doctested. If not, replace it with a RuntimeError.

This type of error is mostly meant for the case of an interrupt happening (in this case it will not be raised though). I don't expect this to happen ever.

  • The module title should be words (not ListOfAllFaces or ListOfFaces)

comment:213 follow-up: Changed 23 months ago by stumpc5

It would be good to simplfy and uniformize string representations

Here are two more issues with the repr:

sage: P = Polyhedron(ieqs=[[0,1]]); P
A 1-dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex and 1 ray
sage: CombinatorialPolyhedron(P)
Combinatorial type of a polyhedron of dimension 1 with 1 vertices

Why do you suppress the information about the ray here?

sage: P = Polyhedron(ieqs=[[0,1,0]]); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex, 1 ray, 1 line

This is correct if we consider P to be the product of a single ray starting from the origin and a line. But this polyhedron itself does not have a one-dimensional face (aka vertex) in the usual definition of faces. On the other hand,

sage: CombinatorialPolyhedron(P)
Combinatorial type of a polyhedron of dimension 2 with 0 vertices

is correct, but suppresses the information about rays and lines.

Also, might it be worth being able to provide the information about atoms, coatoms and ignored facets (if any) in the lattice that is used to iterate through all faces?

comment:214 in reply to: ↑ 213 ; follow-ups: Changed 23 months ago by gh-kliem

Replying to stumpc5:

It would be good to simplfy and uniformize string representations

Here are two more issues with the repr:

sage: P = Polyhedron(ieqs=[[0,1]]); P
A 1-dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex and 1 ray
sage: CombinatorialPolyhedron(P)
Combinatorial type of a polyhedron of dimension 1 with 1 vertices

Why do you suppress the information about the ray here?

sage: P = Polyhedron(ieqs=[[0,1,0]]); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex, 1 ray, 1 line

This is correct if we consider P to be the product of a single ray starting from the origin and a line. But this polyhedron itself does not have a one-dimensional face (aka vertex) in the usual definition of faces. On the other hand,

sage: CombinatorialPolyhedron(P)
Combinatorial type of a polyhedron of dimension 2 with 0 vertices

is correct, but suppresses the information about rays and lines.

I could just add it, I guess.

Also, might it be worth being able to provide the information about atoms, coatoms and ignored facets (if any) in the lattice that is used to iterate through all faces?

Can you be more precise? I don't get what you want. Should I store the information somewhere, if one does ignore_subfaces? What do you mean by provide the information about atoms and coatoms?

comment:215 in reply to: ↑ 214 ; follow-up: Changed 23 months ago by stumpc5

Replying to gh-kliem:

Can you be more precise? I don't get what you want.

Sorry -- I meant to ask you to provide methods atoms, coatoms and ( ignored_facet or facet_at_infinity ). Also, it is worth pointing in the documentation to the description of the algorithm in the paper so that it becomes clear what atoms and coatoms are.

comment:216 in reply to: ↑ 215 Changed 23 months ago by gh-kliem

Replying to stumpc5:

Replying to gh-kliem:

Can you be more precise? I don't get what you want.

Sorry -- I meant to ask you to provide methods atoms, coatoms and ( ignored_facet or facet_at_infinity ). Also, it is worth pointing in the documentation to the description of the algorithm in the paper so that it becomes clear what atoms and coatoms are.

At the moment the FaceIterator is just an Iterator with two extra methods (that manipulate iteration). I don't know, how much sense it makes, to provide more methods.

The method ignored_facet does not make any sense at the moment. For an unbounded polyhedron, there is no facet at infinity as part of the input. Not providing the facet at infinity works as well (and this is the way the Iterator is set up).

One could add a method, that provides the faces that are currently ignored.

While the iterator knows coatoms (and their names) it doesn't know the atoms (only their names). The atoms are calculated along the way (while the names for the indices might have been provided). Adding such a method isn't a big deal, but it's not there at the moment.

comment:217 in reply to: ↑ 211 ; follow-up: Changed 23 months ago by gh-kliem

Replying to vdelecroix:

Just some small things. I am likely to accept a positive review on next round.

  • The name ListOfAllFaces sounds really strange.

Can we agree on a name, before I change it?

This class stores all faces of the polyhedron to generate then all cover relations for the face lattice. Possibly in the future it can also calculate a specified flag vector.

What would be a good name for it?

FaceLattice(Creator), CoverRelations. I can't think of a better name at the moment.

comment:218 in reply to: ↑ 217 ; follow-up: Changed 23 months ago by vdelecroix

Replying to gh-kliem:

Replying to vdelecroix:

Just some small things. I am likely to accept a positive review on next round.

  • The name ListOfAllFaces sounds really strange.

Can we agree on a name, before I change it?

This class stores all faces of the polyhedron to generate then all cover relations for the face lattice. Possibly in the future it can also calculate a specified flag vector.

What would be a good name for it?

FaceLattice(Creator), CoverRelations. I can't think of a better name at the moment.

A name closer to the initial one is PolyhedronFaces. If this object contains all the information about the lattice, then PolyhedronFaceLattice is even better.

comment:219 Changed 23 months ago by gh-kliem

  • Status changed from needs_review to needs_work

comment:220 in reply to: ↑ 218 Changed 23 months ago by gh-kliem

Replying to vdelecroix:

then PolyhedronFaceLattice is even better.

I like it.

I will be working in the comments now. Might take some time, as I'm only able to work 5 minutes at a time or so (or at night).

comment:221 in reply to: ↑ 214 Changed 23 months ago by gh-kliem

I now give the number of facets. This seems more natural to me, as this is how CombinatorialPolyhedron is constructed from the facets. This seems to be more meaningful for many unbounded polyhedra as well (unless one wants to count lowest dimensional proper faces as "vertices").

Also it seems hard to determine the difference between vertices and rays from an incidence matrix.

At the moment this module is not optimized for unbounded polyhedra, but I guess this should be left for later (e.g. the vertices are recalculated every time).

Replying to gh-kliem:

Replying to stumpc5:

It would be good to simplfy and uniformize string representations

Here are two more issues with the repr:

sage: P = Polyhedron(ieqs=[[0,1]]); P
A 1-dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex and 1 ray
sage: CombinatorialPolyhedron(P)
Combinatorial type of a polyhedron of dimension 1 with 1 vertices

Why do you suppress the information about the ray here?

sage: P = Polyhedron(ieqs=[[0,1,0]]); P
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex, 1 ray, 1 line

This is correct if we consider P to be the product of a single ray starting from the origin and a line. But this polyhedron itself does not have a one-dimensional face (aka vertex) in the usual definition of faces. On the other hand,

sage: CombinatorialPolyhedron(P)
Combinatorial type of a polyhedron of dimension 2 with 0 vertices

is correct, but suppresses the information about rays and lines.

I could just add it, I guess.

Also, might it be worth being able to provide the information about atoms, coatoms and ignored facets (if any) in the lattice that is used to iterate through all faces?

Can you be more precise? I don't get what you want. Should I store the information somewhere, if one does ignore_subfaces? What do you mean by provide the information about atoms and coatoms?

comment:222 Changed 23 months ago by git

  • Commit changed from abe00b66751c26f756b7b247064f8db01d5b0f0e to 87653135948037f4e385a8cb0896379cda1608d6

Branch pushed to git repo; I updated commit sha1. New commits:

8765313A number of small edits.

comment:223 Changed 23 months ago by gh-kliem

  • Status changed from needs_work to needs_review

I think I took care of above comments.

comment:224 Changed 23 months ago by vdelecroix

  • Reviewers set to Jeroen Demeyer, Travis Scrimshaw, Vincent Delecroix

I propose to move forward and set to positive review. If nobody objects, I will do so later today.

comment:225 follow-up: Changed 23 months ago by stumpc5

I don't want to slow this ticket down by any means. Anyways, isn't the following two times the same combinatorial polyhedron

sage: def KunzCone(m):
....:     V = ZZ^(m-1)
....:     B = V.basis()
....:     ieqs = [ [0] + list(B[i-1]+B[j-1]-B[(i+j-1) % m]) for j in [1 .. m-1] for i in [1 .. j] if i+j != m]
....:     return Polyhedron(ieqs=ieqs, backend="normaliz")

sage: P = KunzCone(5)
sage: Q1 = CombinatorialPolyhedron(P)
sage: Q1
Combinatorial type of a polyhedron of dimension 4 with 1 vertices
sage: Q2 = CombinatorialPolyhedron(Q1.facets(names=False))
sage: Q2
Combinatorial type of a polyhedron of dimension 4 with 9 vertices
sage: Q1.f_vector(); Q2.f_vector()
(1, 1, 8, 14, 8, 1)
(1, 1, 8, 14, 8, 1)

and can thus only have either 1 or 9 vertices (whatever the definition of vertices might be)?

As said, I would positive about letting this pass---as it is really strong computational-wise---and postpone any minor issues into new tickets.

comment:226 in reply to: ↑ 225 ; follow-up: Changed 23 months ago by gh-kliem

The representation has changed to give the number of facets now. So this output won't happen like this anymore.

Anyway, one has to set the correct nr_lines, when giving a list of facets for an unbounded polyhedron.

if the polyhedron is unbounded, then rays and lines and the extra argument nr_lines are required

It his hard to determine from a list, which elements of the Vrepresentation are actually vertices and which are rays (and in one instance it is impossible to distinct between nr_lines = 0 and nr_lines = 1 just from this input, hence the requirement). If the polyhedron is not unbounded, than the algorithm can just proceed on the polar polyhedron, this is not possible in the unbounded case.

Replying to stumpc5:

I don't want to slow this ticket down by any means. Anyways, isn't the following two times the same combinatorial polyhedron

sage: def KunzCone(m):
....:     V = ZZ^(m-1)
....:     B = V.basis()
....:     ieqs = [ [0] + list(B[i-1]+B[j-1]-B[(i+j-1) % m]) for j in [1 .. m-1] for i in [1 .. j] if i+j != m]
....:     return Polyhedron(ieqs=ieqs, backend="normaliz")

sage: P = KunzCone(5)
sage: Q1 = CombinatorialPolyhedron(P)
sage: Q1
Combinatorial type of a polyhedron of dimension 4 with 1 vertices
sage: Q2 = CombinatorialPolyhedron(Q1.facets(names=False))
sage: Q2
Combinatorial type of a polyhedron of dimension 4 with 9 vertices
sage: Q1.f_vector(); Q2.f_vector()
(1, 1, 8, 14, 8, 1)
(1, 1, 8, 14, 8, 1)

and can thus only have either 1 or 9 vertices (whatever the definition of vertices might be)?

As said, I would positive about letting this pass---as it is really strong computational-wise---and postpone any minor issues into new tickets.

comment:227 in reply to: ↑ 226 Changed 23 months ago by gh-kliem

I think the input arguments should be more intuitive. I also think this should happen in a follow up ticket.

Instead of doing it all over n_lines, one should have another argument is_bounded. I think this is easier to use.

Replying to gh-kliem:

The representation has changed to give the number of facets now. So this output won't happen like this anymore.

Anyway, one has to set the correct nr_lines, when giving a list of facets for an unbounded polyhedron.

if the polyhedron is unbounded, then rays and lines and the extra argument nr_lines are required

It his hard to determine from a list, which elements of the Vrepresentation are actually vertices and which are rays (and in one instance it is impossible to distinct between nr_lines = 0 and nr_lines = 1 just from this input, hence the requirement). If the polyhedron is not unbounded, than the algorithm can just proceed on the polar polyhedron, this is not possible in the unbounded case.

Replying to stumpc5:

I don't want to slow this ticket down by any means. Anyways, isn't the following two times the same combinatorial polyhedron

sage: def KunzCone(m):
....:     V = ZZ^(m-1)
....:     B = V.basis()
....:     ieqs = [ [0] + list(B[i-1]+B[j-1]-B[(i+j-1) % m]) for j in [1 .. m-1] for i in [1 .. j] if i+j != m]
....:     return Polyhedron(ieqs=ieqs, backend="normaliz")

sage: P = KunzCone(5)
sage: Q1 = CombinatorialPolyhedron(P)
sage: Q1
Combinatorial type of a polyhedron of dimension 4 with 1 vertices
sage: Q2 = CombinatorialPolyhedron(Q1.facets(names=False))
sage: Q2
Combinatorial type of a polyhedron of dimension 4 with 9 vertices
sage: Q1.f_vector(); Q2.f_vector()
(1, 1, 8, 14, 8, 1)
(1, 1, 8, 14, 8, 1)

and can thus only have either 1 or 9 vertices (whatever the definition of vertices might be)?

As said, I would positive about letting this pass---as it is really strong computational-wise---and postpone any minor issues into new tickets.

comment:228 Changed 23 months ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:229 Changed 23 months ago by vdelecroix

Please move any further discussion to new tickets.

comment:230 Changed 23 months ago by chapoton

  • Dependencies #27292 deleted

comment:231 follow-up: Changed 22 months ago by vbraun

  • Status changed from positive_review to needs_work

Fails on e.g. Debian 8:

[sagelib-8.8] [ 98/495] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -fPIC -I/home/buildbot/slave/sage_git/build/local/include/python2.7 -c sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc -o build/temp.linux-i686-2.7/sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.o
[sagelib-8.8] In file included from /usr/include/c++/4.9/cstdint:35:0,
[sagelib-8.8]                  from sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:13:
[sagelib-8.8] /usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
[sagelib-8.8]  #error This file requires compiler and library support for the \
[sagelib-8.8]   ^
[sagelib-8.8] sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:27:22: error: ‘is_subset’ declared as an ‘inline’ variable

comment:232 in reply to: ↑ 231 ; follow-up: Changed 22 months ago by gh-kliem

As far as I know there are two ways of solving this.

Either use the macro __cplusplus to determine the c++ version and not use inline if it is not available. (This would be a quick fix I guess).

Use -std=c++11 as compile argument.

Any opinions?

Replying to vbraun:

Fails on e.g. Debian 8:

[sagelib-8.8] [ 98/495] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -fPIC -I/home/buildbot/slave/sage_git/build/local/include/python2.7 -c sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc -o build/temp.linux-i686-2.7/sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.o
[sagelib-8.8] In file included from /usr/include/c++/4.9/cstdint:35:0,
[sagelib-8.8]                  from sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:13:
[sagelib-8.8] /usr/include/c++/4.9/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
[sagelib-8.8]  #error This file requires compiler and library support for the \
[sagelib-8.8]   ^
[sagelib-8.8] sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc:27:22: error: ‘is_subset’ declared as an ‘inline’ variable

comment:233 in reply to: ↑ 232 Changed 22 months ago by vdelecroix

Replying to gh-kliem:

As far as I know there are two ways of solving this.

Either use the macro __cplusplus to determine the c++ version and not use inline if it is not available. (This would be a quick fix I guess).

Use -std=c++11 as compile argument.

Any opinions?

Add the -std=c++11 option to the concerned extension

    Extension('sage.geometry.polyhedron.combinatorial_polyhedron.bit_vector_operations.cc',
              sources = ['sage/geometry/polyhedron/combinatorial_polyhedron/bit_vector_operations.cc'],
              extra_compile_args=['-std=c++11']),

comment:234 Changed 22 months ago by git

  • Commit changed from 87653135948037f4e385a8cb0896379cda1608d6 to 39a70997144faad3c3656770fb17de1e6c4805eb

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

092c916split list_of_faces, fixed imports etc.
46d54b3added documentation and examples to each module
8ee84cecorrect hyperlinks
3869c1fdocumentation fix
938b04cDo not iterate twice for CombinatorialPolyhedron.facets()
e6d5b08added combinatorial face
69e28baimproved docstring in list_of_all_faces
1e2a52bfixed small issues
e298ed0A number of small edits.
39a7099added compile argument -std=c++11

comment:235 Changed 22 months ago by gh-kliem

  • Status changed from needs_work to needs_review

added compile argument, this should work now (also #27987 fixes already a bug in the unbounded case)

Thanks for all the help, btw.

comment:236 Changed 22 months ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:237 Changed 22 months ago by chapoton

  • Milestone changed from sage-8.8 to sage-8.9

comment:238 Changed 22 months ago by vbraun

  • Branch changed from public/26887 to 39a70997144faad3c3656770fb17de1e6c4805eb
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:239 Changed 21 months ago by chapoton

  • Commit 39a70997144faad3c3656770fb17de1e6c4805eb deleted

This triggers a new failing doctest with python3-sage:

sage -t --long src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx
**********************************************************************
File "src/sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 937, in sage.geometry.polyhedron.combinatorial_polyhedron.base.CombinatorialPolyhedron.edge_graph
Failed example:
    G.degree()
Expected:
    [4, 3, 4, 3, 4]
Got:
    [3, 4, 4, 3, 4]

comment:240 Changed 21 months ago by chapoton

I have made #28153 for the py3 problem, please review.

comment:241 follow-up: Changed 21 months ago by gh-kliem

Some attributes like bitrep_vertices might have been an unfortunate choice:

As they are accessed by other classes, I'm forced to compute e.g. bitrep_vertices on initialization. If CombinatorialPolyhedron was ever to be a parent of Polyhedron_base (see #10777), this would force a polyhedron to compute the incidence matrix right away.

From my understanding, the decorator @lazy_attribute is not available for extension types directly. I'm thinking of changing those attributes to methods, such that there is a method bitrep_facets and an attribute _bitrep_facets. This way one can later change this to be lazily evaluated.

Any thoughts?

comment:242 in reply to: ↑ 241 Changed 21 months ago by vdelecroix

Replying to gh-kliem:

[...]

Please don't post messages waiting for an answer on a closed ticket. Discussion is closed. Open a new ticket and start a discussion there if something is wrong.

Note: See TracTickets for help on using tickets.