Modular matrix multiplication on GPU for polynomial system solving - Sorbonne Université
Journal Articles ACM Communications in Computer Algebra Year : 2023

Modular matrix multiplication on GPU for polynomial system solving

Abstract

The bottleneck of the sparse-FGLM algorithm for Gröbner bases change of order is an iterative matrix-tall and skinny matrix product over a finite prime field. Our contribution is twofold. First, we port existing CPU-only algorithms for matrix products over prime fields to GPU architectures, and carry out a performance analysis of our implementation that shows that we can nearly achieve the maximum theoretical throughput of the hardware. Second, existing CPU-only algorithms could not handle primes with more than 26 bits, other than the GMP-based implementation in FLINT; we overcome this limitation by proposing an efficient multiword matrix product algorithm that can deal with primes with at most 35 bits; we benchmarked it on GPU.
Le goulot d'étranglement de l'algorithme FGLM sparse pour le changement d'ordre des bases de Gröbner est un produit matriciel itératif sur un corps premier fini avec matrices fines. Notre contribution est double. Tout d'abord, nous portons sur les architectures GPU les algorithmes CPU existants pour les produits matriciels sur les corps finis, et nous effectuons une analyse des performances de notre implémentation qui montre que nous pouvons presque atteindre le débit théorique maximal du matériel. En second lieu, les algorithmes existants uniquement pour CPU ne pouvaient pas traiter les nombres premiers de plus de 26 bits, à l'exception de l'implémentation basée sur GMP dans FLINT ; nous surmontons cette limitation en proposant un algorithme efficace de produit matriciel multi-mots qui peut traiter les nombres premiers d'au plus 35 bits ; nous l'avons testé sur GPU.
Fichier principal
Vignette du fichier
main.pdf (227.78 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Licence

Dates and versions

hal-04117304 , version 1 (05-06-2023)

Licence

Identifiers

Cite

Jérémy Berthomieu, Stef Graillat, Dimitri Lesnoff, Theo Mary. Modular matrix multiplication on GPU for polynomial system solving. ACM Communications in Computer Algebra, In press, 57 (2), pp.35-38. ⟨10.1145/3614408.3614411⟩. ⟨hal-04117304⟩
234 View
263 Download

Altmetric

Share

More