Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleParallel Gaussian Elimination for Gröbner bases computations in finite fields
Author(s) Jean-Charles Faugère, Sylvain Lachartre
TypeBook, Chapter in Book, Conference Proceeding
AbstractPolynomial system solving is one of the important area of Computer
Algebra with many applications in Robotics, Cryptology, Computational
Geometry, etc. To this end computing a Gröbner basis
is often a crucial step. The most efficient algorithms [6, 7] for
computing Gröbner bases [2] rely heavily on linear algebra techniques.
In this paper, we present a new linear algebra package for
computing Gaussian elimination of Gröbner bases matrices. The
library is written in C and contains specific algorithms [11] to compute
Gaussian elimination as well as specific internal representation
of matrices (sparse triangular blocks, sparse rectangular blocks
and hybrid rectangular blocks). The efficiency of the new software
is demonstrated by showing computational results fr well known
benchmarks as well as some crypto-challenges. For instance, for a
medium size problem such as Katsura 15, it takes 849.7 sec on a
PC with 8 cores to compute a DRL Gröbner basis modulo p < 2^16;
this is 88 faster than Magma (V2-16-1).
KeywordsPolynomial systems solving, Gröbner bases, Gaussian Elimination, High Performance Linear Algebra, Cryptography, Multi-core Programming
URL http://www-salsa.lip6.fr/~jcf/Papers/PASCO2010.pdf
SeriesPASCO '10
AddressNew York, NY, USA
Translation No
Refereed Yes
ConferencenamePASCO '10 4th International Workshop on Parallel and Symbolic Computation