- Computer Science Laboratory Sorbonne Université - CNRS UMR 7606
Sorbonne Universté
Centre National de la Recherche Scientifique

LIP6 supports the Pink October campaign for breast cancer awareness.

LESNOFF Dimitri

Postdoc at Sorbonne University
Team : PEQUAN
https://lesnoff.perso.lip6.fr
https://lesnoff.perso.lip6.fr

Supervision : Stef GRAILLAT
Co-supervision : BERTHOMIEU Jérémy, MARY Théo

Efficient multiword matrix multiplication algorithm using floating-point arithmetic over finite prime fields

This thesis introduces a novel multiword algorithm for matrix multiplication over prime fields whose elements fit within a machine word — a fundamental operation in computer algebra.

This algorithm is particularly well-suited for computing sequences of matrix products in which one matrix remains invariant, as arises, for instance, in the computation of minimal polynomials using the block Wiedemann algorithm.

This manuscript is accompanied by two implementations, one for CPUs and one for GPUs, available at: https://gitlab.lip6.fr/lesnoff/phdcode

Although existing libraries such as FFLAS-FFPACK leverage floating-point arithmetic and BLAS routines to accelerate modular matrix multiplication, they are limited when the field's characteristic exceeds half the mantissa size of a floating-point word (26 bits in double precision), and they also suffer performance degradation for smaller primes. In practice, only a small fraction of the available bits (e.g., about 20 out of 53 in a double precision floating-point format) can be effectively used to represent field elements.

To overcome this limitation, these libraries rely on a multimodular approach based on the Chinese Remainder Theorem when primes exceed 26 bits, reducing the computation to several matrix products modulo smaller primes.

To go beyond this limitation, this thesis proposes a second approach, which is more efficient than the multimodular method for primes between 26 and approximately 45 bits. It extends the FFLAS-FFPACK approach from primes fitting in half a word to primes that occupy a full machine word, by using a floating-point multiword representation.

Our multiword algorithm operates directly at the matrix level rather than on individual coefficients, which enables efficient parallelism.

Like FFLAS-FFPACK, our method combines high-performance BLAS routines with floating-point modular reduction.

The core idea is to decompose each coefficient as an unevaluated representation in a given radix. The resulting digits form the words for each coefficient of the matrices. Storing each digit in separate matrices makes it possible to leverage the BLAS routines for the multiword algorithm.

This representation allows us to improve memory locality by concatenating these word matrices into a larger matrix, which is crucial for handling thin matrices in the block Wiedemann algorithm.

Moreover, this decomposition can be reused when computing sequences of matrix products in which one operand remains unchanged.

We also optimised memory usage by reusing the output buffer during matrix multiplication, and improved data transfers on GPUs within the block Wiedemann algorithm.

Finally, this thesis provides both a theoretical comparison of the number of required matrix products and an experimental performance comparison between our multiword approach and the Residue Number System (RNS), as used in FFLAS-FFPACK and FLINT.


Phd defence : 09/07/2026

Jury members :

Pascal Giorgi, Professeur à l' Université de Montpellier, LIRMM, [Rapporteur]
Nicolas Brisebarre & Directeur de Recherche & CNRS, LIP, ENS Lyon, [Rapporteur]
Stef Graillat, Professeur à Sorbonne Université, LIP6
Jérémy Berthomieu, Maître de Conférences à Sorbonne Université, LIP6
Théo Mary, Chargé de Recherche au CNRS, LIP6, et Sorbonne Université
Mioara Joldes, Directrice de Recherche & CNRS, LAAS
Clément Pernet, Professeur & Grenoble INP, Université Grenobles Alpes, LJK

Departure date : 10/07/2026

2023-2026 Publications