Opened 2 years ago

Closed 19 months ago

Last modified 5 months ago

#28413 closed enhancement (fixed)

Add .h_star_vector to compact rational polytopes

Reported by: jipilab Owned by:
Priority: major Milestone: sage-9.1
Component: geometry Keywords: polytopes, normaliz
Cc: selia, chapoton, Winfried, vdelecroix, mkoeppe Merged in:
Authors: Sophia Elia Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: 48d2a6f (Commits, GitHub, GitLab) Commit: 48d2a6f740428ae4b4c5dc9d431fa73976bd0687
Dependencies: #28247 Stopgaps:

Status badges

Description

Since #25091 is merged, we can compute a few more things with normaliz. One important object is the so-called h^*-vector, see https://en.wikipedia.org/wiki/Ehrhart_polynomial#Ehrhart_series for details.

This ticket implements this method. Currently, one has to do the following:

sage: C = polytopes.hypercube(3, backend="normaliz")
sage: C.ehrhart_series().numerator().coefficients()
[1, 23, 23, 1]

which would now become:

sage: C.h_star_vector()

and return an error if the backend is not 'normaliz'...

See the related SageAsk? question: https://ask.sagemath.org/question/32505/can-sage-compute-the-h-vector-of-a-polytope/

Eventually, it would be nice to also make this possible for polymake too (it would be interesting to know if they use 'normaliz' for that).

Change History (23)

comment:1 follow-up: Changed 2 years ago by gh-w-bruns

For the h*-vector o be well-defined, the polytope should have integral vertices. Otherwise there is no canonical choice for the denominator and, hence, the numerator of the Ehrhart series (as a rational function).

At least one should check that the denominator is a power of 1-t.

Version 0, edited 2 years ago by gh-w-bruns (next)

comment:2 in reply to: ↑ 1 Changed 2 years ago by jipilab

Replying to gh-w-bruns:

For the h*-vector o be well-defined, the polytope should have integral vertices. Otherwise there is no canonical choice for the denominator and, hence, the numerator of the Ehrhart series (as a rational function).

At least one should check that the denominator is a power of 1-t.

Okay! great, good to know. We'll put this check into the function.

Last edited 5 months ago by slelievre (previous) (diff)

comment:3 Changed 2 years ago by selia

  • Branch set to public/28413
  • Commit set to 8606b7e70f94b1c0abbd7af5350ba38d7b17e88a

New commits:

8606b7efirst changes for h-star function

comment:4 Changed 2 years ago by jipilab

A few comments:

+ - ``self`` -- A lattice polytope with ``backend`` = 'normaliz'.

I would put the backend comment in a NOTE environment, although I am not completely sure. It would be to be checked in the guidelines.

Just a suggestion:

- The h*-vector as a list.
+ A list whose entries give the h*-vector.
  • simplicies -> simplices

In the examples, you are only testing one of the 4 and not the four of them.

The method _h_star_vector_normaliz(self) in base should return a TypeError (as the volume_normaliz for example) and the function in backend_normaliz should be appended with _normaliz.

I would also add a less trivial example, like the 0,1 cube and perhaps hypersimplex? This would be good to get sanity checks. Further, I would include an example that uses a different backend to show even further that it requires normaliz...

Otherwise, looks good!

comment:5 Changed 20 months ago by git

  • Commit changed from 8606b7e70f94b1c0abbd7af5350ba38d7b17e88a to b9df5455594bf14929f7e7eb32ac12373048431a

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

b9df545addressing comments

comment:6 Changed 20 months ago by selia

  • Dependencies set to #28247

comment:7 Changed 20 months ago by selia

  • Status changed from new to needs_review

comment:8 Changed 20 months ago by jipilab

  • Authors set to Sophia Elia

comment:9 Changed 20 months ago by jipilab

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to needs_work

It seems there is a merge conflict... Rebase?

In the h_star_vector function, I would not say

+        - ``self`` -- A lattice polytope with ``backend`` = 'normaliz'.

but use a NOTE to say that the backend should be normaliz.

Once we have the ticket #28880 and follow-up related to double description in normaliz, it will be possible to ignore the backend and simply obtain the relevant information in order to obtain the h_star_vector using normaliz.

The syntax for math printing should be corrected in:

+        The h*-vector of a unimodular simplex S (a simplex with 
-        volume = $\frac{1}{dim(S)!} ) is always 1. Here we test this on 
-        simplicies up to dimension 4:
+        volume = `\frac{1}{(\dim S)!}`) is always 1. Here we test this on 
+        simplices up to dimension 4::

Only one of the simplices is tested below:

+            sage: s1 = polytopes.simplex(1,backend = 'normaliz')
+            sage: s2 = polytopes.simplex(2,backend = 'normaliz')
+            sage: s3 = polytopes.simplex(3,backend = 'normaliz')
+            sage: s4 = polytopes.simplex(4,backend = 'normaliz')
+            sage: s3.h_star_vector()
+            [1]        

Why not something like:

sage: [polytopes.simplex(i,backend='normaliz').h_star_vector() for i in [1,2,3,4]]
sage: [[1], [1], [1], [1]]

The function _h_star_vector in backend_normaliz.py should be renamed _h_star_vector_normaliz and the function _h_star_vector_normaliz in base.py should return raise TypeError("the backend should be normaliz").

I would also add some more examples that involve known examples where values can be relevant to check the validity.

comment:10 Changed 20 months ago by selia

I addressed many of these comments in the commit b9df545.

comment:11 Changed 20 months ago by jipilab

I see. Great!

I only looked at the first commit and started writing. Since there's a merge conflict, I couldn't see the final product.

Ok, so now it would need a rebase in any case.

comment:12 Changed 20 months ago by selia

  • Branch changed from public/28413 to public/28413rebase
  • Commit changed from b9df5455594bf14929f7e7eb32ac12373048431a to 73973be3a3896e60448cb02a63e9b0ed9a990cab

New commits:

60eafd1idk
73973beaddressing comments

comment:13 Changed 20 months ago by git

  • Commit changed from 73973be3a3896e60448cb02a63e9b0ed9a990cab to ab006dff035943b51b472557b346a966c01cf2a5

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

ab006dfremoving ehrhart_quasipolynomial

comment:14 Changed 20 months ago by jipilab

You should also add a line in the tutorials to link to this function.

comment:15 Changed 20 months ago by jipilab

  • Milestone changed from sage-pending to sage-9.1

comment:16 Changed 20 months ago by git

  • Commit changed from ab006dff035943b51b472557b346a966c01cf2a5 to a7f14cecab3d5c4c12f1aa235b65b140b4b1152c

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

8f13cacMerge branch '28247' into 28413
4cc4231added lines to tutorial and a test
a7f14ceMerge branch 'public/28247' of trac.sagemath.org:sage into 28413

comment:17 Changed 20 months ago by selia

  • Status changed from needs_work to needs_review

comment:18 Changed 19 months ago by jipilab

  • Status changed from needs_review to needs_work
  • There are no doctests in the function _h_star_vector_normaliz in backend_normaliz.py.
  • The documentation does not build:

[dochtml] docstring of sage.geometry.polyhedron.base.Polyhedron_base.h_star_vector:22: WARNING: Inline interpreted text or phrase reference start-string without end-string.

this is caused by the missing space:

        OUTPUT:

        The h*-vector as a list.

-        ..NOTE:
+        .. NOTE:

        The ``backend`` of ``self`` should be ``'normaliz'``.

I also suggest to remove the two backticks around the word backend in the docstrings as it is not a parameter of the functions.

comment:19 Changed 19 months ago by git

  • Commit changed from a7f14cecab3d5c4c12f1aa235b65b140b4b1152c to 8b8d53d9dcd8baaf194d2d5e6c8e5e45249c6830

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

8b8d53dadded tests to backend_normaliz and fixed other comments

comment:20 Changed 19 months ago by selia

  • Status changed from needs_work to needs_review

comment:21 Changed 19 months ago by git

  • Commit changed from 8b8d53d9dcd8baaf194d2d5e6c8e5e45249c6830 to 48d2a6f740428ae4b4c5dc9d431fa73976bd0687

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

48d2a6ffix documentation

comment:22 Changed 19 months ago by jipilab

  • Status changed from needs_review to positive_review

Looks good to me now. Tests are passing and the documentation now seems to builds too.

comment:23 Changed 19 months ago by vbraun

  • Branch changed from public/28413rebase to 48d2a6f740428ae4b4c5dc9d431fa73976bd0687
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.