msolve: A Library for Solving Polynomial Systems
Résumé
We present a new open source C library \texttt{msolve}
dedicated to solving multivariate
polynomial systems of dimension zero through computer algebra methods.
The core algorithmic framework of \texttt{msolve} relies on Gr\"obner bases
and linear algebra based algorithms for polynomial system solving.
It relies on Gr\"obner basis computation w.r.t.\ the degree reverse lexicographical
order, Gr\"obner conversion to a lexicographical Gr\"obner basis
and real solving of univariate
polynomials.
We explain in detail how these three main steps
of the solving process are implemented, how we exploit \texttt{AVX2} instruction
processors and the more general implementation ideas we put into practice
to better exploit the computational capabilities of this algorithmic
framework.
We compare the practical performances of \texttt{msolve} with
leading computer
algebra systems such as \textsc{Magma}, \textsc{Maple},
\textsc{Singular} on a wide range of
systems with finitely many complex solutions, showing that
\texttt{msolve} can tackle systems which were out of reach by the
computer algebra software state-of-the-art.
Domaines
Calcul formel [cs.SC]Origine | Fichiers produits par l'(les) auteur(s) |
---|