Opened 5 years ago

Closed 5 years ago

Last modified 4 years ago

#18211 closed enhancement (fixed)

Computing Ehrhart polynomials with LattE

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.7
Component: geometry Keywords:
Cc: chapoton, bedutra, mkoeppe, vbraun, ncohen Merged in:
Authors: Vincent Delecroix Reviewers: Matthias Koeppe, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: d09d8a5 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

We just call LattE (command count) through the command line to get the Ehrhart polynomial of a lattice polytope.

For complete doctesting you should run both of the following command (with and without --long)

sage -t --optional=sage,latte_int $SAGE_ROOT/src/sage/geometry/polyhedron/
sage -t $SAGE_ROOT/src/sage/geometry/polyhedron/

Follow up: #18232

Change History (71)

comment:1 Changed 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/18211
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 5110cc954a88ce5477b7f35b60551aae69d9a788

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

5110cc9Trac 18211: use LattE to compute the Ehrhart polynomial

comment:3 follow-up: Changed 5 years ago by mkoeppe

This looks great to me.

In the docstring, could you fix the spelling: "LattE integral" -> "LattE integrale"

Also, LattE has many options that control the type of algorithm used. For example, for many examples "--maxdet=1000" will make the calculation much faster. Is there a way to allow the user to pass such options to LattE?

comment:4 Changed 5 years ago by mkoeppe

  • Description modified (diff)

comment:5 in reply to: ↑ 3 Changed 5 years ago by vdelecroix

Hello Matthias,

Replying to mkoeppe:

This looks great to me.

In the docstring, could you fix the spelling: "LattE integral" -> "LattE integrale"

Will do. Thanks. I was not sure if I needed to cite people for LattE contribution, should I?

Also, LattE has many options that control the type of algorithm used. For example, for many examples "--maxdet=1000" will make the calculation much faster. Is there a way to allow the user to pass such options to LattE?

Yes, whatever you want. The function Popen of python is flexible to send any option to the command line. Could you describe the set of option that will be interesting to have?

(I am currently testing the new method on the Sage library of polytopes... and I found plenty of bugs!)

Vincent

comment:6 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:7 follow-up: Changed 5 years ago by vbraun

Error checking would be nice. Probably just use subprocess.check_output

comment:8 in reply to: ↑ 7 Changed 5 years ago by vdelecroix

Replying to vbraun:

Error checking would be nice. Probably just use subprocess.check_output

Is check_output compatible with Popen? Is the following ok

latte_proc = Popen(*args)
ans, err = latte_proc.communicate()
ret_code = latte_proc.poll()
if ret_code:
    raise ValueError

comment:9 Changed 5 years ago by git

  • Commit changed from 5110cc954a88ce5477b7f35b60551aae69d9a788 to d52053c18a593a621af90b43608851304bc32052

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

cf2a10fTrac 18211: another example using Birkhoff_polytope
ca8da5aTrac 18211: fixed spelling LattE integral*e*
d52053cTrac 18211: check error + options

comment:10 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

All right, LattE is correctly spelled, output is checked and options are taken into account! Needs review again.

Vincent

comment:11 Changed 5 years ago by vdelecroix

By the way, I am not sure about the place where I put the code. It is currently in base_ZZ.py which means that the polytope has to be defined with equations with coefficients in ZZ. But it might be that some polyhedron with coefficients in QQ actually give a lattice polytope. If anybody has an idea about that.

comment:12 follow-up: Changed 5 years ago by mkoeppe

The LattE command line options need to be written with dashes, not underscores:

--irrational_primal --> --irrational-primal --irrational_all_primal --> --irrational-all-primal

The docstring mentions no_decomposition, but it is not handled in the code

comment:13 in reply to: ↑ 12 Changed 5 years ago by vdelecroix

Replying to mkoeppe:

The LattE command line options need to be written with dashes, not underscores:

--irrational_primal --> --irrational-primal --irrational_all_primal --> --irrational-all-primal

Right... LattE did not complain very hard.

The docstring mentions no_decomposition, but it is not handled in the code

Will do.

If you have time, could you provide more details about the command line option. I found the LattE documentation quite cryptic to that respect.

Vincent

comment:14 Changed 5 years ago by git

  • Commit changed from d52053c18a593a621af90b43608851304bc32052 to 0f5122bddee5f104a3e2ff65715129eb275452e7

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

0f5122bTrac 18211: fix command line arguments

comment:15 Changed 5 years ago by mkoeppe

For complete argument checking, it should probably say "if maxdet is not None".

comment:16 Changed 5 years ago by jdemeyer

Instead of using is_package_installed(), I would prefer the more Pythonic

try:
    latte_proc = Popen(args, stdin = PIPE, stdout=PIPE, stderr=PIPE)
except OSError:
    raise ValueError("The package latte_int must be installed!\n" + package_mesg())

comment:17 Changed 5 years ago by ncohen

  • Cc ncohen added

comment:18 Changed 5 years ago by ncohen

Is this if maxdet ok or should it be if maxdet is not None ? I am wondering about the case maxdet=0 (if it makes any sense).

comment:19 Changed 5 years ago by ncohen

(oops sorry mkoeppe. I had not noticed you had made this comment already)

I get a broken doctest about a parent:

File "polyhedron/base_ZZ.py", line 191, in sage.geometry.polyhedron.base_ZZ.Polyhedron_ZZ.?
Failed example:
    parent(_)
Expected:
    Univariate Polynomial Ring in t over Rational Field
Got:
    <type 'int'>

This is apparently solved with a optional - latte_int

Last edited 5 years ago by ncohen (previous) (diff)

comment:20 Changed 5 years ago by ncohen

Once the package is installed, I get another broken doctest

File "polyhedron/library.py", line 179, in sage.geometry.polyhedron.library.Polytopes.Birkhoff_polytope
Failed example:
    p3 = b3.ehrhart_polynomial()     # optional - latte_int
Expected:
    1/8*t^4 + 3/4*t^3 + 15/8*t^2 + 9/4*t + 1
Got:
    <BLANKLINE>

I have a question about the way you call the process, however. The way it is done, it seems that no output is being printed before the process has ended. If the user asked for verbosity, wouldn't it be better to just let the process print to stdout so that one can get some info on the process *while* it is running?

It seems that you only need to do stdout=(None if verbose else PIPE).

Nathann

comment:21 Changed 5 years ago by git

  • Commit changed from 0f5122bddee5f104a3e2ff65715129eb275452e7 to b877932445212ddfd72fd70079c53f17df6d5fd9

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

b877932Trac 18211: fix arguments + doctests + cwd=SAGE_TMP

comment:22 follow-up: Changed 5 years ago by vdelecroix

count is annoying as it always creates the two files latte_stats and totalTime. And possibly: tri.ead, tri.ecd, tri.ext, tri.iad, tri.icd, tri.ine depending on the options... I modified the execution path to be SAGE_TMP (the option cwd in Popen).

I also sorted out all other comments except comment:20. If I set stderr or stdout to something else than PIPE then I am not able to get the result of the command back when doing process.communicate().

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

I also sorted out all other comments except comment:20. If I set stderr or stdout to something else than PIPE then I am not able to get the result of the command back when doing process.communicate().

God. I had not noticed that you were reading the result from the output :-D

With the code from [1] you can do whatever you want with the output:

sage: from subprocess import Popen, PIPE
sage: p = Popen("ls",stdout=PIPE)
sage: for line in iter(p.stdout.readline,''):
....:     print line.strip()

And to check that it does not wait for the process to end, you can run a 'tail -f' on some (existing) temporary file

sage: p = Popen(["tail","-f","/tmp/eee"],stdout=PIPE)
sage: for line in iter(p.stdout.readline,''):
....:     print line.strip()

A new line appears in python every time you type "echo artartaert >> /tmp/eee" in a terminal.

[1] http://stackoverflow.com/questions/2804543/read-subprocess-stdout-line-by-line

comment:24 Changed 5 years ago by vdelecroix

  • Description modified (diff)

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

Replying to ncohen:

I also sorted out all other comments except comment:20. If I set stderr or stdout to something else than PIPE then I am not able to get the result of the command back when doing process.communicate().

God. I had not noticed that you were reading the result from the output :-D

With the code from [1] you can do whatever you want with the output:

Thoug, I do not find it very usable in the current context.

comment:26 in reply to: ↑ 25 ; follow-up: Changed 5 years ago by ncohen

Thoug, I do not find it very usable in the current context.

What's the problem?

comment:27 in reply to: ↑ 26 Changed 5 years ago by vdelecroix

Replying to ncohen:

Thoug, I do not find it very usable in the current context.

What's the problem?

The Ehrhart polynomial appears on stdout (it is not the last line but the one before). While most of the information about the computation appears on stderr. I do not see how to achieve what you suggests in less then 10 unreadable lines. But feel free to have a try on top of commit b877932.

comment:28 follow-up: Changed 5 years ago by ncohen

Then why don't you just let stderr be printed to the screen and only intercept stdout ?

Nathann

comment:29 Changed 5 years ago by git

  • Commit changed from b877932445212ddfd72fd70079c53f17df6d5fd9 to 1ee5281fcc157a083bcdca71106562b056fcd27d

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

1ee5281Trac 18211: much better `verbose` handling!

comment:30 in reply to: ↑ 28 Changed 5 years ago by vdelecroix

Replying to ncohen:

Then why don't you just let stderr be printed to the screen and only intercept stdout ?

right right right! see last commit! Thanks.

comment:31 Changed 5 years ago by ncohen

Hello !

There was still a (very unimportant) problem when verbose=True and the process returns with an error. In this case the exception displays an (empty) variable err.

I fixed this nonexisting problem at public/18211, though I have not been able to make the process return with an error. Even when I changed "--cdd" with "--crghalruhaldd" it returned 'normaly' :-P

Nathann

comment:32 Changed 5 years ago by ncohen

P.S. : you probably got a 10000x speedup with the replacement in Birkhoff_polytope :-P

comment:33 Changed 5 years ago by ncohen

(just added another commits with 'seealsos')

comment:34 follow-up: Changed 5 years ago by vdelecroix

I do not want your SEEALSO here. Could we postpone it to #18213?

comment:35 in reply to: ↑ 34 ; follow-up: Changed 5 years ago by ncohen

I do not want your SEEALSO here.

O_o

Sorry?

comment:36 in reply to: ↑ 35 ; follow-up: Changed 5 years ago by vdelecroix

Replying to ncohen:

I do not want your SEEALSO here.

O_o

Sorry?

By "here" I meant "in this ticket". Your commit is likely to create a conflict with #18213. It would be easier to move your changes on top of #18213.

comment:37 in reply to: ↑ 36 ; follow-up: Changed 5 years ago by ncohen

By "here" I meant "in this ticket". Your commit is likely to create a conflict with #18213. It would be easier to move your changes on top of #18213.

Oh. Well, yeah no problem: just cherry-pick it on the top of your other branch if it is easier.

Nathann

comment:38 Changed 5 years ago by git

  • Commit changed from 1ee5281fcc157a083bcdca71106562b056fcd27d to 930791639042e46c339ba40720456d73dcad1d1b

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

a9ce461trac #18211: print stderr when verbose=False
9307916Trac 18211: "in in" -> "in"

comment:39 Changed 5 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

comment:40 in reply to: ↑ 37 Changed 5 years ago by vdelecroix

Replying to ncohen:

By "here" I meant "in this ticket". Your commit is likely to create a conflict with #18213. It would be easier to move your changes on top of #18213.

Oh. Well, yeah no problem: just cherry-pick it on the top of your other branch if it is easier.

done!

comment:41 Changed 5 years ago by vdelecroix

  • Reviewers changed from Nathann Cohen to Matthias Köppe, Nathann Cohen

Thanks for the review! (I added Matthias to the reviewer list too)

comment:42 Changed 5 years ago by mkoeppe

This looks great, thanks a lot for your work.

There are, however, quite a few more LattE options that are useful, at least for expert users. Below I list the ones (this is cut and paste from "count --help") that make sense for the "--ehrhart-polynomial" mode.

  --compute-vertex-cones={cdd,lrs,4ti2}    Use this method for computing vertex cones
  --smith-form={ilio,lidia}
  --dualization={cdd,4ti2}
  --triangulation={cddlib,4ti2,topcom,...}
  --triangulation-max-height=HEIGHT        Use a uniform distribution of height from 1 to HEIGHT.

comment:43 Changed 5 years ago by vdelecroix

  • Status changed from positive_review to needs_work

will add it... (sorry Nathann)

comment:44 Changed 5 years ago by git

  • Commit changed from 930791639042e46c339ba40720456d73dcad1d1b to a6d03cd0f21b5c7438ec6b03e82fb6ba7536c414

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

a6d03cdTrac 18211: any option to the command (using **kwds)

comment:45 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

All right, you can now send whatever option you like to count even if its not documented!

comment:46 Changed 5 years ago by ncohen

But now you really have a problem with the error code returned by 'count'

sage: P.ehrhart_polynomial(argaerh=3)
...
IndexError: list index out of range

comment:47 follow-up: Changed 5 years ago by mkoeppe

And also now there is no tab completion for the known keyword arguments any more, which is inconvenient

comment:48 Changed 5 years ago by git

  • Commit changed from a6d03cd0f21b5c7438ec6b03e82fb6ba7536c414 to c935177688734f81eec5dd96a1d85c76e7239df6

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

c935177Trac 18211: handle bad output from count

comment:49 Changed 5 years ago by git

  • Commit changed from c935177688734f81eec5dd96a1d85c76e7239df6 to 3c075b2a87ad5690faf548e021900b70a2873cea

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

3c075b2Trac 18211: write explicitely the options in function declaration

comment:50 in reply to: ↑ 47 ; follow-up: Changed 5 years ago by vdelecroix

Replying to mkoeppe:

And also now there is no tab completion for the known keyword arguments any more, which is inconvenient

corrected in 3c075b2

comment:51 Changed 5 years ago by git

  • Commit changed from 3c075b2a87ad5690faf548e021900b70a2873cea to 70e70d8cb73405ca0de84cbdfe3731785ae9a994

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

70e70d8Trac 18211: write explicitely the options in function declaration

comment:52 Changed 5 years ago by git

  • Commit changed from 70e70d8cb73405ca0de84cbdfe3731785ae9a994 to 7215956eea81f8750a96184ca1f16173ef27c334

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

7215956Trac 18211: write explicitely the options in function declaration

comment:53 in reply to: ↑ 50 Changed 5 years ago by vdelecroix

Replying to vdelecroix:

Replying to mkoeppe:

And also now there is no tab completion for the known keyword arguments any more, which is inconvenient

corrected in 3c075b2

Much better with 7215956

comment:54 Changed 5 years ago by ncohen

I added a commit at public/18211. If it's fine for you, you can change the status.

Nathann

comment:55 Changed 5 years ago by ncohen

About the error message: instead of the dictionary it prints the actual command. It may help debug things a bit better than the dictionary, in particular with the '_' -> '-' replacement.

comment:56 Changed 5 years ago by git

  • Commit changed from 7215956eea81f8750a96184ca1f16173ef27c334 to 74ef0f1721a9f73dacf442d29c45acc7a18a1ff6

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

74ef0f1trac #18211: Nothing important

comment:57 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Nice! Thanks!

comment:58 follow-up: Changed 5 years ago by mkoeppe

Has the question of ZZ vs. QQ been resolved?

Perhaps more examples should be added that make uses of some of LattE's options. For example, an Ehrhart polynomial of a cross-polytope, which benefits from irrational_all_primal.

comment:59 in reply to: ↑ 58 Changed 5 years ago by vdelecroix

Replying to mkoeppe:

Has the question of ZZ vs. QQ been resolved?

Actually, in the current state there is not much to do about this. The method self.cdd_Hrepresentation is only available for polytopes defined over ZZ.

Perhaps more examples should be added that make uses of some of LattE's options. For example, an Ehrhart polynomial of a cross-polytope, which benefits from irrational_all_primal.

That would be good indeed. You can propose a commit on top of what I did on the ticket #18213.

Vincent

comment:60 follow-up: Changed 5 years ago by mkoeppe

In the doctests, is it wise to hard-code the version number of LattE? Looks like this could cause trouble whenever the package is updated?

            sage: p = P.ehrhart_polynomial(irrational_primal=True, verbose=True)   # optional - latte_int
            This is LattE integrale 1.7.2
            ...
            Invocation: count --ehrhart-polynomial '--redundancy-check=none' --irrational-primal --cdd ...
            ...
            sage: p   # optional - latte_int
            1/2*t^2 + 3/2*t + 1

comment:61 in reply to: ↑ 60 Changed 5 years ago by vdelecroix

Replying to mkoeppe:

In the doctests, is it wise to hard-code the version number of LattE? Looks like this could cause trouble whenever the package is updated?

I hope that in the next version of LattE we will have a better return code than 0 in case of errors. So anyway, this code will be partly rewritten. The code is very much adapted to the current LattE, so it is good that when the package will be updated, people take care of this.

comment:62 follow-up: Changed 5 years ago by mkoeppe

I see... The return code 0 on errors is a regression in LattE's count, introduced in a recent version. I was not aware of this.

We'll fix this in the next release of LattE.

Last edited 5 years ago by mkoeppe (previous) (diff)

comment:63 in reply to: ↑ 62 Changed 5 years ago by vdelecroix

Replying to mkoeppe:

I see... The return code 0 on errors is a regression in LattE's count, introduced in a recent version. I was not aware of this.

We'll fix this in the next release of LattE.

Nice!

comment:64 follow-up: Changed 5 years ago by kcrisman

Does this then replicate some of the functionality of polymake? (I'm never quite sure of the relationship between the two programs.)

comment:65 Changed 5 years ago by vdelecroix

  • Description modified (diff)

comment:66 in reply to: ↑ 64 Changed 5 years ago by mkoeppe

Replying to kcrisman:

Does this then replicate some of the functionality of polymake? (I'm never quite sure of the relationship between the two programs.)

Just like Sage, polymake interfaces with many libraries and programs. polymake does have a LattE interface for a subset of LattE's features.

Last edited 5 years ago by mkoeppe (previous) (diff)

comment:67 Changed 5 years ago by vdelecroix

A doctest fails. Am I allowed to correct it?

comment:68 Changed 5 years ago by git

  • Commit changed from 74ef0f1721a9f73dacf442d29c45acc7a18a1ff6 to d09d8a53a3b1a0c9661e3be4485c2d3ca1c0c148
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

d09d8a5Trac 18211: forgot a # optional in the doctest

comment:69 Changed 5 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:70 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/18211 to d09d8a53a3b1a0c9661e3be4485c2d3ca1c0c148
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:71 Changed 4 years ago by kcrisman

  • Commit d09d8a53a3b1a0c9661e3be4485c2d3ca1c0c148 deleted
  • Reviewers changed from Matthias Köppe, Nathann Cohen to Matthias Koeppe, Nathann Cohen
Note: See TracTickets for help on using tickets.