Wednesday, June 20, 2012

Update on basis coercion, LLL and Fincke-Pohst

As written in a previous post, I tried to prevent FreeModule from coercing its basis vectors to the fraction field of its ambient space, mainly motivated by the fact that I wanted floating-point numbers to remain "inexact" and not being converted to rational numbers. However, the resulting discussion on sage-devel made clear that this is actually desirable and we do want this coercion to happen. This is a pity somehow because it renders some of my code useless, but admittedly, it was a "hack" anyway.

So now Lattice_with_basis inherits from FreeModule_submodule_with_basis_pid without changing much of its behaviour. Only echelonization of the basis matrix is turned off, and the representation (_repr_) is different, of course.

Most of the action happens in Lattice_ZZ_in_RR now: I added code to reduce the given basis using the LLL algorithm. Because of our restriction to QQ (no RR vectors), the patch for Ticket #12051 is already enough. (Nevertheless, I might still add an LLL implementation for RR matrices.) Basis reduction can be disabled by handing reduce_basis=False to the Lattice constructor/factory function.

Furthermore, I added a shortest_vectors method to Lattice_ZZ_in_RR that uses Pari's Fincke-Pohst implementation qfminim to find (a certain number of) short vectors (of a given maximum length). The builtin method gram_matrix in FreeModule is used to get the basis inner product matrix. I might add a generator version as well at a later point.

The lattice discriminant is already implemented by FreeModule using the appropriate Gram matrix as well.

Now I'm starting to work on Voronoi cells based on the diamond-cutting algorithm.

No comments:

Post a Comment