Computing Ehrhart polynomials with LattE

[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

[git]

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

​5110cc9

Trac 18211: use LattE to compute the Ehrhart polynomial

[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?

[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

[vbraun]

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

[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

[git]

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

​cf2a10f	Trac 18211: another example using Birkhoff_polytope
​ca8da5a	Trac 18211: fixed spelling LattE integral*e*
​d52053c	Trac 18211: check error + options

[vdelecroix]

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

Vincent

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

[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

[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

[git]

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

​0f5122b

Trac 18211: fix command line arguments

[mkoeppe]

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

[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())

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

[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

[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

[git]

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

​b877932

Trac 18211: fix arguments + doctests + cwd=SAGE_TMP

[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().

[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

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

[ncohen]

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

What's the problem?

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

[ncohen]

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

Nathann

[git]

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

​1ee5281

Trac 18211: much better `verbose` handling!

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

[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

[ncohen]

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

[ncohen]

(just added another commits with 'seealsos')

[vdelecroix]

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

[ncohen]

I do not want your SEEALSO here.

O_o

Sorry?

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

[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

[git]

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

​a9ce461	trac #18211: print stderr when verbose=False
​9307916	Trac 18211: "in in" -> "in"

[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!

[vdelecroix]

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

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

[vdelecroix]

will add it... (sorry Nathann)

[git]

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

​a6d03cd

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

[vdelecroix]

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

[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

[mkoeppe]

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

[git]

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

​c935177

Trac 18211: handle bad output from count

[git]

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

​3c075b2

Trac 18211: write explicitely the options in function declaration

[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

[git]

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

​70e70d8

Trac 18211: write explicitely the options in function declaration

[git]

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

​7215956

Trac 18211: write explicitely the options in function declaration

[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

[ncohen]

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

Nathann

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

[git]

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

​74ef0f1

trac #18211: Nothing important

[vdelecroix]

Nice! Thanks!

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

[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

[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

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

[mkoeppe]

Upstream is not aware of cases of return code 0 on errors. Report

[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!

[kcrisman]

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

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

[vdelecroix]

A doctest fails. Am I allowed to correct it?

[git]

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

​d09d8a5

Trac 18211: forgot a # optional in the doctest