What’s New

Maria Montanucci joins the algebra group

On the 1st of April 2019, Maria Montanucci joined the algebra group in the section for mathematics at DTU Compute as assistant professor. We all wish her welcome!

Maria studied mathematics at the Universitá degli Studi di Perugia in Italy, obtaining her bachelor’s degree cum laude in 2013 and her master’s degree cum laude in 2015. From 2015-2018, she did her PhD under the supervision of Prof. G. Korchmáros at the Università della Basilicata, Italy. After this she was a postdoc at the University of Padua from November 2018 – February 2019, where she worked with Corrado Zanella.

Visit by professor Trygve Johnsen.

Prof. Trygve Johnsen from The Arctic University of Norway will visit the algebra group in the section for mathematics at DTU Compute in the coming three months. He is currently on a sabbatical and fortunately for us, he chose DTU as one of the universities he would like to visit. During his stay, he will primarily work with Peter Beelen and Prasant Singh on Grassmann and Schubert codes.

Research visit by Sven Puchinger

The Algebra group was visited late January 2019 by Sven Puchinger who is a postdoc at TU München. Sven has visited us before, and is also a former colleague of Johan at Ulm University in 2013-2014. Sven has numerous research papers jointly written with Johan and Peter.

During the visit, we mostly discussed Twisted Reed-Solomon codes: these are optimal codes (MDS) which are constructed by slightly “twisting” a Reed-Solomon code by carefully adding a monomial to the evaluation polynomials. We proposed the codes in an ISIT paper in 2017, and in 2018 we derived more properties and proposed them for quantum-computer-resilient cryptography. After Sven’s visit, we now have new observations which we will write down in an upcoming paper.

Sven also gave a very nice talk entitled “On Decoding and Applications of Interleaved Gabidulin Codes”.

New PhD Student: Leonardo Landi

Leonardo Landi, PhD at Algebra Group at DTU

Our new PhD student Leonardo Landi started 1st January 2019! Leonardo holds a Master’s degree from the University of Parma, Italy. His PhD project has the tentative title “Curves and Error-Correction”: the aim is to get a better insight in the structure of algebraic geometry codes constructed using towers of function fields.

Research visit to Perugia

From October 27 til November 1, Peter Beelen visited Prof. Massimo Giulietti and his team at the Università degli Studi di Perugia in Italy. During the visit he finished an article with Maria Montanucci, who visited DTU as a guest PhD in 2017. Directly after the visit, Maria started as a postdoctoral researcher at the University of Padua.

In the joint article certain subfields are described of the new maximal function fields found by Maria and Peter in 2017. Such subfields are of interest, since by a result of Serre, they are maximal as well. The article has been submitted to the journal Finite Fields and Their Applications. A preprint is available here.

FNU-funded PhD starts

Grigory Solomatov PhD student at Algebra Group DTU

On October 15, PhD student Grigory Solomatov joined our team! Grigory did a dual master at NTNU and DTU. In the coming three years, he will work on the decoding of AG-codes. His project is an important part of the FNU-project “Correcting on a Curve”.

Research project in the media

Our research project “Correcting on a Curve”, funded by DFF-FNU, has received attention in the media, more specifically the web-based business newspaper Finans.dk:

Danske forskere vil udvikle verdens hurtigste fejlrettende koder

(The full article is unfortunately behind a paywall)

Our project is also featured by DFF’s web page for funded projects:

https://dff.dk/cases/forskere-skal-udvikle-verdens-hurtigste-fejlrettende-koder-til-digital-kommunikation

Paper on record-breaking decoding accepted

The paper “Improved Power Decoding of Interleaved One-Point Hermitian Codes” was accepted for publication in the journal Designs, Codes and Cryptography, and should appear soon!

Visit by Prof. Mark Giesbrecht

During the first week of September 2018, Professor Mark Giesbrecht visited Johan. Mark is Director of the David R. Cheriton School of Computer Science at the University of Waterloo. His research is in symbolic mathematical computation, both developing the algorithmic and complexity theoretical tools as well as building computer algebra software. He was named ACM Distinguished Scientist in 2013 and received an NSERC Synergy Award in 2003 for work with MapleSoft on Maple.

During his visit, Mark and Johan worked together on computing reduced forms of matrices over Ore polynomial rings, with a focus on \(\mathbb Q[x][\partial; d/dx]\). Ore polynomials are a type of non-commutative polynomials which has applications in such diverse fields as partial differential equations, control theory, and coding theory. Matrices over such polynomials arise e.g. when studying systems of equations in these applications, and reducing the matrices can be used to find small representations of the systems which can reduce later, computationally hard steps. The work is together with Arne Storjohann also at University of Waterloo with whom Johan has worked on this issue earlier.

During his visit, Mark also gave a talk entitled “Algorithms and statistics for additive polynomials”

Abstract:

The additive or linearized polynomials were introduced by Ore in 1933 as an analogy over finite fields to his theory of difference and difference equations over function fields. The additive polynomials over a finite field \(\mathbb{F}_q\), where \(q=p^e\) for some prime \(p\),
are those of the form

$$f = f_0 x + f_1 x^p + f_2 x^{p^2} + … + f_m x^{p^m} \in \mathbb{F}_q[x]$$

They form a non-commutative left-euclidean principal ideal domain under the usual addition and functional composition, and possess a rich structure in both their decomposition structures and root geometries. Additive polynomials have been employed in number theory and algebraic geometry, and applied to constructing error-correcting codes and cryptographic protocols. In this talk we will present fast algorithms for decomposing and factoring additive polynomials, and also for counting the number of decompositions with particular degree sequences.

Algebraically, we show how to reduce the problem of decomposing additive polynomials to decomposing a related associative algebra, the eigenring. We give computationally efficient versions of the Jordan-Holder and Krull-Schmidt theorems in this context to describe all possible factorization. Geometrically, we show how to compute a representation of the Frobenius operator on the space of roots, and how its Jordan form can be used to count the number of decompositions. We also describe an inverse theory, from which we can construct and count the number of additive polynomials with specified factorization patterns.

Some of this is joint work with Joachim von zur Gathen (Bonn) and Konstantin Ziegler (Landshut).

Paper on computing reduced form of polynomial matrices presented

The paper “Computing Popov and Hermite forms of rectangular polynomial matrices” was accepted at the prestigious ISSAC conference  earlier this year, and was recently presented at the conference in New York.

The paper is a collaboration between Johan Rosenkilde from the group,  former postdoc Vincent Neiger,  and former Master’s thesis student Grigory Solomatov. Parts of the results were obtained by Grigory during his Master’s thesis!

The paper concerns the computation of something similar to Gaussian elimination but for matrices with entries which are polynomials (univariate).  These kind of computations were recently improved by Vincent for square matrices, but it was still open how to generalise these results to cover rectangular matrices. There are good reasons why this generalisation is not completely straightforward, and in fact most of Grigory’s thesis work was about shooting down all the obvious ways one could think of doing this.

In the end, we found a very elegant randomized algorithm, which is fast in many cases, and a more sophisticated algorithm which works well in almost all cases. The issue is not completely settled, though, and there are still a spectrum of input for which we believe a slightly faster algorithm should exist. That’s for future work!

The full paper can be found here.