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?

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.

Voronoi cells

Recently, I have implemented the diamond-cutting algorithm to calculate the Voronoi cell of a lattice as described in the paper Computing the Voronoi Cell of a Lattice: The Diamond-Cutting Algorithm by Emanuele Viterbo and Ezio Biglieri.

Basically, it starts with a parallelotope defined by hyperplanes through (and normal to) the halves of the basis vectors (and their negated counterparts). Then it gradually combines basis vectors and cuts off  further half spaces, much like a diamond is cut.

The algorithm considers vectors within a certain distance from the origin. This radius can be specified explicitly to speed things up significantly; if not, a "conservative" safe choice is made.

In the current implementation, I am using Sage's existing Polyhedron class to perform the cutting. It seems reasonably fast.

Emanuele Viterbo was so friendly as to provide his implementation of the algorithm from 1995. Comparing running times, it does not seem like it is worth switching from the Polyhedron class to a custom-tailored version of cutting (i.e. intersecting polyhedrons with half spaces). For example, calculating the Voronoi cell of the following lattice:

2.45 0.00 0.00 0.00 0.00 0.00 
-0.41 2.42 0.00 0.00 0.00 0.00 
-0.41 -0.48 2.37 0.00 0.00 0.00 
-0.41 -0.48 -0.59 2.29 0.00 0.00 
-0.41 -0.48 -0.59 -0.76 2.16 0.00 
-0.41 -0.48 -0.59 -0.76 -1.08 1.87

with ball radius 3 takes 51.4 sec using Emanuele's program but only 13.5 sec with my implementation using Polyhedron on my 2.4 GHz Intel Core 2 Duo Mac. (104 cutting operations are performed in both cases.)

A nice consequence of using the Polyhedron class is that it already provides methods to deal with the resulting Voronoi cell. For example, a representation either by (in)equalities or by vertices/edges/faces can be computed easily.

I had to take special care to deal with non-quadratic basis matrices. To deal with "over-specified" lattices (e.g. redundant basis vectors as in (1,0), (2,0), (0,1)), an LLL-reduction is performed prior to diamond-cutting. (This helps to speed up the algorithm anyway.)

"Non-full" lattices (less basis vectors than dimension of embedded space) are dealt with in a special way, too:

1. To get a quadratic basis matrix, "artificial" basis vectors that represent infinity are added first (they are simply chosen to be longer than any other basis vector);
2. LLL-reduction is performed to get a quadratic basis matrix.
3. After diamond-cutting, all inequalities induced by artificial basis vectors are removed again.

This allows the following:

sage: L = Lattice([[2, 0, 0], [0, 2, 0]])
sage: V = L.voronoi_cell()
sage: V.Hrepresentation()
(An inequality (-1, 0, 0) x + 1 >= 0, An inequality (0, -1, 0) x + 1 >= 0, An inequality (1, 0, 0) x + 1 >= 0, An inequality (0, 1, 0) x + 1 >= 0)

Of course, this is still sort of a workaround—maybe there is a better solution to the problem of non-quadratic basis matrices.

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.

My Eclipse/PyDev/git workflow for Sage

I want to briefly describe how I code for Sage so that others can comment on how to improve the workflow or maybe learn something from it.

For Python (and actually for all programming languages, meanwhile), I've always been using Eclipse as an IDE. With PyDev you get pretty nice Python syntax highlighting, code outlines, and features such as code completion, although I have never used that a lot. PyDev has even added Cython support for .pyx files recently—yeah!

I have added the complete Sage tree (which is located in /Applications/sage/ on my Mac) as an Eclipse project. As recommended and described earlier, I created a new branch ("sandbox") using sage -clone lattices; consequently, I'm working on the files in sage/devel/sage-lattices.

Test-driven development makes much sense in general, and especially when working on Sage:

• Due to the fact that you have to rebuild Sage every time you change something, working completely "interactive" isn't possible.
• You don't want to type the code to "bootstrap" your tests (e.g. creating lattices) every single time you change something.
• Eventually, lots of examples are demanded in the documentation anyway.

This is why I usually add some examples that I want to be working in Python docstrings, then code something, and then run the tests. Running the tests is done by

./sage -bt devel/sage-lattices/sage/lattices/lattice.py

which will rebuild the changed components of Sage (compiling Cython code if necessary) and then run the tests defined in lattice.py. Usually it says "All tests passed!" in the end; otherwise it gives an overview of the test cases (examples) that failed.

To see how the documentation that is generated from docstrings looks like, I sometimes rebuild it. For some strange reasons, the documentation generator (Sphinx) does not always recognize that I changed something in the source files. To avoid having to rebuild the complete reference manual (which takes quite a while) every time, I created a small documentation part that only includes the lattices chapter. This is easily done by adding a folder to doc/en and creating files conf.py, index.rst, and lattices.rst therein. The latter basically contains

Lattices
========

.. automodule:: sage.lattices.lattice
   :members:
   :undoc-members:
   :show-inheritance:

Then, the relevant documentation can be rebuilt using

sage --docbuild lattices html -S -a,-E

(-S passes arguments on to Sphinx, -a,-E erase and recreate everything.)

On a side note: When building the HTML documentation on my Mac, I got a bunch of warnings saying "Incompatible library version: libfontconfig.1.dylib requires version 13.0.0 or later, but libfreetype.6.dylib provides version 10.0.0". It seems that the system-wide version of dvipng that I installed through Fink referenced a library "libfreetype" that was loaded through Sage, but with an insufficiently recent version. I simply resolved this by replacing the libfreetype* files in sage/local/lib with the Fink files from /sw/lib. Now the HTML documentation displays beautiful PNG graphics for LaTeX formulas.

I tried to use the integrated Eclipse/PyDev Python debugger with Sage, but ran into some problems. First, you have to launch Eclipse through the Sage shell, i.e. using

sage -sh
/path/to/eclipse

But then, after selecting sage-python as interpreter, when I tried to run the doctests in debug mode, I still got some weird ImportErrors. I could reproduce them using sage-python alone (leaving Eclipse out) and reported the issue on sage-trac.

Despite test-driven development, sometimes I still want to play around with things in Sage interactively.  To reload my lattice module after having done

from sage.lattices import lattice

at one point, I still have to rebuild everything (using the mentioned sage -bt ... command which tests things as well), and then reload it using

lattice = reload(lattice)

Then I can go on creating lattices, e.g. by

L = lattice.Lattice([[1, 0], [0, 1]])

and experiment with them.

When I am done working on something, I do a git commit to my sage repository using

git commit -am "my commit message"

Using the Eclipse git interface is terribly slow when working on the entire Sage tree (even though only a few files are checked in), so I'm using the terminal for this. Usually I also push commits to the github repository using

git push

immediately.

Usually I have at least three terminal windows open: one entirely for running the doctests, one for handling git, and one for "experiments" in Sage. To finally include a picture on this blog as well, here's how this might look like:

Please let me know if you have any suggestions.

Finally, some useful documentation links:

• Sage Developer's Guide
• Editing and building documentation
• Unit testing for Sage objects

Class structure

The class structure of the upcoming lattice module is now as follows: Lattice_with_basis inherits from FreeModule_submodule_with_basis_pid (with some tweaks as described in my previous post) and is the general class for all lattices with bases. This is what Robert Miller called SubLatticeModule in a rather old discussion about lattices, although it is more general as it does not restrict to ZZ-lattices. Would it make sense to implement a general LatticeModule (in Robert Miller's notion) that does not have a concrete basis? How would such a LatticeModule be constructed and what could it offer?

Inheriting from Lattice_with_basis there is Lattice_ZZ that specializes on lattices with integer coefficients (ZZ-Lattices), probably the most usual form of lattices.

Furthermore, there is the specialization on lattices embeddable in the real vector space, Lattice_ZZ_in_RR (again, a very common form of lattices). The actual type of the vectors in the lattice could still be ZZ^n or QQ^n (not necessarily RR^n). Most of the algorithms implemented in this project will probably lie in this class.

I have already added a few lines of documentation and some examples/doctests.

You can see the current state of the code in the main lattice.py file in the code repository on github.

Preventing FreeModule from coercing to its base_ring

I've been working on the class structure for lattices recently. As described in the project description and already suggested in a previous discussion on lattices in Sage, the generic Lattice class should inherit from FreeModule in some way. In our current approach, lattices will always have a basis, which is why the lattice base class Lattice_with_basis should probably inherit from FreeModule_submodule_with_basis_pid.

However, the issue with this is that, apparently, FreeModule expects the basis to be in the fraction field of the coefficient ring (if not in the coefficient ring itself). (The coefficient ring is called base_ring in FreeModule, which is a little confusing because this is not the ring the basis has to lie in.) For instance, a ZZ-lattice in RR^n would be constructed as (an inherited version of)

FreeModule(ZZ^n, <basis matrix>)

with a real-valued basis matrix, but then the basis matrix would be coerced to a matrix over QQ^n first, discarding the information about the original field that the lattice was embedded in. This is not desired here—we want to keep the original vector space, e.g. keep calculating with floating point numbers in RR.

After playing around with the way FreeModules are constructed, I implemented a small workaround: When calling the inherited constructor from FreeModule_submodule_with_basis_pid, echelonization and checking (whether the basis vectors are actually in the free module) are disabled to keep the basis "as is". Consequently, they have to be converted from their given form (usually lists) to elements of a vector space; this is already done in the factory function Lattice.

Furthermore, the element_class has to be overridden, because it is used in the constructor to convert the basis elements (even when echelonization and checking are disabled). Apparently, even the semi-private member _element_class has to be set because it is used instead of the interface function element_class, e.g., when random_element is called. Nevertheless, the function element_class in free_module has to be used to get the actual element class (the underlying ring being changed though), because it wraps the Element structure around the ring.

Now, the following works with Lattice:

sage: Lattice([[1.0, 0, 0], [0, 1, 0]], ZZ)
Real-embedded integer lattice of degree 3 and rank 2
Basis matrix:
[ 1.00000000000000 0.000000000000000 0.000000000000000]
[0.000000000000000  1.00000000000000 0.000000000000000]

While using FreeModule coerces to rationals:

sage: FreeModule(ZZ, 3).span([[1.0, 0, 0], [0, 1, 0]])
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1 0 0]
[0 1 0]

I know this workaround is not an optimal solution—maybe FreeModule itself should be modified if this behaviour is desired. Please let me know if you have any ideas.

Update: This still doesn't work. I came across an error (a pretty severe one, actually) when running the TestSuite on lattices, namely:

sage: L = Lattice([[i, 0], [0, 1]])
sage: L.zero() + L.an_element()

------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
/Applications/sage/spkg/bin/sage: line 312:  4708 Segmentation fault

So while constructing lattices this way works perfectly, working with their elements does not. It seems elements still rely on L.basis_ring() being their own "parent" to some extent, which is not true e.g. for ZZ-lattices in RR^n. I really don't know whether the whole idea of subclassing from FreeModule this way is what FreeModule was designed for, so I asked on sage-devel.

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.