Changing the ordering of Gröbner Bases with LLL: Case of Two Variables

Abdolali Basiri; Jean-Charles Faugère

inria-00071841, version 1

Changing the ordering of Gröbner Bases with LLL: Case of Two Variables

Abdolali Basiri ^1, 2, Jean-Charles Faugère ^1, 2

N° RR-4746 (2003)

Résumé : We present an algorithm for the transformation of a Gröbner basis of an ideal with respect to any given ordering into a Gröbner basis with respect to any other ordering. This algorithm is based on a modified version of the LLL algorithm. The worst case theoretical complexity of this algorithm is not better than the complexity of the FGLM algorithm; but can also give the theoretical complexity with some parameters depending on the size of the output. When the output is small then algorithm is more efficient. We also present a first implementation of the algorithm in Maple. This algorithm is restricted to the case of two variables but works also in positive dimension.

1 : SPACES (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
2 : Laboratoire d'Informatique de Paris 6 (LIP6)
CNRS : UMR7606 – Université Pierre et Marie Curie (UPMC) - Paris VI

inria-00071841, version 1
http://hal.inria.fr/inria-00071841
oai:hal.inria.fr:inria-00071841
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mardi 23 Mai 2006, 18:56:21
Dernière modification le : Vendredi 7 Juillet 2006, 16:12:48

Voir la fiche détaillée

Documents associés

PS :

PDF :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00071841"><monogr>
<author><persName><forename>Abdolali</forename><surname>Basiri</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">SPACES</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIP6</orgName>
<orgName type="team">Laboratoire d'Informatique de Paris 6</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7606</orgName>
<orgName type="institution">Université Pierre et Marie Curie (UPMC) - Paris VI</orgName>
</affiliation>
</author>
<author><persName><forename>Jean-Charles</forename><surname>Faugère</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">SPACES</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIP6</orgName>
<orgName type="team">Laboratoire d'Informatique de Paris 6</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7606</orgName>
<orgName type="institution">Université Pierre et Marie Curie (UPMC) - Paris VI</orgName>
</affiliation>
</author>
<title type="main" level="m">Changing the ordering of Gröbner Bases with LLL: Case of Two Variables</title><title type="main" level="m">Changing the ordering of Gröbner Bases with LLL: Case of Two Variables</title><imprint><biblScope type="publicationDate">2003-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00071841</idno><idno type="HALFile">http://hal.inria.fr/inria-00071841/PDF/RR-4746.pdf</idno></biblStruct>
</listBibl>
</listBibl>