Two days ago I wrote about LELA’s implementation of Gaussian elimination for Gröbner basis computations over 
Tag Archives: matrix decomposition
Report: Workshop on Efficient Linear Algebra for Gröbner Basis Computations
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
Rank-profile revealing Gaussian elimination and the CUP matrix decomposition
by Claude-Pierre Jeannerod, Clément Pernet, Arne Storjohann is now available on the archive. I like this paper a lot and we also referenced it in both the M4RI elimination paper and the M4RIE paper so three cheers that it’s now available.
Abstract: Transforming a matrix over a field to echelon form, or decomposing the matrix as a product of structured matrices that reveal the rank profile, is a fundamental building block of computational exact linear algebra. This paper surveys the well known variations of such decompositions and transformations that have been proposed in the literature. We present an algorithm to compute the CUP decomposition of a matrix, adapted from the LSP algorithm of Ibarra, Moran and Hui (1982), and show reductions from the other most common Gaussian elimination based matrix transformations and decompositions to the CUP decomposition. We discuss the advantages of the CUP algorithm over other existing algorithms by studying time and space complexities: the asymptotic time complexity is rank sensitive, and comparing the constants of the leading terms, the algorithms for computing matrix invariants based on the CUP decomposition are always at least as good except in one case. We also show that the CUP algorithm, as well as the computation of other invariants such as transformation to reduced column echelon form using the CUP algorithm, all work in place, allowing for example to compute the inverse of a matrix on the same storage as the input matrix.
Efficient dense Gaussian elimination over the field with two elements
Finally, we finished our paper about Gaussian elimination in the M4RI library.
Abstract: In this work we describe an efficient implementation of a hierarchy of algorithms for Gaussian elimination upon dense matrices over the field with two elements (
The sources of this document are available on bitbucket. But I also compiled a PDF.
Update: arXiv link.
Block-iterative PLE decomposition
I guess one advantage of not finishing a paper that is “done” is that one can (a) change the name of the algorithm over and over again and (b) improve said algorithm. Continue reading
Final Version of my PhD thesis
I passed my PhD defence on Friday. I’ve uploaded the final version of my thesis titled Algorithmic Algebraic Techniques and their Application to Block Cipher Cryptanalysis. Not much changed since the last draft, which I also posted on this blog, except a few typos and errors.
Slides of my talks
I’m giving four talks this week at the ECRYPT Tools for Cryptanalysis 2010 workshop and at the 2nd International Conference on Symbolic Computation and Cryptography (both at Royal Holloway). If you want to come prepared to ask the really tough questions but are too lazy to read the papers, here are the slides:
