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).
