Symbolic and Exact Linear Algebra

over Rings and Fields

Applications of Computer Algebra

July 23-27, 2021, Virtual, Online


Mark Giesbrecht 1 , email:

Armin Jamshidpey 2 , email:

Éric Schost 1 , email:

1David R. Cheriton School of Computer Science, University of Waterloo

2Institute for Quantum Computing, University of Waterloo

Symbolic and exact linear algebra over various mathematical domains has developed to become a cornerstone of modern computer algebra systems. Over fields, such as finite fields, we now have well developed methods to work with massive systems of sparse linear equations.

Over the ring of integers, there have been many developments with exact integer matrices, canonical forms such as Smith and Hermite, and integer lattices. Polynomial matrices have seen similar developments with respect to order bases and M-Padé approximation.

Algorithmic techniques are less well-developed for matrices over non-commutative rings, such as rings of differential or difference operators. Similarly algorithms for rings with zero divisors and modules over more general commutative rings present many open problems.

All of these are applicable to a wide range of applications of the theory in science and engineering.

The aim of this special session is to gather experts in the area to discuss the recent achievements and potential new directions, in algorithms, mathematics, and implementations/libraries.

Topics of interest include, over a variety of rings and fields:

Linear algebra over non-commutative rings

Lattices and ideals

Sparse matrices

Symbolic eigenvalue problems

Canonical forms

Linear system solving

Integer matrices

Computing null ideals

Applications: to coding theory, cryptography, mathematics


Applications of the Smith massager of a nonsingular integer matrix, Stavros Birmpilis, University of Waterloo

Exact linear algebra over the complex numbers, Fredrik Johansson, Inria and Institut. Math. Bordeaux

Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Vincent Neiger, Univ. Limoges

Null ideals of square matrices over residue class rings of PIDs, Roswitha Rissner, University of Klagenfurt

Fast and Practical Algorithms for Solving Linear Systems over Number Fields, Jayantha Suranimalee, University of Colombo

Efficient verification for polynomial matrix computations , Daniel Roche, US Naval Academy

Frobenius Normal Form: what, why, and how to compute , David Saunders, University of Delaware

Coppersmith’s block Wiedemann method for polynomial problems, Gilles Villard, ENS de Lyon