Opened 11 years ago

Closed 11 years ago

#11312 closed enhancement (fixed)

Speed up the computation of the Hilbert basis of a cone

Reported by: vbraun Owned by: mhampton
Priority: major Milestone: sage-4.7.2
Component: geometry Keywords: sd31
Cc: novoselt, zaf Merged in: sage-4.7.2.alpha0
Authors: Volker Braun Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by novoselt)

My first implementation of the Hilbert basis eventually uses PALP to compute the points in the parallelotope spanned by the rays of a simplicial cone. This can be done much faster with just the Smith normal form of the ray matrix.

This makes it easy to compute the points in the semi-open parallelotope, so the actual number of semigroup generators is sometimes less than the PALP version (which computed the integral points in the closure). As a pleasant side effect, arbitrary dimension cones work now as we are no longer limited to PALP's compile-time bounds.

Apply:

  1. trac_11312_speed_up_Hilbert_cone.2.patch

Attachments (2)

trac_11312_speed_up_Hilbert_cone.patch (11.0 KB) - added by vbraun 11 years ago.
Updated patch
trac_11312_speed_up_Hilbert_cone.2.patch (11.1 KB) - added by novoselt 11 years ago.
Two corrections to REST formatting

Download all attachments as: .zip

Change History (18)

comment:1 Changed 11 years ago by vbraun

  • Cc novoselt added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 11 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to needs_work
  • Work issues set to non-full-dimensional errors

The speed-up looks impressive! About 20x on trivial examples (no surprise here since we are avoiding system calls to both cdd and PALP), on a "complicated" 6-d example that I picked the new version worked for 15sec and the old one didn't finish before my patience ran out ;-) Am I right that this speed is partially due to taking into account the special structure of the polytopes in which you are computing integral points?

There are, however, issues with non-full-dimensional cones::

sage: Cone([(1,1), (-1,1)], check=False).Hilbert_basis()
(N(1, 1), N(-1, 1), N(0, 1))
sage: Cone([(1,1,0), (-1,1,0)], check=False).Hilbert_basis()
(N(1, 1, 0), N(-1, 1, 0))

comment:3 Changed 11 years ago by vbraun

I think I'm just implementing the same algorithm as PALP would use to enumerate the points in the parallelotope spanned by the rays, though I'm not sure. Essentially you have to compute the Smith form to enumerate the points, the rest is a simple loop. I'll try to get some more info about Palp's inner workings out of Harald Skarke at the Kreuzer Memorial conference.

And thanks for catching the non-full dimensional cone bug, I should have thought about that but didn't.

comment:4 Changed 11 years ago by vbraun

  • Status changed from needs_work to needs_review

Fixed:

sage: Cone([(1,1), (-1,1)], check=False).Hilbert_basis()
(N(1, 1), N(-1, 1), N(0, 1))
sage: Cone([(1,1,0), (-1,1,0)], check=False).Hilbert_basis()
(N(1, 1, 0), N(-1, 1, 0), N(0, 1, 0))

comment:5 Changed 11 years ago by vbraun

On further thought, I think its better to also remove non-primitive vectors from the semigroup generators. The new version of the patch saves a few generators, which should speed up the Hilbert basis a little bit.

comment:6 Changed 11 years ago by vbraun

New version of the patch breaks out the parallelotope_points() function so it can be reused in #11429

comment:7 Changed 11 years ago by vbraun

  • Work issues non-full-dimensional errors deleted

comment:8 Changed 11 years ago by novoselt

  • Keywords sd31 added
  • Status changed from needs_review to needs_work
  • Work issues set to One long test fails in cone module

comment:9 Changed 11 years ago by novoselt

As the patch has to be adjusted one more time anyway - what do you think about creating some kind of sage.geometry.misc module for "helper functions"? Names and rays normalization functions are also natural candidates to go there. This will reduce the potential for circular imports and clarify the structure. cone.parallelotope_points seems a bit strange ;-)

comment:10 Changed 11 years ago by novoselt

Ah, this particular function is moved to another place in the next patch anyway!

Changed 11 years ago by vbraun

Updated patch

comment:11 Changed 11 years ago by vbraun

  • Status changed from needs_work to needs_review

Good catch! I fixed the offending doctest. Up to the ordering the Hilbert bases before and after the patch are the same, of course.

comment:12 Changed 11 years ago by novoselt

  • Status changed from needs_review to positive_review

All works now!

Changed 11 years ago by novoselt

Two corrections to REST formatting

comment:13 Changed 11 years ago by novoselt

  • Description modified (diff)
  • Work issues One long test fails in cone module deleted

I have made tiny adjustments to the patch to make the documentation compile without warnings, I'll leave it at positive review. (Added one column and replaced a quote with a backward one.)

Volker: subsequent patches may need to be rebased.

comment:14 Changed 11 years ago by zaf

  • Cc zaf added

comment:15 Changed 11 years ago by jdemeyer

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:16 Changed 11 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.