The Efficient Linear Algebra for Gröbner Basis Computations workshop in Kaiserslautern two weeks ago was a welcome opportunity to finally test out LELA, a library specifically written for linear algebra for Gröbner basis computations including for GF(2). The library implements the “Faugère-Lachartre” algorithm (a similar trick, though less developed, appeared before in PolyBoRi) and uses M4RI for dense parts over GF(2).
So, I ran my benchmark matrices through LELA, discovered a bug in the process, then Bradford returned the favour and discovered a bug in M4RI … Finally, below are the timings. The column PLE is the PLE algorithm as implemented in M4RI, M4RI is the M4RI algorithm as implemented in M4RI, GB is a very naive variant of the algorithm LELA uses and LELA is, well, LELA.
What this table means is that one can expect more than an order of magnitude of speed-up when using LELA – which is dedicated to these computations – instead of M4RI – which does not have the specialised algorithm implemented yet. For very small matrices sometimes M4RI/PLE win, but then not by a large margin. The only row where LELA doesn’t do so good is Mutant, which – btw. – is not an F4 matrix but comes from the MXL2 algorithm. It is possible that LELA’s sparse data structures are not that well equipped to deal with this rather dense matrix.
I am in the process of implementing the algorithm LELA uses in M4RI and will report updated timings here.
As you may know, today is the last day of the wokshop on Efficient Linear Algebra for Gröbner Basis Computations that Christian Eder, Burcin Eröcal, Alexander Dreyer and I organised.
I have to say that I am quite pleased with how the workshop played out. We planned the whole thing to be hands on: people were strongly encouraged to work on projects, i.e., to write code preferably together, in addition to attending talks. Those who attended a Sage Days workshop in the past, will know what workshop format I am referring to. Continue reading “Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations”
Linear algebra plays an important role in modern efficient implementations of Gröbner basis algorithms. Consequently, a number of groups aim at developing linear algebra packages for these computations: we mention the HPAC project, LELA by the Singular team, the FGB package by Jean-Charles Faugère, the M4RI libraries, specialised linear algebra routines in PolyBoRi as well as non-public projects. In this workshop we want to bring researchers interested in this problem and developers of these packages together to discuss and develop solutions. The format of this workshop will be a mixture of talks, coding sprints and design discussions.
Topics will include but are not limited to:
- presentation of existing software packages and solutions for linear algebra suitable for Gröbner basis computations
- presentation of scientific results on linear algebra for Gröbner basis computations
- modular approaches to Gröbner basis computations which allow to swap linear algebra packages
- approaches to parallelization of linear algebra routines on multicore machines, multiple machines and GPUs.
- suitable benchmark and test matrices, ideals and their format.
- Brice Boyer (Grenoble, France)
- Michael Brickenstein (Oberwolfach, Germany)
- Daniel Cabarcas (Darmstadt, Germany)
- Jean-Charles Faugère (Paris, France)
- Bradford Hovinen (Munich, Germany)
- Sylvain Lachartre (Paris, France)
- Emmanuel Thomé (Nancy, France)
The workshop will feature mathematical talks, presentations on software and coding sprints.
There is no registration fee for the workshop. Please email the organizers beforehand if you intend to participate.
It is strongly recommended that participants bring their own laptop for use during the coding sprints.
More information regarding this event is available at http://wiki.lmona.de/events/elagb
CIEM – Castro Urdiales, Spain, 11-13 July 2012, http://scc2012.unican.es/
CALL FOR PAPERS
- Deadline for submission: April 28, 2012
- Notification of acceptance or rejection: May 18, 2012
- Deadline for final version: May 30, 2012
- Deadline for registration: June 12, 2012
- Deadline for special issue JSC: September 30, 2012
SCC 2012 is the third edition of a new series of conferences where research and development in symbolic computation and cryptography may be presented and discussed. It is organized in response to the growing interest in applying and developing methods, techniques, and software tools of symbolic computation for cryptography. The use of Lattice Reduction algorithms in cryptology and the application of Groebner bases in the context of algebraic attacks are typical examples of explored applications. The SCC 2012 conference is co-located with third Workshop on Mathematical Cryptology (WMC 2012, http://wmc2012.unican.es/) , an event also organized by research group Algorithmic Mathematics And Cryptography (AMAC), which will be held on 9-11 July 2012.
Continue reading “Call for Papers: 3nd International Conference on Symbolic Computation and Cryptography”
Slightly redacted announcement for the 2012 Summer School on Tools below.
Following the success of the ECRYPT Workshop on Tools for Cryptanalysis 2010,the ECRYPT II Symmetric Techniques Virtual Lab (SymLab) is pleased to announce the 2012 Summer School on Tools. Covering selected topics in both symmetric and asymmetric cryptography, this summer school will provide a thorough overview of some of the most important cryptographic tools that emerged in recent years. While the summer school is aimed primarily at postgraduate students, attendance is open to all. Continue reading “Summer School on Tools :: Mykonos, Greece :: 28.5 – 1.6.”
Sage has many optional packages, about 50 actually. However, it is not necessarily well known what some of these do. For example, recently William asked me to fix some issue in the optional database_symbolic_data (still needing review btw. hint hint) package which bought it back to my attention. Shortly after, Burcin mentioned to me that he spent considerable time copy’n’pasting some standard ideals from some package to Sage’s input format. Time which he probably wouldn’t have spent if he’d known about the SymbolicData.org database and it’s Sage interface. Here’s in it action: Continue reading “SymbolicData”
Over at the Bristol Cryptography Blog Martijn Stam writes about our “Polly Cracker, Revisted” paper:
We did not discuss the paper in great detail, but Jake did mention one interesting avenue for continued research. Given that this new approach allows one to cast both LWE and approximate GCD in the same framework, can one also capture ring-LWE. If so, this might enable a better comparison of the various fully homomorphic encryption (FHE) schemes out there. The hope expressed by Jake was that this might allow a reduction to standard LWE (for the current batch of ring-LWE schemes), which would boost our confidence in those schemes.
This motivated me to express the Ring-LWE problem in a language of Gröbner bases, here’s what I could come up with so far. Continue reading “Ring-LWE and the GB(N) Problem”