\documentclass[a4paper,english,11pt]{scrartcl}

\usepackage{ifpdf}
\ifpdf
  \pdfoutput=1
\fi

%\usepackage[DIV=9]{typearea}
\KOMAoptions{DIV=12,abstract=true}

%%%%% PAQUETS

% Base
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,amsfonts,amsthm}
\usepackage[usenames,dvipsnames,svgnames,table,hyperref]{xcolor}
\usepackage{eurosym}
\usepackage{listings}
\lstset{
basicstyle=\tiny\ttfamily,
columns=flexible,
breaklines=true
}

% Typographies
\usepackage{microtype}
\usepackage{mathtools}  % Pour mathrlap et compagnie
\usepackage{booktabs}   % De beaux tableaux
\usepackage{array}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}

\usepackage[]{csquotes}
\usepackage{xspace}
%\usepackage{fontawesome}

% Graphiques
%\usepackage{tikz}
%\usepackage{tikz-cd}
%\usetikzlibrary{calc,intersections,angles,quotes}

\usepackage{float}

\usepackage[]{graphicx}

% Divers
\usepackage[]{url}
\usepackage[backgroundcolor=white,linecolor=red]{todonotes}

\usepackage[shortlabels,inline]{enumitem}
\setlist[description]{labelindent=!,labelsep=1em,font=\normalfont\bfseries}

\usepackage{bm}

\usepackage{libertine}  % NOARXIV
\usepackage[libertine,vvarbb]{newtxmath}  % NOARXIV
\setkomafont{sectioning}{\bfseries\rmfamily}
\setkomafont{title}{}

\usepackage[ruled]{caption}      % La légende des boites flottantes
\captionsetup{format=hang,justification=raggedright,font=small,width=.95\textwidth,labelfont=it,labelsep=period}
\usepackage[titles]{tocloft}
\usepackage{setspace}
\setstretch{1.07}
\setdisplayskipstretch{.6}


% Algorithms
\usepackage[]{algpseudocode}
\floatstyle{ruled}
\newfloat{algo}{tp}{lop}
\floatname{algo}{Algorithm}
\setcounter{topnumber}{1}     % Pas plus d'une boite flottante en haut d'une page.
\setcounter{bottomnumber}{1}  % idem mais en bas

% scale texttt
\usepackage[scaled=.75]{beramono}
% PL : Chez moi, \tt, \sf, \bf, etc ne fonctionnent pas.
\def\sf{}    % Il faudrait remplacer par \mathsf mais la syntaxe n'est pas la même
\def\tt{\ttfamily}

\definecolor{darkgoldenrod}{rgb}{0.72, 0.53, 0.04}
\definecolor{amber}{rgb}{1.0, 0.75, 0.0}
\definecolor{mred}{rgb}{.886,.239,.157}
\definecolor{darkblue}{RGB}{63,101,134}
% \usepackage[]{tocstyle}
% \usetocstyle{nopagecolumn}
% \settocstylefeature{pagenumberhook}{\normalfont\itshape\color{darkgoldenrod}}
% \setkomafont{sectionentrypagenumber}{\itshape\color{darkgoldenrod}}

\typearea{10}

\setkomafont{title}{\raggedright\sffamily\bfseries\color{darkblue}}
\setkomafont{title}{\raggedright\sffamily\bfseries\color{darkgoldenrod}}
\addtokomafont{subtitle}{\normalfont\sffamily\raggedright\Large\itshape}
\setkomafont{subject}{\raggedright\Large\sffamily\medls}
\addtokomafont{author}{\raggedright\sffamily\setlength{\tabcolsep}{0pt}}
\setkomafont{pageheadfoot}{\sffamily}
\setkomafont{pagenumber}{\sffamily}

\setkomafont{titlehead}{\sffamily}

%\addtokomafont{section}{\color{darkblue}}
\addtokomafont{section}{\color{darkgoldenrod}}
%\addtokomafont{subsection}{\color{darkblue}}
\addtokomafont{subsection}{\color{darkgoldenrod}}
%\addtokomafont{subsubsection}{\normalfont\itshape\color{darkblue}}
\addtokomafont{subsubsection}{\normalfont\itshape\color{darkgoldenrod}}
%\addtokomafont{paragraph}{\normalfont\itshape\color{darkblue}}
\addtokomafont{paragraph}{\normalfont\itshape\color{darkgoldenrod}}

\ifpdf
  \usepackage[
      linktocpage=true,
      hyperfootnotes=false,
      pdftex,                %
      bookmarks         = true,%     % Signets
      bookmarksnumbered = true,%     % Signets numerotes
      pdfpagemode       = None,%     % Signets/vignettes fermes a l'ouverture
      pdfstartview      = FitH,%     % La page prend toute la largeur
      pdfpagelayout     = SinglePage,% Vue par page
      colorlinks        = true,%     % Liens en couleur
      linkcolor= red, %    % couleur des liens internes
      citecolor         =blue,
      urlcolor          = magenta,%  % Couleur des liens externes
      pdfborder         = {0 0 0}%   % Style de bordure : ici, pas de bordure
      ]{hyperref}%                   % Utilisation de HyperTeX
\else
  \usepackage[
      linktocpage=true,
      hyperfootnotes=false,
      bookmarks         = true,%     % Signets
      bookmarksnumbered = true,%     % Signets numerotes
      pdfpagemode       = None,%     % Signets/vignettes fermes a l'ouverture
      pdfstartview      = FitH,%     % La page prend toute la largeur
      pdfpagelayout     = SinglePage,% Vue par page
      colorlinks        = true,%     % Liens en couleur
      linkcolor= red, %    % couleur des liens internes
      citecolor         =blue,
      urlcolor          = magenta,%  % Couleur des liens externes
      pdfborder         = {0 0 0}%   % Style de bordure : ici, pas de bordure
      ]{hyperref}%                   % Utilisation de HyperTeX
\fi
    
\hypersetup{
linkcolor=blue!60!black,
citecolor=red, %OrangeRed, %Emerald, %OliveGreen,
urlcolor=blue, %BlueViolet %NavyBlue
}
\hypersetup{colorlinks=true}
\usepackage{framed}
%\usepackage{bm}

\usepackage{cleveref}
\graphicspath{{../fwf_anr_2017/etc/}}
\usepackage{tcolorbox}
\tcbuselibrary{skins}

\usepackage{pgfgantt}
\usepackage{pgfplots}
\usetikzlibrary{positioning}
\usetikzlibrary{fit}
\usetikzlibrary{backgrounds}
\usetikzlibrary{calc}
%%SG\usetikzlibrary{shapes,fpu,arrows,arrows.meta,calc,matrix,shapes.geometric,decorations.pathmorphing,intersections,fit,external,backgrounds,spy}
%\usetikzlibrary{mindmap}
%\usetikzlibrary{decorations.text}

%\tikzset{box1/.style={draw=black, thick, rectangle,rounded corners, minimum height=2cm, minimum width=2cm}}
\tikzset{box1/.style={draw=black, thick, rectangle,rounded corners, fill=black!7!white}}
\tikzset{box2/.style={draw=black, thick, rectangle,rounded corners, fill=black!7!white, minimum height=3cm}}
\tikzset{annot/.style={draw=black,thick,rounded corners,anchor=base, fill=red!10!white}}

\newtcolorbox[auto counter]{challenge}[2][]{
colframe=white!40!black,coltext=white!25!black,colback=white
,fonttitle=\bfseries, title=Exercise~\thetcbcounter}

\usepackage{fancyhdr}
\usepackage{verbatim}

\allowdisplaybreaks[4]

\newtheorem{proposition}{Proposition}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{definition}[proposition]{Definition}
\newtheorem{conjecture}[proposition]{Conjecture}
\newtheorem*{question}{Problem}


% \def\mbbone{\mathbf{1}} % ONLYARXIV
\def\mbbone{\mathbb{1}} % NOARXIV

\theoremstyle{definition}
\newtheorem{example}[proposition]{Example}

\theoremstyle{remark}
%\newtheorem{example}[proposition]{Example}
\newtheorem*{remark}{Remark}

\newcommand{\cmment}[1]{}
\newcommand{\mop}[1]{\operatorname{#1}}
\newcommand{\ud}{\mathrm{d}}
\newcommand{\st}{\ \middle|\ }
%\newcommand{\eqdef}{\smash{\ \stackrel{\text{def}}{=}\ }}
\newcommand{\eqdef}{\triangleq}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\bA}{{\mathbb{A}}}
\newcommand{\bE}{{\mathbb{E}}}
\newcommand{\bP}{{\mathbb{P}}}
\newcommand{\bN}{{\mathbb{N}}}
\newcommand{\bC}{{\mathbb{C}}}
\newcommand{\bQ}{{\mathbb{Q}}}
\newcommand{\bR}{{\mathbb{R}}}
\newcommand{\bF}{{\mathbb{F}}}
\newcommand{\bK}{{\mathbb{K}}}
\newcommand{\bS}{{\mathbb{S}}}
\newcommand{\bZ}{{\mathbb{Z}}}
\newcommand{\cL}{{\mathcal{L}}}
\newcommand{\cB}{{\mathcal{B}}}
\newcommand{\cD}{{\mathcal{D}}}
\newcommand{\cY}{{\mathcal{Y}}}
\newcommand{\cT}{{\mathcal{T}}}
\newcommand{\cS}{{\mathcal{S}}}
\newcommand{\cN}{{\mathcal{N}}}
\newcommand{\cO}{{\mathcal{O}}}
\newcommand{\cH}{{\mathcal{H}}}
\newcommand{\cU}{{\mathcal{U}}}

\newcommand{\vol}{\mop{vol}}

\newcommand{\Sqrt}{\mop{Sqrt}}
\newcommand{\Sin}{\mop{Sin}}
\newcommand{\Cos}{\mop{Cos}}

\newcommand{\NJ}{\mop{NJ}}

\newcommand{\Proj}{\ensuremath{\bP^n}}
\newcommand{\intx}[1]{\int_{\mathrlap{#1}}}
\newcommand{\muav}{\mu_{\textrm{av}}}
\newcommand\Fquatre{\textsc{\texorpdfstring{F\textsubscript{4}}{F4}}\xspace}

\def\geq{\geqslant}
\def\leq{\leqslant}

\makeatletter
\def\cqlt{c.ql.t\@ifnextchar{.}{}{.\xspace}}

%\bf and KOMA do not work in jcapco TeX distribution it complains that \bf is an old command if KOMA is active
\DeclareOldFontCommand{\rm}{\normalfont\rmfamily}{\mathrm}
\DeclareOldFontCommand{\sf}{\normalfont\sffamily}{\mathsf}
\DeclareOldFontCommand{\tt}{\normalfont\ttfamily}{\mathtt}
\DeclareOldFontCommand{\bf}{\normalfont\bfseries}{\mathbf}
\DeclareOldFontCommand{\it}{\normalfont\itshape}{\mathit}
\DeclareOldFontCommand{\sl}{\normalfont\slshape}{\@nomath\sl}
\DeclareOldFontCommand{\sc}{\normalfont\scshape}{\@nomath\sc}

\makeatother

%\usepackage[pdftex,hypertexnames=false,hidelinks]{hyperref}


\input{macros.tex}

% \newtheorem{pbm}{Problem}
% \newtheorem{definition}{Definition}
% \newtheorem{theorem}[definition]{Theorem}
% \newtheorem{corollary}[definition]{Corollary}
% \newtheorem{proposition}[definition]{Proposition}
% \newtheorem{lemma}[definition]{Lemma}
% \newtheorem{remark}[definition]{Remark}


\titlehead{\ACRONYM}
\title{How to solve multivariate polynomial systems with {\msolve}?}
\date{}

\usepackage[
%  citestyle=authoryear,
  bibstyle=authoryear,
  citestyle=numeric,
  bibstyle=numeric,
%  dashed=false,
  backend=biber,
  isbn=false,
  doi=false,url=false,
  maxcitenames=50,
  hyperref=true,
  maxbibnames=20,
  firstinits=true
  ]{biblatex}
  \bibliography{biblio}

\usepackage{mathrsfs}

\begin{document}

\maketitle

\tableofcontents

\section{Introduction}

\msolve~is a C library for solving multivariate polynomial systems of equations. 
It relies on computer algebra, a.k.a.\ symbolic computation, algorithms to
compute \emph{algebraic} representations of the solution set from which
many, if not all, informations can be extracted.

Solving polynomial systems with \msolve~is \emph{global} by contrast to
\emph{local} numerical routines. The use of computer algebra methods allow also
the user to bypass classical numerical issues encountered by numerical methods
for polynomial system solving such as those based on numerical homotopy
continuation or semi-definite programming.

\msolve~relies mainly on Gr\"obner bases algorithms (see below for a some basic
definitions and properties). It is highly optimized, uses \texttt{AVX2}
vectorization instructions and multi-threading.

It uses the \href{https://gmplib.org/}{\texttt{GMP}} library (handling
multi-precision integers) and the \href{https://flintlib.org/}{\texttt{FLINT}}
library (handling arithmetics of univariate polynomials).

\msolve~can be downloaded from
\begin{center}
  \url{https://msolve.lip6.fr}
\end{center}
where binaries (for \texttt{x86} processors runing Linux operating systems) and
source files are provided.

\msolve~is designed for $64$ bit architectures, with \texttt{AVX2} instructions. 

\msolve allows you to:
\begin{itemize}
\item isolate all real solutions to polynomial systems with rational
  coefficients and finitely many complex solutions;
\item compute Gr\"obner bases of polynomial systems with coefficients which are
  either rational numbers or in a prime field $\mathbb{Z}/p\mathbb{Z}$ with $p <
  2^{31}$; 
\item compute parametrizations of the solutions of polynomial systems with
  coefficients which are either rational numbers or in a prime field
  $\mathbb{Z}/p\mathbb{Z}$ with $p < 2^{31}$ (assuming that the system has
  finitely many solutions with coordinates in an algebraic closure of the field
  generated by the input coefficients). 
\end{itemize}

\msolve is based on Gr\"obner bases computations. When launching \msolve on 
an input polynomial system (see the file format in~\cref{sec:input}), a Gr\"obner 
basis computation starts and allows \msolve to determine if the number of solutions 
to the system is infinite or finite in an algebraic closure of the base field 
(the complex numbers when the input coefficients are rational numbers).

When the number of solutions is finite, one says that the system (or the ideal 
generated by the input equations) has dimension zero at most. Else it has positive 
dimension. 
\Cref{sec:dim} shows how \msolve behaves when the input system has positive dimension 
or when there is no solution at all in an algebraic closure of the base field (over 
the complex numbers when the input coefficients are rational numbers). 

When the system has dimension at most zero, \msolve can compute the real solutions 
or, as said above, compute a Gr\"obner basis (when the base field is a prime field) 
or compute a parametrization of the solutions. 
\Cref{sec:solvingreals} shows how to use \msolve for solving polynomial 
systems over the reals when they have dimension at most zero. 
\Cref{sec:grobner} shows how to use \msolve for computing 
Gr\"obner bases over prime fields (with some restriction on the bit size of the 
considered prime). \Cref{sec:param} shows how to use \msolve for computing rational 
parametrizations of solutions to polynomial systems which have dimension at most 
zero. Finally, \cref{sec:flags} summarizes some options which can be used rational 
parametrizations of solutions to polynomial systems which have dimension at most 
zero. Finally, \cref{sec:flags} summarizes some options which can be used. 

The \msolve library is described in \cite{msolve} with implementation details on 
the algorithms used therein. All computations performed over the rational numbers 
(e.g. for computing real roots) are based on multi-modular computations with a 
probabilistic stopping criterion. Unless explicitely requested by the user (see the 
\verb+-l+ flag in \cref{sec:flags}), all computations of Gr\"obner bases 
in prime fields use deterministic 
algorithms. Change of order algorithms which are used are deterministic 
when the input ideal is radical.

\section{Input file format}\label{sec:input}

\msolve allows you to solve polynomial systems either with coefficients
which are either rational numbers or in a prime field $\mathbb{Z}/p\mathbb{Z}$
with $p < 2^{31}$. If you aim at solving polynomial systems with coefficients
which are floating point numbers, you can just replace these floating point
numbers with rational numbers. Further, we explain how the input files of
\msolve should be.

Consider the following polynomial system of equations
\[
  \begin{array}{rcl}
    x+2 y+2 z-1 &= &0\\
    x^2+2 y^2+2 z^2-x &= &0\\
    2 x y+2 y z-y &= &0
  \end{array}
\]
in $\Q[x,y,z]$.

In order to solve it with \msolve~one simply produces a file with the following content
\msolveinput{examples/simple_char0.ms}
Hence the structure of input files to \msolve is as follows:
\begin{enumerate}
\item the first line contains the variables of the input system, separated with
  a comma (no comma at end of line); 
\item the second line contains the characteristic of the field over which
  computations are performed; 
\item the next lines contain polynomials, in expanded form, separated by a comma
   and with a line break (no comma or line break for the last one).
\end{enumerate}

In each given polynomial, \msolve expects a single occurrence of each monomial;
if some monomial appears several times (e.g.\ as in \verb#x+2*y+2*z-x#),
the behaviour of \msolve's parser is undefined.

When one wants to solve this system over $\frac{\Z}{65521\Z}$ one just replaces
$0$ by $65521$ in the second line. Note that in the positive characteristic case
the coefficients used should be smaller or equal to $2^{31}-1$.

\msolveinput{examples/simple_char65521.ms}

\section{Computing the dimension}\label{sec:dim}

To make things explicit on the behaviour of \msolve when the input system
does not have finitely many complex solutions, let us consider first the example
below.
\msolveinput{examples/empty_char0.ms}
Then, \msolve outputs
\begin{tcolorbox} % examples/empty_char0.res
  \begin{lstlisting}[basicstyle=\normalsize\ttfamily]
[-1]:
  \end{lstlisting}
\end{tcolorbox}
indicating that the dimension of the set of complex solutions is $-1$, hence it
is empty.

If now, one considers the following example.
\msolveinput{examples/hypersurface_char0.ms}
Then, \msolve outputs
\begin{tcolorbox} % examples/hypersurface_char0.res
  \begin{lstlisting}[basicstyle=\normalsize\ttfamily]
[1, 3, -1, []]:
  \end{lstlisting}
\end{tcolorbox}
The first integer $1$ indicates that the complex solution is positive
dimensional (note that the actual dimension of the complex solution set is $2$).


\section{Solving over the reals (finitely many solutions)}\label{sec:solvingreals}

The basic functionality \msolve allows you to perform is real root
isolation for polynomial systems with rational coefficients and {\em with
  finitely many complex solutions}. This latter requirement is automatically
tested by \msolve. 

For instance, consider the following input to \msolve written in a file
\verb+in.ms+.
\msolveinput{examples/reals_dim0.ms}
Then, typing the following command line
\begin{tcolorbox} % examples/reals_dim0.sh
  \begin{verbatim}
    ./msolve -f in.ms -o out.ms 
  \end{verbatim}
\end{tcolorbox}
will display in the \verb+out.ms+ file the following content. 
\begin{tcolorbox} % examples/reals_dim0.res
  \begin{lstlisting}
[0, [1,
[[[107291359935630315248585097660753910587 / 2^127, 26822839983907578812146274415188477647 / 2^125], [107291359935630315248585097660753910587 / 2^128, 26822839983907578812146274415188477647 / 2^126], [-355532291286331190123863132844989723573 / 2^131, -1422129165145324760495452531379958894291 / 2^133]], [[1, 1], [0, 0], [0, 0]], [[38543940173343311950004019810003894311 / 2^127, 77087880346686623900008039620007788667 / 2^128], [9635985043335827987501004952500973579 / 2^126, 4817992521667913993750502476250486791 / 2^125], [93053303113782607831679264095876317083 / 2^128, 372213212455130431326717056383505268333 / 2^130]], [[7089215977519551322153637654828504405 / 2^124, 113427455640312821154458202477256070491 / 2^128], [-1 / 2^127, 1 / 2^127], [1814839290245005138471331239636097127765 / 2^132, 907419645122502569235665619818048563883 / 2^131]]]
]]:
  \end{lstlisting}
\end{tcolorbox}
This is a list whose first element is the integer $0$ indicating that the input
polynomial system has finitely many complex solutions. The second element of
this list is a list which provides the coordinates of the real solutions as
follows:
\begin{itemize}
\item the first element is an integer $\ell$ indicating how many lists are given
  further; in the above example, the integer $1$ tells that we have a single
  list (this will be the usual case);
\item the next are $\ell$ lists $L_1, \ldots, L_\ell$ which encode the solutions
  to the input system; each of them containing boxes isolating a single real
  solution. 
\end{itemize}
For instance, from the above output, we deduce that the box defined by 
\[
  \left \{
    \begin{array}{l}
      \frac{107291359935630315248585097660753910587}{2^{127}}
      \leq x \leq
      \frac{26822839983907578812146274415188477647}{2^{125}}, \\
      \frac{107291359935630315248585097660753910587}{2^{128}}
      \leq y \leq
      \frac{26822839983907578812146274415188477647}{2^{126}}, \\
      \frac{-355532291286331190123863132844989723573}{2^{131}}
      \leq z \leq
      \frac{-1422129165145324760495452531379958894291}{2^{133}}
\end{array}\right .
\]
contains a single real solution to the input system.

Sometimes, it makes sense to increase the precision. To do that, we use the
\verb+-p+ flag, followed by an integer monitoring the used precision, as
follows.
\begin{tcolorbox} % examples/reals_dim0_prec256.sh
  \begin{verbatim}
    ./msolve -p 256 -f in.ms -o out.ms 
  \end{verbatim}
\end{tcolorbox}
We obtain in \verb+out.ms+ the following
\begin{tcolorbox} % examples/reals_dim0_prec256.res
  \begin{lstlisting}
[0, [1,
[[[36509357909062631536129668436573070012487487067100583303001175658946635606055 / 2^255, 4563669738632828942016208554571633751560935883387572912875146957368329450757 / 2^252], [36509357909062631536129668436573070012487487067100583303001175658946635606055 / 2^256, 4563669738632828942016208554571633751560935883387572912875146957368329450757 / 2^253], [-60490684797868661441895377475208744393359927205523538345094237255746825568573 / 2^258, -483925478382949291535163019801669955146879417644188306760753898045974604548583 / 2^261]], [[1, 1], [0, 0], [0, 0]], [[3278955798161077339921616998930436909728483733114914607048732943254033559905 / 2^253, 26231646385288618719372935991443495277827869864919316856389863546032268479285 / 2^256], [6557911596322154679843233997860873819456967466229829214097465886508067119813 / 2^255, 13115823192644309359686467995721747638913934932459658428194931773016134239637 / 2^256], [63328796466738957984825113025800917297614244935801930326677856915848592681411 / 2^257, 126657592933477915969650226051601834595228489871603860653355713831697185362823 / 2^258]], [[2412335192444087404657728854347664746943124680534178417488699666831523534165 / 2^252, 38597363079105398474523661669562635951089994888546854679819194669304376546651 / 2^256], [-1 / 2^255, 1 / 2^255], [617557809265686375592378586713002175217439918216749674877107114708870024746325 / 2^260, 308778904632843187796189293356501087608719959108374837438553557354435012373163 / 2^259]]]
]]:
  \end{lstlisting}
\end{tcolorbox}


\section{Computing Gr\"obner bases}\label{sec:grobner}

\msolve relies on Gr\"obner bases algorithms which allow one to rewrite the
input polynomial system as an equivalent system which reveals properties of the
solution set (dimension, degree) and to compute ``modulo'' the input equations.

\msolve provides Gr\"obner bases computations for the so-called \emph{grevlex}
ordering (see e.g.~\cite{CLO}) when the coefficients either lie in the field of
rational numbers or when they lie in the prime field case. For instance, assume
the file \verb+in.ms+ contains the following:
\msolveinput{examples/grevlex_char1073741827.ms} Now, typing the following
command:
\begin{tcolorbox} % examples/grevlex_char1073741827.sh
  \begin{verbatim}
    ./msolve -g 2 -f in.ms -o out.ms 
  \end{verbatim}
\end{tcolorbox}
where the \verb+-g+ flag indicates that one aims at computing a Gr\"obner
basis. The value \verb+2+ tells \msolve to compute the Gr\"obner basis for the
\emph{grevlex order} with $z_1\succ z_2 \succ z_3 $. The computed Gr\"obner basis
is then printed in the file \verb+out.ms+ as follows.
\begin{tcolorbox} % examples/grevlex_char1073741827.res
  \begin{lstlisting}
#Reduced Groebner basis data
#---
#field characteristic: 1073741827
#variable order:       z1, z2, z3
#monomial order:       graded reverse lexicographical
#length of basis:      6 elements sorted by increasing leading monomials
#---
[1*z2^2+832149913*z1^1*z3^1+876889156*z3^2+295279002*z1^1+724775733*z2^1+143165573*z3^1,
1*z1^1*z2^1+613566759*z2^1*z3^1+766958448*z3^2+766958448*z1^1+613566759*z3^1+153391691,
1*z1^2+134217730*z1^1*z3^1+268435458*z3^2+671088642*z1^1+671088642*z2^1,
1*z2^1*z3^2+722232944*z3^3+180778379*z1^1*z3^1+1027531442*z2^1*z3^1+173735741*z3^2+936498976*z1^1+702034498*z2^1+921316952*z3^1+59915395,
1*z1^1*z3^2+557357968*z3^3+911535897*z1^1*z3^1+419648179*z2^1*z3^1+96648475*z3^2+698659259*z1^1+282295066*z2^1+885328953*z3^1+769127629,
1*z3^4+250491376*z3^3+716275774*z1^1*z3^1+91652836*z2^1*z3^1+88303466*z3^2+855797860*z1^1+18642214*z2^1+728901227*z3^1+969918485]:
  \end{lstlisting}
\end{tcolorbox}
When one is interested only in the leading monomials of the Gr\"obner basis
(which is a way smaller output), one simply uses the \verb+-g 1+ flag as follows
\begin{tcolorbox} % examples/grevlex_lm_char1073741827.sh
  \begin{verbatim}
    ./msolve -g 1 -f in.ms -o out.ms 
  \end{verbatim}
\end{tcolorbox}
and we obtain:
\begin{tcolorbox} % examples/grevlex_lm_char1073741827.res
  \begin{lstlisting}
#Leading ideal data
#---
#field characteristic: 1073741827
#variable order:       z1, z2, z3
#monomial order:       graded reverse lexicographical
#length of basis:      6 elements sorted by increasing leading monomials
#---
[z2^2,
z1^1*z2^1,
z1^2,
z2^1*z3^2,
z1^1*z3^2,
z3^4]:
  \end{lstlisting}
\end{tcolorbox}
Note that from this list of monomials, one can deduce the Hilbert series of the
ideal generated by the input equations and then its dimension and its degree
(see~\cite{CLO}). 

Note that when the \verb+-g 1+ flag is used in characteristic $0$, the result is
always probabilistic: the leading monomials are deduced from two computations
over a prime field, the first prime being chosen randomly.

For instance, in the above example, one can deduce that the ideal has dimension
$0$ (finitely many solutions with coordinates in an algebraic closure of
$\frac{\mathbb{Z}}{1073741827\mathbb{Z}}$) since the basis of leading monomials
contain pure powers of all variables. The degree of the ideal is also $8$ since
there are $8$ monomials in $z_1, z_2, z_3$ which are not divisible by the above
leading monomials.

\msolve also allows you to perform Gröbner bases computations using 
\emph{one-block elimination monomial order}
thanks to the \verb+-e+ flag. The following command 
\begin{tcolorbox} % examples/elim_char1073741827.sh
  \begin{verbatim}
    ./msolve -e 1 -g 2 -f in.ms -o out.ms
  \end{verbatim}
\end{tcolorbox}
on
\msolveinput{examples/elim_char1073741827.ms}
will perform the Gröbner basis computation eliminating the first
variable.
The output is
\begin{tcolorbox}
  \begin{lstlisting}
#Reduced Groebner basis data
#---
#field characteristic: 1073741827
#variable order:       t, w, x, y, z
#monomial order:       eliminating first variable, blocks: graded reverse lexicographical
#length of basis:      7 elements sorted by increasing leading monomials
#---
[1*w^1*y^3+1073741826*x^1*z^3,
1*x^4,
1*w^1*x^3,
1*w^2*x^2,
1*w^3*x^1,
1*w^4,
1*t^1*z^1+1073741826]:
  \end{lstlisting}
\end{tcolorbox}
where we see that the first $6$ polynomials are only in $w,x,y,z$,
which corresponds to the elimination of the variable $t$. When the input
coefficients lie in the field of rational numbers (hence, characteristic $0$),
the returned Gröbner basis is the one of the {\em elimination ideal}, i.e. they
have partial degree $0$ in the variables to eliminate.

More generally, using \verb+-e k+ will eliminate the $k$ first
variables. Thus
\begin{tcolorbox} % examples/elim2_char1073741827.sh
  \begin{verbatim}
    ./msolve -e 2 -g 2 -f in.ms -o out.ms
  \end{verbatim}
\end{tcolorbox}
will eliminate $t$ and $w$, yielding
\begin{tcolorbox} % examples/elim2_char1073741827.res
  \begin{lstlisting}
#Reduced Groebner basis data
#---
#field characteristic: 1073741827
#variable order:       t, w, x, y, z
#monomial order:       eliminating first 2 variables, blocks: graded reverse lexicographical
#length of basis:      7 elements sorted by increasing leading monomials
#---
[1*x^4,
1*w^1*y^3+1073741826*x^1*z^3,
1*w^1*x^3,
1*t^1*z^1+1073741826,
1*w^2*x^2,
1*w^3*x^1,
1*w^4]:
#Reduced Groebner basis for input in characteristic 1073741827
#for variable order t, w, x, y, z
#w.r.t. grevlex monomial ordering
#consisting of 7 elements:
[1*x^4,
1*w^1*y^3+1073741826*x^1*z^3,
1*w^1*x^3,
1*t^1*z^1+1073741826,
1*w^2*x^2,
1*w^3*x^1,
1*w^4]:
  \end{lstlisting}
\end{tcolorbox}
where we see that only the first polynomial is not in $t$ and $w$.

\section{Parametrizations of (finitely many) solutions}
\label{sec:param}

Assume that the input polynomials have coefficients in some field $\K$ with
variables $x_1, \ldots, x_n$. In the case of polynomial systems of dimension
$0$, \msolve computes by default a zero-dimensional parametrization of the
solution set. The user can obtain such an encoding using the \verb+-P+ flag 
(see below).

Let us recall what a rational parametrization is.
This is a couple $(\mathscr{P}, \ell)$ where $\ell$ is a linear form $\lambda_1
x_1 + \cdots + \lambda_n x_n$ with $\lambda_i\in \K$ (for $1\leq i \leq n$),
$\mathscr{P}$ is a sequence of polynomials $(w, w', v_1, \ldots, v_n)$ in
$\K[t]$ where $t$ is a new variable such that:
\begin{itemize}
\item when $\K$ is a prime field, $w'=1$ else $w' = \frac{\partial w}{\partial
    t}$;
\item $\deg(v_i) < \deg(w)$ for $1\leq i \leq n$;
\item $\lambda_1 v_1 +\cdots +\lambda_n v_n = tw' \mod w$
\end{itemize}
and the solution set to the input polynomials coincides with the set:
\[
\left \{\left (-\frac{v_1(\vartheta)}{w'(\vartheta)}, \ldots,
  -\frac{v_n(\vartheta)}{w'(\vartheta)}\right ) \st w(\vartheta) = 0
\right\}.
\]
In algebraic words, the polynomials \(w' x_i + v_i\) belong to the radical of the 
ideal generated by the input equations and the form \(\lambda_1 x_1 + \cdots +
\lambda_n x_n + t\). 

\msolve outputs univariate polynomials as an array \verb+[deg,L]+ where
\verb+deg+ is the degree of the polynomial under consideration and \verb+L+ is
the array of its coefficients in the monomial basis by increasing degree and 
\verb+c+ is a denominator to all coefficients. For instance, the polynomial 
\(x^2+3x-2\) is encoded by 
\begin{verbatim}
[2, [-2, 3, 1]]
\end{verbatim}


We first explain \msolve's output in the case where the input coefficients are 
rational numbers (the characteristic zero case).
For an input in the file \verb+in.ms+
\msolveinput{examples/param_simple.ms}
the command
\begin{tcolorbox} % examples/param_simple.sh
  \begin{verbatim}
./msolve -P 2 -f in.ms
  \end{verbatim}
\end{tcolorbox}
\msolve outputs is
\begin{tcolorbox} % examples/param_simple.res
  \begin{lstlisting}
[0, [0, 
3, 
4, 
['z1', 'z2', 'A'],
[-119/576,69/576,5/576],
[1,
[[4, [883600, 0, -18922, 0, 25]],
[3, [0, -37844, 0, 100]],
[
[[3, [223720, 0, -1190, 0]],
1],
[[3, [129720, 0, 690, 0]],
1]
]]]]]:
  \end{lstlisting}
\end{tcolorbox}
and
has the following structure
\begin{tcolorbox}
  \begin{lstlisting}
[0, [0, nvars, deg, vars, form, [1,[lw, lwp, param]]]]:
  \end{lstlisting}
\end{tcolorbox}
where
\begin{itemize}
\item the first $0$ indicates that the input system has finitely
  many complex solutions (dimension at most $0$);
\item the second $0$ is the characteristic;
\item \verb+nvars+ is the number of variables used for the parametrization (it
  coincides with the number of input variables if the form $\ell$ is chosen
  as one of the variables else it is one more);
\item \verb+deg+ is the number of solutions, \emph{counted with multiplicities}
  (in other words the degree of the ideal generated by the input equations);
\item \verb+vars+ is the list of variables following the ordering used for
  computing the parametrization (hence, with maybe with one
  more variable than the ones given as input).

  In our example, \msolve outputs:
\begin{verbatim}
['z1', 'z2', 'A']
\end{verbatim}
where \verb+A+ is a new variable. 

\item \texttt{form} is the list of coefficients for the linear form $\ell$ when
  it does not coincide with one of the input variables (else it is an empty list);

  In our example, this is a list of three rational numbers,
  say \verb+[-119/576,69/576,5/576]+, 
  indicating that the linear form used to compute the rational parametrization is 
\begin{verbatim}
-119/576*z1+69/576*z2+5/576*A
\end{verbatim}
\item the next $1$ indicates that a single parametrization is returned next (the one encoded by \verb+[lw, lwp, param]+);
\item \verb+lw+ is the encoding of the eliminating polynomial $w$;
\item \verb+lwp+ is the encoding of the denominator used in the rational
  parametrization;
\item \verb+param+ is the list of the output parametrizations, there are $n-1$ where 
    $n$ is the number of elements in \verb+vars+ ; 
    they are encoded as follows \verb+[[deg, L], c]+ where \verb+c+ is 
    an integer which divides the polynomial encoded by \verb+[deg, L]+. 

    The first one corresponds to the first variable in \verb+vars+, the 
    second parametrization corresponds to the second variable in \verb+vars+ 
    and so on. Hence, the variable which is used to parametrize the solution 
    set is always the last one.
\end{itemize}
We illustrate now how the output looks like on input file \verb+in.ms+
\msolveinput{examples/param_char0.ms}
Using \verb+./msolve -P 2 -f in.ms+ the output is 
\begin{tcolorbox} % examples/param_char0.res
  \begin{lstlisting}
[0, [0, 
3, 
4, 
['z1', 'z2', 'z3'],
[0, 0, 1],
[1,
[[4, [-116, -210, 1484, -344, 53]],
[3, [-210, 2968, -1032, 212]],
[
[[3, [1894, 162, -1636, 192]],
1],
[[3, [-146, -620, -3118, 314]],
1]
]]]]]:
  \end{lstlisting}
\end{tcolorbox}
On this example, all variables are parametrized by the variable \verb+z3+. 

The polynomial $w$ is $-116 - 210 z_3 + 1484 z_3^2 -344 z_3^3 + 53 z_3^4$. 
The polynomials $v_1$ and $v_2$ are respectively 
\[
    v_1 = 1894 + 162 z_3 - 1636 z_3^2 + 192 z_3^3 \quad \text{ and } 
    \quad v_2 = -146 -620 z_3 - 3118 z_3^2 + 314 z_3^3.
\]
Note that we can get both the parametrization and the real roots.
For instance, using the command 
\verb+./msolve -P 1 -f in.ms+, one obtains
\begin{tcolorbox} % example/param_and__reals_char0.res
  \begin{lstlisting}
[0, [0, 
3, 
4, 
['z1', 'z2', 'z3'],
[0, 0, 1],
[1,
[[4, [-116, -210, 1484, -344, 53]],
[3, [-210, 2968, -1032, 212]],
[
[[3, [1894, 162, -1636, 192]],
1],
[[3, [-146, -620, -3118, 314]],
1]
]]]],[1,
[[[679375673646273705027530285330331715009 / 2^128, 339687836823136852513765142665165857505 / 2^127], [-60535166785954698124918883091179878673 / 2^128, -3783447924122168632807430193198742417 / 2^124], [-1162789190151604508343028862486419979779 / 2^132, -581394595075802254171514431243209989889 / 2^131]], [[-756665306660103909967296571629791504137 / 2^128, -756665306660103909967296571629791504135 / 2^128], [88745898258177294078528671940999802399 / 2^126, 177491796516354588157057343881999604799 / 2^127], [2063895933416661444279689618845660247455 / 2^132, 4127791866833322888559379237691320494911 / 2^133]]]
]]:
  \end{lstlisting}
\end{tcolorbox}

We end this section with the same example as above but seeing the coefficients in 
\(\Z/65521\Z\).
\msolveinput{examples/param_char65521.ms}
The call \verb+./msolve -P 2 -f in.ms+ then outputs
\begin{tcolorbox} % examples/param_char65521.res
  \begin{lstlisting}
[0, [65521, 
3, 
4, 
['z1', 'z2', 'z3'],
[0, 0, 1],
[1,
[[4,
[16069, 9886, 28, 2466, 1]],
[0,
[1]],
[
[[3,
[6276, 37054, 57744, 4959]]],
[[3,
[29622, 14235, 36649, 30281]]]
]]]]]:
  \end{lstlisting}
\end{tcolorbox}

\section{Saturation and colon ideals}\label{sec:f4sat}
\msolve also proposes algorithms for computing Gr\"obner bases of
saturation and colon ideals. Given $m+1$ polynomials
$f_1,\ldots,f_m,\varphi$ over a field $\K$ with variables
$x_1,\ldots,x_n$,
the saturation ideal
$\langle f_1,\ldots,f_m\rangle:\langle \varphi\rangle^{\infty}$ is the ideal of all
polynomials $h$, such that there exists $k\in\N$ such that
$h \varphi^k\in\langle f_1,\ldots,f_m\rangle$.
The colon ideal
$\langle f_1,\ldots,f_m\rangle:\langle \varphi\rangle$ is the ideal of all
polynomials $h$, such that
$h \varphi\in\langle f_1,\ldots,f_m\rangle$.

A Gr\"obner basis for the \emph{grevlex order} can be computed in the
former case with an input file containg $f_1,\ldots,f_m,\varphi$ and
called with the flag \verb+-S+ to use the F4SAT algorithm. Note that this option 
is at the moment restricted to 32 bit prime fields.

For instance, consider the following input to \msolve written in a file
\verb+in.ms+.
\msolveinput{examples/saturate_char1073741827.ms}
Then, typing the following command line
\begin{tcolorbox} % examples/saturate_char1073741827.sh
  \begin{verbatim}
    ./msolve  -S -g 2 -f in.ms -o out.ms 
  \end{verbatim}
\end{tcolorbox}
will display in the \verb+out.ms+ file the following content. 
\begin{tcolorbox}
  \begin{lstlisting}
#Reduced Groebner basis data
#---
#field characteristic: 1073741827
#variable order:       w, x, y, z
#monomial order:       graded reverse lexicographical
#length of basis:      6 elements sorted by increasing leading monomials
#---
[1*w^1*y^3+1073741826*x^1*z^3,
1*x^4,
1*w^1*x^3,
1*w^2*x^2,
1*w^3*x^1,
1*w^4]:
  \end{lstlisting}
\end{tcolorbox}


% \section{Preliminaries}

% Polynomial systems arise in a wide range of applications in engineering and
% computing sciences. What it means to ``solve'' a polynomial system mainly
% depends on the application, the \emph{domain} where the coefficients lie and the
% properties of the solution set.

% For instance, in many applications of engineering sciences, the coefficients lie
% in the \emph{field} of rational numbers $\Q$. Sometimes, these coefficients
% appear as \emph{floating point} numbers but since floating point arithmetics is
% not fully convenient to handle reliably non-linear systems, the end-user may
% coerce these coefficients into rational numbers. There, using continued
% fractions is quite useful as it allows one to obtain reliable approximations
% with integers of small \emph{height} (hence small length when represented with
% bits). 

% All in all, one ends up with polynomial equations in the polynomial ring
% $\Q[x_1, \ldots, x_n]$, i.e. the set of polynomials with coefficients in $\Q$
% and involving indeterminates $x_1, \ldots, x_n$.

% In such applications, the end-user will most of the time expect informations on
% the solutions with coordinates in the field of real numbers $\R$ (for instance
% in robotics or biology) or in the field of complex numbers $\C$ (for instance in
% signal theory).

% When the number of solutions of such systems in $\C^n$ is finite (one says that
% such systems have dimension at most zero), then it is well-known that the
% coordinates of the solutions can be parametrized by an \emph{algebraic number}
% at which one evaluates a rational fraction. In other words, there exist
% univariate polynomials $(w, v_1, \ldots, v_n)$ in $\Q[t]$ such that $w$ is
% square-free and the solution set in $\C^n$ can be written as
% \[
%   \left \{
%   \left (\frac{v_1(\vartheta)}{w'(\vartheta)}, \ldots,
%   \frac{v_n(\vartheta)}{w'(\vartheta)}\right ) \quad \st \quad w(\vartheta) = 0
% \right \}
% \]
% where
% $w'=\frac{\ud w}{\ud t}$.
% % $w'=\frac{\partial w}{\partial t}$.
% Note that, with such an encoding
% (which is called a rational parametrization of the solution set), one can
% approximate at arbitrary precision the solutions of the input system (by isolating
% the ones of the univariate polynomial $w$).
% Note also that, since $w$ is square-free, $w$ and $w'$ are co-prime and the
% denominator in the above parametrization can be replaced by a constant.

% Remark that the total number of solutions in $\C^n$ equals the degree of $w$.
% Hence, when the input system has no complex solution, $w$ is a non-zero
% constant. Also, the number of real roots to the input system is the number of
% real roots of $w$.

% Note also that this encoding loses the number of solutions counted with
% \emph{multiplicities} ; this number is called the \emph{degree} of the input
% system (which always dominates the number of complex solutions). 

% For systems in $\Q[x_1, \ldots, x_n]$, \msolve~is able to decide if they have
% finitely many complex solutions and, in that case, returns a rational
% parametrization of the solution set in $\C^n$. It also counts and isolates the
% real roots of the polynomial $w$. We refer to Section~\ref{sec:zerodim} for
% details on how \msolve~encodes such outputs.

% When the input system has infinitely many complex solutions, \msolve~can output
% a \emph{Gr\"obner basis} of the \emph{ideal} generated by all input polynomials
% ; this is a family of polynomials which is obtained by taking appropriate
% algebraic combinations of the input polynomials and from which one can extract
% several properties of the solution set, in particular its \emph{dimension} and
% its \emph{degree} (see Section~\ref{sec:posdim}). 

% For applications in cryptology and/or coding theory, polynomial systems lie in
% some polynomial ring $\bF[x_1, \ldots, x_n]$ where $\bF$ is some finite field. In
% that situation, \msolve~only supports prime field $\frac{\Z}{p\Z}$ with $p <
% 2^{31}$. Denoting by $\overline{\bF}$ an algebraic closure of $\bF$, such systems
% have dimension at most $0$ when they have finitely many solutions in
% $\overline{\bF}^n$, else they have positive dimension. For systems of dimension
% at most zero, a rational parametrization as above can be computed when the
% characteristic of the field is large enough. 

% \section{Solving polynomial systems of dimension at most zero}\label{sec:zerodim}

% Let $\K$ be a field and $\overline{\K}$ be an algebraic closure of $\K$. We
% consider polynomials $(f_1, \ldots, f_s)$  in $\K[x_1, \ldots,
% x_n]$ and $V$ be the set of solutions to the system
% \[
% f_1=\cdots=f_s=0
% \]
% in $\overline{\K}^n$.

% When $V$ is
% empty,
% % in $\overline{\K}[x_1, \ldots, x_n]$,
% the
% output of \msolve~is
% \begin{verbatim}
% [1, []]
% \end{verbatim}

% When $V$ is finite, say $V$ is the union of the $\ell$ points $\balpha_1,
% \ldots, \balpha_\ell$ in $\overline{\K}^n$ with $\balpha_i = (\alpha_{i,1},
% \ldots, \alpha_{i,n})$,
% % When the input system has finitely many solutions in
% % $\overline{\K}^n$,
% the
% output is encoded as follows:
% % \begin{verbatim}
% % [dim, [deg, nbsols, form, vars, [lw, lwp, param]]]
% % \end{verbatim}
% % where
% % \begin{itemize}
% % \item \texttt{dim} is $0$ (which indicates that the input system has finitely
% %   many solutions);
% % \item \texttt{deg} is the number of solutions counted with multiplicities in
% %   $\overline{\K}^n$;
% % \item \texttt{nbsols} is the number of solutions in $\overline{\K}^n$; 
% % \item \texttt{form} is the linear form $t$;
% % \item \texttt{vars} is the list of the variables which are parametrized;
% % \item \texttt{lw} is the encoding of the eliminating polynomial $w$;
% % \item \texttt{lwp} is the encoding of the denominator used in the rational
% %   parametrization;
% % \item \texttt{param} is the list of the output parametrizations as described
% %   above ; the $i$th one corresponds to the $i$th element of \texttt{vars}.
% %   % \textcolor{magenta}{I am not sure this is still the case, maybe I used a reverse
% %   %   ordering.} 
% % \end{itemize}
% \begin{verbatim}
% [dim, nbvar, deg, varstr, linform, lw, lwp, param]
% \end{verbatim}
% in characteristic $0$, where
% \begin{itemize}
% \item \texttt{dim} is $0$ (which indicates that the input system has finitely
%   many solutions);
% \item \texttt{nbvar} is the number of variables;
% \item \texttt{deg} is the number of solutions counted with multiplicities in
%   $\overline{\K}^n$;
% % \item \texttt{nbsols} is the number of solutions in $\overline{\K}^n$; 
% \item \texttt{varstr} is the list of the variables which are parametrized;
% \item \texttt{linform} is the linear form $t$, it is empty if there is none;
% \item \texttt{lw} is the encoding of the eliminating polynomial $w$
%   either in $t$ or the last variable of \texttt{varstr};
% \item \texttt{lwp} is the encoding of the denominator used in the rational
%   parametrization;
% \item \texttt{param} is the list of the output parametrizations as described
%   above ; the $i$th one corresponds to the $i$th element of \texttt{varstr}.
%   % \textcolor{magenta}{I am not sure this is still the case, maybe I used a reverse
%   %   ordering.} 
% \end{itemize}
% \begin{verbatim}
% [char, nbvar, elim, den, param]
% \end{verbatim}
% in positive characteristic, where
% \begin{itemize}
% \item \texttt{char} is the characteristic of the field;
% % \item \texttt{dim} is $0$ (which indicates that the input system has finitely
% %   many solutions);
% \item \texttt{nbvar} is the number of variables;
% \item \texttt{elim} is the encoding of the eliminating polynomial of
%   the last variable;
% \item \texttt{den} is the encoding of the denominator used in the rational
%   parametrization, it is always $1$ at the moment;
% \item \texttt{param} is the list of the output parametrizations as described
%   above ; the $i$th one corresponds to the $i$th element of \texttt{vars}.
%   % \textcolor{magenta}{I am not sure this is still the case, maybe I used a reverse
%   %   ordering.} 
% \end{itemize}


% %\textcolor{magenta}{Here we should give (small) examples.}
% \section{Solving polynomial systems of positive dimension}\label{sec:posdim}


\section{More flags and options}\label{sec:flags}

\begin{itemize}
\item The flag \verb+-h+ displays some documentation

\item The flag \verb+-v <int>+ controls the verbosity

  \hfill \verb+Default value: 0+

\item The flag \verb+-t <int>+ controls the number of threads used

  \hfill \verb+Default value: 1+

\item The flag \verb+-p <int>+ controls the binary precision of the output of the 
    univariate real root
    solver (default value may be automatically increased by \msolve when needed).

    \hfill \verb+Default value:128+
\item The flag \verb+-g <int>+ tells \msolve to output the leading monomial of
  the ideal generated by the input polynomials (when \verb+<int>+ is \verb+1+)
  or the minimal reduced Gr\"obner basis (when \verb+<int>+ is \verb+2+ and
  a prime characteristic is indicated).

  \hfill \verb+Default value:0+

\item The flag \verb+-P <int>+ tells \msolve to output the 
rational parametrization computed for solving zero-dimensional polynomial 
systems (those with finitely many solutions in an algebraic closure of the base field).
When +\verb+-P 0+ is set, such a parametrization is not returned, when \verb+-P 1+ is
set, the parametrization is returned and, in the charactersitic zero case (rational 
coefficients), real solutions are returned, when +\verb+-P 2+ is set, only the 
rational parametrization is returned.

  \hfill \verb+Default value:0+


\item The flag \verb+-c <int>+ tells \msolve how to handle genericity
  requirements: when \verb+<int>+ is \verb+0+ \msolve quits when these
  requirements are not satisfied, when \verb+<int>+ is \verb+1+ \msolve is
  allowed to change the order of the variables if needed and quits if after
  these changes, the genericity requirements are not satisfied,  when
  \verb+<int>+ is \verb+2+ \msolve is allowed to introduce a new variable and a
  linear form until the genericity requirements are satisfied. 

  \hfill \verb+Default value:2+

\item The flag \verb+-d <int>+ tells \msolve how to handle further genericity
  requirements when the staircase is not generic enough by computing some normal forms:
  \verb+<int>+ can go from \verb+0+ (no normal form computations are computed) to
  \verb+4+ (all the normal forms are computed). 

  \hfill \verb+Default value:2+
  
\end{itemize}

\section{Julia interface to \msolve}
The Julia interface to \msolve is part of the official Julia package
\texttt{Oscar.jl}. You can install the package via the following
commands inside a Julia session:\\[1em]
\texttt{using Pkg\\
Pkg.add(“Oscar”)}\\[1em]
Once the package is loaded via \texttt{using Oscar} one can call the function
\texttt{msolve()} which returns, if any, the rational parametrization and the solutions of the given input
system of multivariate polynomials. The most common calling convention is as follows:\\[1em]
\texttt{res = msolve(I)}.\\[1em]
where
\begin{itemize}
    \item \texttt{I} is of type \texttt{ideal}.
\end{itemize}
The most common options for calling \texttt{msolve()} in Julia are:
\begin{itemize}
    \item \texttt{info\_level} with values \texttt{0} (no information printing;
        default), \texttt{1} (slight information printing on comptutational
        status) or \texttt{2} (full information printing also on intermediate
        steps),
    \item \texttt{la\_option} for the linear algebra variant to be chosen inside
        F4: \texttt{2} for exact linear algebra and tracing multi modular
        computations (default) or \texttt{44} for probabilistic linear algebra
        with independent modular computations;
    \item \texttt{precision} for the bit precision with which the solutions are
        computed from the rational parametrization. Default is \texttt{64}.
\end{itemize}
So using \texttt{msolve()} with probabilistic linear algebra, the most verbose
information printout and a precision of $80$ one would call\\[1em]
\texttt{res = msolve(I, la\_option=44, info\_level=2,
precision=80)}.\\[1em]
You can get a full list of options for \texttt{msolve()} in Julia by typing
inside Julia\\[1em]
\texttt{? msolve()}
\section{Maple interface to \msolve}

The Maple interface to \msolve is a file interface which can be found on the
\msolve \href{https://msolve.lip6.fr/interfaces/index.html}{interface
  page} or in the \msolve binary package. Having loaded the interface
one can call the function
\texttt{MSolveRealRoots()} in the following way:\\[1em]
\texttt{results = MSolveRealRoots(F, vars)}\\[1em]
where \texttt{F} denotes a polynomial system in variables \texttt{vars},


In order to compute Gr\"obner bases, you can also the function
\texttt{MSolveGroebner}. 

You may consult the source code for optional arguments which allow you to better
control the output format, the names of used files, verbosity, etc.

\section{Sage interface to \msolve}

There is now an interface between \href{https://www.sagemath.org/}{SageMath} 
and \msolve. 

You can have a look at 
\url{https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/msolve.py}
and 
\url{https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/multi_polynomial_ideal.py}

\hfill Many thanks to the SageMath development team, in particular to Marc 
Mezzarobba who initiated this interface.

%The Sage interface to \msolve can be found on the \msolve homepage or in the
%\msolve binary package. Starting
%Sage we load the interface:\\[1em]
%\texttt{load(“msolve-to-sage-file-interface.sage”)}.\\[1em]
%Defining a multivariate polynomial ring \texttt{R} and a list \texttt{F} of
%polynomials in \texttt{R} one can solve the multivariate polynomial system
%defined by \texttt{F} via calling\\[1em]
%\texttt{results = MSolveRealRoots(}\\
%\texttt{F, mspath=“/path/to/msolve/binary”,
%v=verbosity, p=get\_parametrization)}\\[1em]
%Parameter \texttt{mspath} states the path to the msolve binary (default is
%\texttt{“../binary/msolve”}).
%The verbosity level can be set to \texttt{0} (no information printing; default),
%\texttt{1} (slight information printing on computational status) or \texttt{2}
%(full information printing also on intermediate steps).
%The \texttt{p} parameter can be set to \texttt{0} (rational parametrization of
%solution set is not returned) or \texttt{1} (returns also the rational
%parametrization of the solution set). Depending on parameter \texttt{p}
%\texttt{results} consists only of the solutions or it is an array consisting of
%the rational parametrization as first entry and the solutions as second entry.

\section{Credits}

The main developers of \msolve~are J\'er\'emy Berthomieu, Christian Eder and
Mohab Safey El Din. It relies on original implementations of Faugère's \Fquatre
algorithm~\cite{F4} as well as Faug\`ere and Mou's Sparse-FGLM
algorithm~\cite{SparseFGLM}. We are grateful to Huu Phuoc Le and Jorge
García Fontán for a 
preliminary version of the Maple interface as well as Rémi Prébet for a
preliminary version of the Sage interface.  

If you use \msolve, you may cite:
\begin{verbatim}
@inproceedings{msolve,
  TITLE = {{msolve: A Library for Solving Polynomial Systems}},
  AUTHOR = {Berthomieu, J{\'e}r{\'e}my and Eder, Christian and {Safey El Din}, Mohab},
  URL = {https://hal.sorbonne-universite.fr/hal-03191666},
  BOOKTITLE = {{2021 International Symposium on Symbolic and Algebraic Computation}},
  ADDRESS = {Saint Petersburg, Russia},
  SERIES = {46th International Symposium on Symbolic and Algebraic Computation},
  YEAR = {2021},
  MONTH = Jul,
  DOI = {10.1145/3452143.3465545},
  PDF = {https://hal.sorbonne-universite.fr/hal-03191666v2/file/main.pdf},
  HAL_ID = {hal-03191666},
  HAL_VERSION = {v2},
}
\end{verbatim}
\renewcommand*{\bibfont}{\small}
  \printbibliography
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: