Friday, August 24, 2012

Update on class structure, lattice constructors, plotting

Sorry that I haven't posted to this blog for a while. That doesn't mean that nothing happened in the meanwhile—on the contrary, I got quite a lot done in the last weeks of this Summer of Code.

First of all, I completely redesigned the class structure for lattices in Sage. Accounting for the discussion on sage-devel, a lattice in Sage is now a FreeQuadraticModule_ambient_pid with a given inner product matrix ("Gram matrix") and the "standard" basis [(1, 0, 0, ...), (0, 1, 0, ...), ...]. Additionally, a basis for the embedding of the lattice is stored. When constructing a lattice, either a Gram matrix or an embedded basis can be given, and the respective other property will be calculated (either using Cholesky decomposition or via the standard real inner product).

A lattice can also be constructed using a quadratic form or an order in an algebraic number field. The inner product matrix will be calculated accordingly.

There are only two lattice classes now: Lattice_with_basis is meant to be the base class for all lattices in Sage, while Lattice_ZZ represents lattices with base ring ZZ and integral Gram matrix. Storing the Gram matrix as well and not only the basis has the advantage that some lattices with floating-point basis can still be represented exactly, e.g., the embedding of ZZ[sqrt(2)] as a lattice in the sense of Minkowski's geometry of numbers. LLL reduction is primarily performed on the Gram matrix, and the embedded basis is transformed accordingly.

I also added new ways of creating lattices: random_lattice uses random_matrix to create a random basis of a given dimension and turns it into a ZZ-lattice. special_lattice can be used to create particular "special" named lattices such as the Leech lattice. The list of integrated named lattices is probably not complete, but easily extensible. Again, lattices can be specified using their basis or their Gram matrix.

Finally, 2-dimensional and 3-dimensional lattices can be plotted now. All combinations of basis vectors are plotted as points, and the extensive graphics capabilities of Sage allow to modify the plot further. For instance, the Voronoi cell can easily be added, too:

This graphics was constructed using the following code:

L = special_lattice('SimpleCubic')
graphics = plot_lattice(L)
V = L.voronoi_cell()
graphics += V.plot()
graphics.show(viewer='tachyon')

How do you like it?

Thursday, August 16, 2012

Rebasing to Sage 5.2

As there were some changes to Sage since version 5.0 that also affect my code, I rebased my code from Sage 5.0 to 5.2. That meant installing the latest version, cloning a new branch "lattices", and manually copying over the lattices files and re-doing respective changes to some global files. I retained the 5.0-compatible version as a separate branch, whereas the main branch on github is 5.2-targeted. Of course, it would have been much easier if all of Sage was managed through git, so I'm really looking forward to that happening.

Closest vectors

I haven't written about the latest development yet: closest vectors in lattices. This is done using the algorithm in the paper "A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations" by Daniele Micciancio and Panagiotis Voulgaris. As the title suggests, it uses the Voronoi cell V. The idea is

  1. to deal with the special case where the target vector is in 2V, and
  2. to solve the general problem with polynomially many calls to this special case.
See the paper (esp. Algorithm 1) for the details.

Currently, I am working on polishing up documentation, and maybe we still need to change the class structure a little.