tag:blogger.com,1999:blog-77973691156511643762023-09-28T14:06:28.193+02:00Lattices in SageGoogle Summer of Code 2012 project by Jan PöschkoJan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-7797369115651164376.post-28990632847618663602012-08-24T00:29:00.002+02:002012-08-24T02:21:45.905+02:00Update on class structure, lattice constructors, plottingSorry 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.<br />
<br />
First of all, I completely redesigned the class structure for lattices in Sage. Accounting for the <a href="https://groups.google.com/forum/?fromgroups=#!searchin/sage-devel/lattice/sage-devel/omE8nI2HFbg/cEf8Y-39tWsJ">discussion on sage-devel</a>, a lattice in Sage is now a <span style="font-family: Courier New, Courier, monospace;">FreeQuadraticModule_ambient_pid</span> 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 <a href="http://en.wikipedia.org/wiki/Cholesky_decomposition">Cholesky decomposition</a> or via the standard real inner product).<br />
<br />
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.<br />
<br />
There are only two lattice classes now: <span style="font-family: Courier New, Courier, monospace;">Lattice_with_basis</span> is meant to be the base class for all lattices in Sage, while <span style="font-family: Courier New, Courier, monospace;">Lattice_ZZ</span> 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.<br />
<br />
I also added new ways of creating lattices: <span style="font-family: Courier New, Courier, monospace;">random_lattice</span> uses random_matrix to create a random basis of a given dimension and turns it into a ZZ-lattice. <span style="font-family: Courier New, Courier, monospace;">special_lattice</span> can be used to create particular "special" named lattices such as the <a href="http://en.wikipedia.org/wiki/Leech_lattice">Leech lattice</a>. The <a href="https://github.com/poeschko/sage/blob/master/devel/sage-lattices/sage/lattices/special_lattices.py">list of integrated named lattices</a> is probably not complete, but easily extensible. Again, lattices can be specified using their basis or their Gram matrix.<br />
<br />
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:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-bWlYH9G6mNg/UDauB3BXuuI/AAAAAAAABCU/oZwW2l8KYSE/s1600/lattice.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="http://3.bp.blogspot.com/-bWlYH9G6mNg/UDauB3BXuuI/AAAAAAAABCU/oZwW2l8KYSE/s320/lattice.png" width="320" /></a></div>
<br />
This graphics was constructed using the following code:<br />
<br />
<pre>L = special_lattice('SimpleCubic')
graphics = plot_lattice(L)
V = L.voronoi_cell()
graphics += V.plot()
graphics.show(viewer='tachyon')</pre>
<br />
How do you like it?Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com4tag:blogger.com,1999:blog-7797369115651164376.post-35934134588114225222012-08-16T21:47:00.000+02:002012-08-16T21:47:26.060+02:00Rebasing to Sage 5.2As 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 <a href="https://github.com/poeschko/sage/tree/sage-5.0">5.0-compatible version as a separate branch</a>, whereas the <a href="https://github.com/poeschko/sage">main branch on github</a> 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 <a href="https://groups.google.com/forum/?fromgroups#!topic/sage-git/TRMb6FTEZMg%5B1-25%5D">that happening</a>.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com13tag:blogger.com,1999:blog-7797369115651164376.post-39415938576707564162012-08-16T18:08:00.000+02:002012-08-16T18:08:43.701+02:00Closest vectorsI haven't written about the latest development yet: closest vectors in lattices. This is done using the algorithm in the paper "<a href="http://www.math.ucdavis.edu/~abasu/papers/voronoi_full.pdf">A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations</a>" by Daniele Micciancio and Panagiotis Voulgaris. As the title suggests, it uses the Voronoi cell <i>V</i>. The idea is<br />
<br />
<ol>
<li>to deal with the special case where the target vector is in 2<i>V</i>, and</li>
<li>to solve the general problem with polynomially many calls to this special case.</li>
</ol>
<div>
See the paper (esp. Algorithm 1) for the details.</div>
<div>
<br /></div>
<div>
Currently, I am working on polishing up documentation, and maybe we still need to change the class structure a little.</div>
Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0tag:blogger.com,1999:blog-7797369115651164376.post-79378283570824221842012-07-08T18:16:00.000+02:002012-07-08T18:17:39.083+02:00Voronoi cellsRecently, I have implemented the diamond-cutting algorithm to calculate the Voronoi cell of a lattice as described in the paper <a href="http://www.ecse.monash.edu.au/staff/eviterbo/papers/itjan96.pdf">Computing the Voronoi Cell of a Lattice: The Diamond-Cutting Algorithm</a> by Emanuele Viterbo and Ezio Biglieri.<br />
<br />
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.<br />
<br />
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.<br />
<br />
In the current implementation, I am using Sage's existing Polyhedron class to perform the cutting. It seems reasonably fast.<br />
<br />
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:<br />
<pre>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
</pre>
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.)<br />
<br />
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.<br />
<br />
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.)<br />
<br />
"Non-full" lattices (less basis vectors than dimension of embedded space) are dealt with in a special way, too:<br />
<ol>
<li><span style="background-color: white;">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);</span></li>
<li><span style="background-color: white;">LLL-reduction is performed to get a quadratic basis matrix.</span></li>
<li><span style="background-color: white;">After diamond-cutting, all inequalities induced by artificial basis vectors are removed again.</span></li>
</ol>
<div>
This allows the following:</div>
<div>
<br /></div>
<div>
<pre class="brush:python;gutter:false">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)</pre>
</div>
<br />
Of course, this is still sort of a workaround—maybe there is a better solution to the problem of non-quadratic basis matrices.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com6tag:blogger.com,1999:blog-7797369115651164376.post-35876647118955743102012-06-20T20:28:00.000+02:002012-06-20T20:28:07.172+02:00Update on basis coercion, LLL and Fincke-PohstAs written in a <a href="http://www.youtube.com/watch?v=sforhbLiwLA">previous post</a>, 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 <a href="https://groups.google.com/forum/?fromgroups#!topic/sage-devel/omE8nI2HFbg">discussion on sage-devel</a> 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.<br />
<br />
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.<br />
<br />
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 <a href="http://trac.sagemath.org/sage_trac/ticket/12051">Ticket #12051</a> 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.<br />
<br />
Furthermore, I added a shortest_vectors method to <span style="background-color: white;">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.</span><br />
<br />
The lattice discriminant is already implemented by FreeModule using the appropriate Gram matrix as well.<br />
<br />
Now I'm starting to work on Voronoi cells based on the <a href="http://www.ecse.monash.edu.au/staff/eviterbo/papers/itjan96.pdf">diamond-cutting algorithm</a>.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0tag:blogger.com,1999:blog-7797369115651164376.post-25760423252363461832012-06-04T11:36:00.000+02:002012-08-16T21:48:20.536+02:00My Eclipse/PyDev/git workflow for SageI want to briefly describe <i>how</i> I code for Sage so that others can comment on how to improve the workflow or maybe learn something from it.<br />
<br />
For Python (and actually for all programming languages, meanwhile), I've always been using <a href="http://www.eclipse.org/">Eclipse</a> as an IDE. With <a href="http://pydev.org/">PyDev</a> 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!<br />
<br />
I have added the complete Sage tree (which is located in /Applications/sage/ on my Mac) as an Eclipse project. As <a href="http://www.sagemath.org/doc/developer/walk_through.html#creating-a-sandbox">recommended</a> and <a href="http://gsoc-sage-lattices.blogspot.co.at/2012/05/code-repository.html">described earlier</a>, I created a new branch ("sandbox") using sage -clone lattices; consequently, I'm working on the files in sage/devel/sage-lattices.<br />
<br />
<a href="http://en.wikipedia.org/wiki/Test-driven_development">Test-driven development</a> makes much sense in general, and especially when working on Sage:<br />
<ul>
<li>Due to the fact that you have to rebuild Sage every time you change something, working completely "interactive" isn't possible.</li>
<li>You don't want to type the code to "bootstrap" your tests (e.g. creating lattices) every single time you change something.</li>
<li>Eventually, lots of examples are demanded in the documentation anyway.</li>
</ul>
<div>
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</div>
<pre class="brush: shell; gutter: false">./sage -bt devel/sage-lattices/sage/lattices/lattice.py</pre>
<div>
which will rebuild the changed components of Sage (compiling Cython code if necessary) and then run the tests defined in <a href="https://github.com/poeschko/sage/blob/master/devel/sage-lattices/sage/lattices/lattice.py">lattice.py</a>. Usually it says "All tests passed!" in the end; otherwise it gives an overview of the test cases (examples) that failed.</div>
<div>
<br /></div>
<div>
To see how the documentation that is generated from docstrings looks like, I sometimes rebuild it. For some strange reasons, the documentation generator (<a href="http://sphinx.pocoo.org/">Sphinx</a>) 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</div>
<pre>Lattices
========
.. automodule:: sage.lattices.lattice
:members:
:undoc-members:
:show-inheritance:
</pre>
Then, the relevant documentation can be rebuilt using<br />
<pre class="brush: shell; gutter: false">sage --docbuild lattices html -S -a,-E</pre>
(-S passes arguments on to Sphinx, -a,-E erase and recreate everything.)<br />
<br />
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 <a href="http://www.finkproject.org/">Fink</a> 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.<br />
<br />
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<br />
<pre class="brush: shell; gutter: false">sage -sh
/path/to/eclipse</pre>
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 <a href="http://trac.sagemath.org/sage_trac/ticket/13083">reported the issue on sage-trac</a>.<br />
<br />
Despite test-driven development, sometimes I still want to play around with things in Sage interactively. To reload my lattice module after having done<br />
<pre class="brush: python; gutter: false">from sage.lattices import lattice</pre>
at one point, I still have to rebuild everything (using the mentioned <code>sage -bt ...</code> command which tests things as well), and then reload it using<br />
<pre class="brush: python; gutter: false">lattice = reload(lattice)</pre>
Then I can go on creating lattices, e.g. by<br />
<pre class="brush: python; gutter: false">L = lattice.Lattice([[1, 0], [0, 1]])</pre>
and experiment with them.<br />
<br />
When I am done working on something, I do a git commit to my sage repository using<br />
<pre class="brush: shell; gutter: false">git commit -am "my commit message"</pre>
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 <a href="https://github.com/poeschko/sage">github repository</a> using<br />
<pre class="brush: shell; gutter: false">git push</pre>
immediately.<br />
<br />
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:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-pLmWvMY7bYo/T8x-XwIMCuI/AAAAAAAABB4/bltgKQ4kh8w/s1600/screen.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="250" src="http://2.bp.blogspot.com/-pLmWvMY7bYo/T8x-XwIMCuI/AAAAAAAABB4/bltgKQ4kh8w/s400/screen.gif" width="400" /></a></div>
<br />
Please let me know if you have any suggestions.<br />
<br />
Finally, some useful documentation links:<br />
<ul>
<li><a href="http://www.sagemath.org/doc/developer/index.html">Sage Developer's Guide</a></li>
<li><a href="http://www.sagemath.org/doc/developer/sage_manuals.html#building">Editing and building documentation</a></li>
<li><a href="http://www.sagemath.org/doc/reference/sage/misc/sage_unittest.html">Unit testing for Sage objects</a></li>
</ul>Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com52tag:blogger.com,1999:blog-7797369115651164376.post-43694631450668019092012-06-04T01:08:00.001+02:002012-06-04T01:08:20.410+02:00Class structureThe 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 <a href="http://gsoc-sage-lattices.blogspot.co.at/2012/06/preventing-freemodule-from-coercing-to.html">my previous post</a>) and is the general class for all lattices with bases. This is what Robert Miller called SubLatticeModule in a rather old <a href="https://groups.google.com/forum/?fromgroups#!topic/sage-devel/OO0ADcuraqE">discussion about lattices</a>, 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?<br />
<br />
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.<br />
<br />
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.<br />
<br />
I have already added a few lines of documentation and some examples/doctests.<br />
<br />
You can see the current state of the code in the main <a href="https://github.com/poeschko/sage/blob/master/devel/sage-lattices/sage/lattices/lattice.py">lattice.py file</a> in the <a href="https://github.com/poeschko/sage">code repository on github</a>.<br />Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0tag:blogger.com,1999:blog-7797369115651164376.post-30136262500858442502012-06-04T00:47:00.002+02:002012-06-05T10:05:04.589+02:00Preventing FreeModule from coercing to its base_ringI've been working on the class structure for lattices recently. As described in the project description and already suggested in <a href="https://groups.google.com/forum/?fromgroups#!topic/sage-devel/OO0ADcuraqE">a previous discussion on lattices in Sage</a>, 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.<br />
<br />
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)<br />
<pre class="brush:python;gutter:false">FreeModule(ZZ^n, <basis matrix>)</pre>
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
Now, the following works with Lattice:<br />
<pre class="brush:python;gutter:false">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]
</pre>
<div class="p1">
While using FreeModule coerces to rationals:</div>
<pre class="brush:python;gutter:false">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]
</pre>
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.<br />
<br />
<b>Update</b>: This still doesn't work. I came across an error (a pretty severe one, actually) when running the TestSuite on lattices, namely:<br />
<pre class="brush:python;gutter:false">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</pre>
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 <a href="https://groups.google.com/forum/?fromgroups#!topic/sage-devel/omE8nI2HFbg">asked on sage-devel</a>.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0tag:blogger.com,1999:blog-7797369115651164376.post-10771885830225692692012-05-27T14:31:00.001+02:002012-05-27T14:31:21.138+02:00Time scheduleTo have everything in one place, I want to add the time schedule from the original project proposal to this blog as well:
<br />
<br />
<table>
<tbody>
<tr><td>before 05/21</td><td>get detailed insights in relevant existing Sage classes and functions</td></tr>
<tr><td>until 05/31</td><td>basic class structure and factory function</td></tr>
<tr><td>until 06/05</td><td>resolve LLL ticket</td></tr>
<tr><td>until 06/09</td><td>implement Fincke-Pohst</td></tr>
<tr><td>until 06/12</td><td>basic lattice invariants</td></tr>
<tr><td colspan="2">approx. one week of work for exams etc.</td></tr>
<tr><td>until 07/06</td><td>compute Voronoi cell</td></tr>
<tr><td>until 07/13</td><td>extensive testing of the core algorithms</td></tr>
<tr><td>until 07/20</td><td>closest vector</td></tr>
<tr><td>until 07/27</td><td>successive minima, special case for 2-dimensional lattices</td></tr>
<tr><td colspan="2">1 week for optional further algorithms</td></tr>
<tr><td colspan="2">at least 1 week for additional documentation, testing, and report</td></tr>
</tbody></table>
<br /><div>
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.</div>Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0tag:blogger.com,1999:blog-7797369115651164376.post-58936128292889796312012-05-27T14:15:00.001+02:002012-05-27T14:15:24.149+02:00Posting source code on bloggerAs 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
<br />
<pre class="brush: shell; gutter: false">sage -b lattices
</pre>
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.<br />
<br />
Apparently, there is no built-in syntax highlighting on blogger. But there is <a href="http://alexgorbatchev.com/SyntaxHighlighter/">SyntaxHighlighter</a>, a very nice client-side syntax highlighting library. Integration on blogger is a little tricky though.<br />
<br />
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 <span style="font-family: 'Courier New', Courier, monospace;"><title>...</title></span> tag:<br />
<pre class="brush: xml"><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'/>
</pre>
And the following goes right before the closing <span style="font-family: 'Courier New', Courier, monospace;"></body></span> tag:<br />
<pre class="brush: xml"><script type="text/javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.all();
</script>
</pre>
To actually include highlighted source in the blog, you have to edit the raw HTML of your post and mark it as <span style="font-family: 'Courier New', Courier, monospace;"><pre></span>, like the following:<br />
<pre class="brush: xml"><pre class="brush: python">
if x: print y
</pre>
</pre>
This will render as:
<br />
<pre class="brush: python">if x: print y
</pre>
To disable line numbers, add <code>class="brush: python; gutter: false"</code> (see the <a href="http://alexgorbatchev.com/SyntaxHighlighter/manual/configuration/">full list of options</a>).<br />
<br />
I'm still not sure how to markup inline code in the text: should I use the font menu and choose <span style="font-family: 'Courier New', Courier, monospace;">Courier</span> (which is more convenient) or go to raw HTML and enter it as <code><code></code> (which is semantically correct)? Note that it doesn't even look the same.<br />
<br />
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.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com4tag:blogger.com,1999:blog-7797369115651164376.post-30775869712952117122012-05-27T13:40:00.002+02:002012-06-04T02:26:16.820+02:00Code repositoryTo host the code created during the Lattices project, my mentor Daniel Krenn and I decided to set up a <a href="https://github.com/poeschko/sage">code repository at github</a>. While this is not the "native" way of sharing Sage code (which would be <a href="http://www.sagemath.org/doc/developer/producing_patches.html">Mercurial patches</a>), it has the following advantages:<br />
<ul>
<li>Collaboration is much easier on a shared repository, compared to working with patch files.</li>
<li>It is easy to compare and restore previous versions of files.</li>
<li>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.</li>
<li>Code can be viewed by others instantly, and even arbitrary people can make suggestions for changes using github pull requests.</li>
<li>It is good (i.e., necessary) to have a backup even in the case my private backup system should fail.</li>
</ul>
<div>
The repository is set up like this: I started a new Sage code branch using</div>
<pre class="brush: shell; gutter: false">sage -clone lattices</pre>
<div>
thereby creating a new source tree in <span style="font-family: 'Courier New', Courier, monospace;">sage/devel/sage-lattices</span>. 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).<br />
<br />
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 (<span style="font-family: 'Courier New', Courier, monospace;">setup.py</span> and <span style="font-family: 'Courier New', Courier, monospace;">sage/all.py</span>) should be overwritten during checkout, and the new lattice files will be added.<br />
<br />
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.<br />
<br />
So far, there's not much code there yet. I just started working on the basic class hierarchy and the <span style="font-family: 'Courier New', Courier, monospace;">Lattice</span> factory function. More to come soon.<br />
<br />
Let me know if you have any suggestions.</div>Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com2tag:blogger.com,1999:blog-7797369115651164376.post-77276730446807028022012-05-26T03:39:00.000+02:002012-05-26T03:39:02.732+02:00Project descriptionThere could be <code>Lattice_generic</code> class that derives from the existing <code>FreeModule</code>. It would act as the base for arbitrary <em>R</em>-lattices, where <em>R</em> is a ring in some field <em>K</em> and the lattice is over a <em>K</em>-vector space. Deriving from Lattice there would be a class <code>LatticeZZ</code> that represents general Z-lattices (with integer coefficients). An even more specific class could be <code>Lattice_embedded_in_RR</code> that deals with lattices embeddable in <code>RR^n</code>. This would be the class where most algorithms that are currently planned would be implemented. <code>Lattice_embedded_in_RR</code> 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 <code>Lattice_embedded_in_RR2</code> (deriving from <code>Lattice_embedded_in_RR</code>) for speedups.<br />
<br />
A factory function <code>Lattice</code> 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).<br />
<br />
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, <a href="http://trac.sagemath.org/sage_trac/ticket/12051">Ticket #12051</a> 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.<br />
<br />
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 (<em>J. Math. Comp</em> 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 <a href="http://pari.math.u-bordeaux.fr/dochtml/html.stable/Vectors,_matrices,_linear_algebra_and_sets.html#qfminim"><code>qfminim</code> in PARI</a> 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.<br />
<br />
Calculations of lattice invariants (e.g. the discriminant) should be straight-forward. This could be realized in the more general <code>LatticeZZ</code> class. More advanced invariants such as the theta series require Fincke-Pohst to already be implemented.<br />
<br />
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, <em>IEEE Trans. Information Theory</em> 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.<br />
<br />
Computing the closest lattice point given a vector in <code>RR^n</code> 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, <em>Proc. 42nd ACM Symp. Theory of Comput.</em>, 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.<br />
<br />
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.<br />
<br />
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.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0tag:blogger.com,1999:blog-7797369115651164376.post-37951436398127509732012-05-09T02:51:00.000+02:002012-05-10T01:12:50.386+02:00Existing occurrences of latticesAs already pointed out by Dmitrii Pasechnik in the comments to the <a href="https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2012/poeschko/1">project proposal</a>, one of the first things to do is probably to search for existing occurrences of lattices in Sage.<br />
<br />
A bold search for "lattice" in <span style="font-family: 'Courier New', Courier, monospace;">*.py</span><span style="font-family: inherit;"> </span>and <span style="font-family: 'Courier New', Courier, monospace;">*.pyx</span> files in <span style="font-family: 'Courier New', Courier, monospace;">sage-5.0b11/sage/sage</span> yields 3,946 matches. Here's what they are about (places with potential overlap with or use for our new Lattice class in <b>bold</b>):<br />
<ul>
<li><b>algebras.quatalg.basis_for_quaternion_lattice</b>: 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.</li>
<li>categories.*: "lattice" in the sense of a partially ordered set with unique supremum.</li>
<li>coding.code_constructions.ToricCode</li>
<li>combinat.*: poset.</li>
<li><b>crypto.lattice.gen_lattice</b>: generates different types of lattice bases of row vectors relevant in cryptography.</li>
<li><b>geometry</b>: lattice polytopes, integral points. Using the <a href="http://hep.itp.tuwien.ac.at/~kreuzer/CY/CYpalp.html">PALP</a> library.</li>
<li><b>group.abelian_gps.abelian_group.subgroup_reduced</b>: find small basis.</li>
<li>homology.simplicial_complex.lattice_paths: </li>
<li>interfaces.r: poset.</li>
<li><b>libs.fplll</b>: wrapper for the floating-point LLL implementation in <a href="http://perso.ens-lyon.fr/xavier.pujol/fplll/">fplll</a>. 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.</li>
<li><b>libs.ntl.ntl_mat_ZZ.LLL</b> (and variants): LLL implementation with different precisions (up to arbitrary precision floats).</li>
<li>libs.pari.gen: period lattices of elliptic curves.</li>
<li><b>matrix.matrix_integer_dense</b>: LLL and BKZ functions (using fplll or ntl).</li>
<li>modular.abvar.*: calculate lattices that define various subgroups etc.</li>
<li>modular.modsym.ambient.ModularSymbolsAmbient.integral_structure</li>
<li>modular.quatalg.brandt: orders and ideals in quaternion algebras.</li>
<li><b>modular.etaproducts.EtaGroup_class.basis</b>: uses LLL algorithm.</li>
<li>modules.fg_pid.fgp_module: lattice used in example code.</li>
<li>modules.free_module.FreeModule_generic_pid.index_in: lattice_index.</li>
<li>quadratic_forms</li>
<li>rings.number_field.CyclotomicField._positive_integral_elements_with_trace: enumerate lattice points.</li>
<li>rings.number_field.order: lattice index.</li>
<li>rings.number_field.totallyreal_data.hermite_constant: nth Hermite constant.</li>
<li>rings.number_field.totallyreal_rel.integral_elements_in_box: uses geometry.lattice_polytope.LatticePolytope to find points numerically.</li>
<li><b>rings.number_field.enumerate_totallyreal_fields_prim</b>: find a minimal lattice element.</li>
<li><b>rings.polynomial_modn_dens.small_roots</b>: uses LLL algorithm.</li>
<li>rings.qqbar: poset (lattice of algebraic extensions).</li>
<li>rings.rational_field: example code using period lattice of elliptic curves.</li>
<li>schemes.elliptic_curves: period lattice of elliptic curves.</li>
<li>schemes.generic.*: lattice polytopes.</li>
</ul>
<div>
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?</div>Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com2tag:blogger.com,1999:blog-7797369115651164376.post-23650178874324612842012-05-07T01:16:00.001+02:002012-05-07T01:16:28.069+02:00WelcomeWelcome to the blog about the Google Summer of Code project <a href="http://www.google-melange.com/gsoc/project/google/gsoc2012/poeschko/15001">Lattices</a> for <a href="http://www.sagemath.org/">Sage</a>.Jan Pöschkohttp://www.blogger.com/profile/13654908322659541350noreply@blogger.com0