Compute Hilbert basis of cone

[vbraun]

The Hilbert basis of a cone is useful for toric geometry since one needs to know the generators of "sigma-dual intersect M". This patch implements not necessarily reduced generators of a cone and the Hilbert basis.

This patch depends on #9918: triangulate point configurations. See tracker bug #9604 for the patch queue/dependencies.

The ray order of cones in doctests is written with for the PPL-based cones in #10140. Although the resulting Hilbert basis is, strictly speaking, correct, the doctests will not pass without #10140.

Apply

• attachment: trac_10023_Hilbert_basis.patch
• attachment: trac_10023_reviewer.patch

CC: @novoselt

Component: geometry

Author: Volker Braun

Reviewer: Andrey Novoseltsev

Merged: sage-4.7.1.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/10023

[novoselt]

comment:2

A couple little picks after glancing at it:

• No date after the last "AUTHORS" entry.
• Cone.generators() seems very confusing to me - I think of cones as generated by their rays. Maybe Cone.lattice_points_generators()? I know, it is quite long, but just lattice_generators or integral_generators are still misleading...

[vbraun]

comment:3

How about Cone.semigroup_generators()? This is closer to the truth :-)

[novoselt]

comment:4

Replying to @vbraun:

How about Cone.semigroup_generators()? This is closer to the truth :-)

Great!

[vbraun]

comment:5

For the trac bot: Depends on #9918

[vbraun]

comment:6

I've added a Hilbert_coefficients(point) method that will expand point into a non-negative integer linear combination of the Hilbert basis.

[novoselt]

comment:7

There are doctest errors according to the buildbot, looks like sorting is changed in the new version.

[novoselt]

Work Issues: doctest failures

[vbraun]

comment:8

For the trac bot:
Depends on #9918, #10233, #10039, #10140.

[vbraun]

Attachment: trac_10023_Hilbert_basis.patch.gz

Fixed doctest ray orders due to #10140

[novoselt]

Reviewer: Andrey Novoseltsev

[novoselt]

Changed work issues from doctest failures to none

[novoselt]

comment:10

Hi Volker, I've formatted the documentation a little and adjusted conversion logic in the semigroup_generators (some conversions were unnecessary and for simplicial cones it was returning a list, rather than tuple).

If all changes look fine, please switch to positive review!

[novoselt]

Attachment: trac_10023_reviewer.patch.gz

Added commit message.

[vbraun]

comment:11

Looks good, thanks!

[jdemeyer]

Merged: sage-4.7.1.alpha2