Time schedule

To have everything in one place, I want to add the time schedule from the original project proposal to this blog as well:

before 05/21	get detailed insights in relevant existing Sage classes and functions
until 05/31	basic class structure and factory function
until 06/05	resolve LLL ticket
until 06/09	implement Fincke-Pohst
until 06/12	basic lattice invariants
approx. one week of work for exams etc.
until 07/06	compute Voronoi cell
until 07/13	extensive testing of the core algorithms
until 07/20	closest vector
until 07/27	successive minima, special case for 2-dimensional lattices
1 week for optional further algorithms
at least 1 week for additional documentation, testing, and report

Of course, this is just a proposal and there will probably be deviations from this original plan. But at the very least, it's an ordered list of things that will be done during this project.

Posting source code on blogger

As this is a blog about a coding project, it certainly makes sense to have a nice way of posting source code. I just ran into this when trying to format the shell line

sage -b lattices

in the previous post. This might not seem like a very sophisticated thing, but there will probably be longer pieces of (Python) code, eventually, and so I wanted to do it right from the start.

Apparently, there is no built-in syntax highlighting on blogger. But there is SyntaxHighlighter, a very nice client-side syntax highlighting library. Integration on blogger is a little tricky though.

First, I had to switch the theme to a non-dynamic ("simple") theme in order to be able to edit its HTML code. But I prefer the design of this one anyway, and the annoying loading phase with those rotating gears seems to be gone now. Then, in the HTML template (which is actually XML markup with the HTML for the blog page inside it), I included the following after the <title>...</title> tag:

<link href="http://alexgorbatchev.com/pub/sh/current/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js" type="text/javascript">
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPython.js' type='text/javascript'/>
<script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushBash.js' type='text/javascript'/>

And the following goes right before the closing </body> tag:

To actually include highlighted source in the blog, you have to edit the raw HTML of your post and mark it as <pre>, like the following:

<pre class="brush: python">
if x: print y
</pre>

This will render as:

if x: print y

To disable line numbers, add class="brush: python; gutter: false" (see the full list of options).

I'm still not sure how to markup inline code in the text: should I use the font menu and choose Courier (which is more convenient) or go to raw HTML and enter it as <code> (which is semantically correct)? Note that it doesn't even look the same.

Furthermore, I still don't like the way linebreaks and paragraphs are dealt with on blogger, and actually the whole way markup is generated. But after all, I still think it's good to have a hosted, ready-to-be-used blog for such a project and not having to set up (and most of all, maintain) everything yourself.

Code repository

To host the code created during the Lattices project, my mentor Daniel Krenn and I decided to set up a code repository at github. While this is not the "native" way of sharing Sage code (which would be Mercurial patches), it has the following advantages:

• Collaboration is much easier on a shared repository, compared to working with patch files.
• It is easy to compare and restore previous versions of files.
• The whole history is also saved locally (in contrast to SVN, for instance) and commits can be made while being offline, which is nice when being on the road. Might always happen in summer.
• Code can be viewed by others instantly, and even arbitrary people can make suggestions for changes using github pull requests.
• It is good (i.e., necessary) to have a backup even in the case my private backup system should fail.

The repository is set up like this: I started a new Sage code branch using

sage -clone lattices

thereby creating a new source tree in sage/devel/sage-lattices. The root directory of the repository is the root sage directory, although I only added the files I actually changed (plus the copyright notice) to the repository. Otherwise, the Python code alone make up some 200 MB, which would probably too much for github—at least not very nice (and necessary).

To work with the code, all you have to do is create the lattices branch yourself and check out the github repository to your sage root directory. The few existing files I had to change (setup.py and sage/all.py) should be overwritten during checkout, and the new lattice files will be added.

I will add Daniel as a collaborator on github should he ever want to make small changes himself. Others are welcome, too, to contribute code, of course. Eventually, we will submit a regular Mercurial patch to Sage to be reviewed by the community, or maybe even several "on the go", should that make sense.

So far, there's not much code there yet. I just started working on the basic class hierarchy and the Lattice factory function. More to come soon.

Let me know if you have any suggestions.

Project description

There could be Lattice_generic class that derives from the existing FreeModule. It would act as the base for arbitrary R-lattices, where R is a ring in some field K and the lattice is over a K-vector space. Deriving from Lattice there would be a class LatticeZZ that represents general Z-lattices (with integer coefficients). An even more specific class could be Lattice_embedded_in_RR that deals with lattices embeddable in RR^n. This would be the class where most algorithms that are currently planned would be implemented. Lattice_embedded_in_RR would store the base of the lattice as a matrix. If most algorithms deal with special cases for 2-dimensional lattices, it could make sense to introduce another specialization Lattice_embedded_in_RR2 (deriving from Lattice_embedded_in_RR) for speedups.

A factory function Lattice could return an instance of the appropriate concrete class, given either a matrix representation of the base of the lattice, a quadratic form, or an order in an algebraic number field (lattices via the Minkowski map --> geometry of numbers).

To find a "good" base of a lattice, the Lenstra-Lenstra-Lovász (LLL) algorithm can be used. To use it over rational and especially real numbers, Ticket #12051 has to be resolved. There are already quite elaborated ideas on how to do this, so this would be a reasonable first step. Maybe the implementation can even be extended further to deal with real interval arithmetic, too.

To calculate vectors of short length in a lattice, the Fincke-Pohst algorithm can be implemented. It is described in the paper "Improved methods for calculating vectors of short length in a lattice, including a complexity analysis" by U. Fincke and M. Pohst (J. Math. Comp 44, 1985). It can be implemented in two variants, one returning all vectors of a given maximum length, and one generating shortest vectors after another (using Python's yield to create a generator that can be iterated over). There is an existing function qfminim in PARI that implements Fincke-Pohst; depending on benchmarks, it might be used, it will however not be possible to get a generator function out of it, which will require a Python or Cython implementation.

Calculations of lattice invariants (e.g. the discriminant) should be straight-forward. This could be realized in the more general LatticeZZ class. More advanced invariants such as the theta series require Fincke-Pohst to already be implemented.

A core part of the project would be the calculation of the Voronoi cell of a lattice. There are many algorithms that calculate Voronoi decompositions, but few are specifically targeted towards the special structure of lattices. The diamond-cutting algorithm is one of them and would be a reasonable choice for the task (paper "Computing the Voronoi cell of a lattice: the diamond-cutting algorithm" by E. Viterbo and E. Biglieri, IEEE Trans. Information Theory 42, 1996), but other algorithms specifically targeted to special cases could be considered as well. The implementation could use existing functions to deal with half spaces in Sage, possibly also including visualizations of them.

Computing the closest lattice point given a vector in RR^n could be implemented using "brute-force search" in a very first step and for the most general case. A more advanced method can use the Voronoi cell (paper "A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations" by D. Micciancio, P. Voulgaris, Proc. 42nd ACM Symp. Theory of Comput., 2010), an approach that might prove useful for other problems as well. Even more specialized algorithms not using the Voronoi cell could be implemented optionally.

All algorithms (specifically Fincke-Pohst, Voronoi cell, closest lattice point) might benefit from an implementation in Cython. Whether this is necessary will be decided after doing benchmarks with pure-Python implementations.

Further optional extension could deal with lattices over Dedekind domains. Most importantly, this would involve implementing support for working with modules over such domains via pseudo-bases. This would, for example, be useful for ideal arithmetic in quaternion algebras.

Existing occurrences of lattices

As already pointed out by Dmitrii Pasechnik in the comments to the project proposal, one of the first things to do is probably to search for existing occurrences of lattices in Sage.

A bold search for "lattice" in *.py and *.pyx files in sage-5.0b11/sage/sage yields 3,946 matches. Here's what they are about (places with potential overlap with or use for our new Lattice class in bold):

• algebras.quatalg.basis_for_quaternion_lattice: returns a basis for the `\\ZZ`-lattice in a quaternion algebra spanned the given generators. It uses _hnf_pari (which calculates the upper triangular Hermite normal form) of an integer matrix.
• categories.*: "lattice" in the sense of a partially ordered set with unique supremum.
• coding.code_constructions.ToricCode
• combinat.*: poset.
• crypto.lattice.gen_lattice: generates different types of lattice bases of row vectors relevant in cryptography.
• geometry: lattice polytopes, integral points. Using the PALP library.
• group.abelian_gps.abelian_group.subgroup_reduced: find small basis.
• homology.simplicial_complex.lattice_paths: 
• interfaces.r: poset.
• libs.fplll: wrapper for the floating-point LLL implementation in fplll. This library also contains a floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the Block Korkin-Zolotarev (BKZ) reduction algorithm.
• libs.ntl.ntl_mat_ZZ.LLL (and variants): LLL implementation with different precisions (up to arbitrary precision floats).
• libs.pari.gen: period lattices of elliptic curves.
• matrix.matrix_integer_dense: LLL and BKZ functions (using fplll or ntl).
• modular.abvar.*: calculate lattices that define various subgroups etc.
• modular.modsym.ambient.ModularSymbolsAmbient.integral_structure
• modular.quatalg.brandt: orders and ideals in quaternion algebras.
• modular.etaproducts.EtaGroup_class.basis: uses LLL algorithm.
• modules.fg_pid.fgp_module: lattice used in example code.
• modules.free_module.FreeModule_generic_pid.index_in: lattice_index.
• quadratic_forms
• rings.number_field.CyclotomicField._positive_integral_elements_with_trace: enumerate lattice points.
• rings.number_field.order: lattice index.
• rings.number_field.totallyreal_data.hermite_constant: nth Hermite constant.
• rings.number_field.totallyreal_rel.integral_elements_in_box: uses geometry.lattice_polytope.LatticePolytope to find points numerically.
• rings.number_field.enumerate_totallyreal_fields_prim: find a minimal lattice element.
• rings.polynomial_modn_dens.small_roots: uses LLL algorithm.
• rings.qqbar: poset (lattice of algebraic extensions).
• rings.rational_field: example code using period lattice of elliptic curves.
• schemes.elliptic_curves: period lattice of elliptic curves.
• schemes.generic.*: lattice polytopes.

Do you know of any other relevant places where lattices are used in Sage? Any ideas on how any of these pieces of code might benefit from a new Lattice class?

Welcome

Welcome to the blog about the Google Summer of Code project Lattices for Sage.