Border basis representation of a general quotient algebra

Bernard Mourrain 1 Philippe Trebuchet 2
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
2 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this paper, we generalized the construction of border bases to non-zero dimensional ideals for normal forms compatible with the degree, tackling the remaining obstacle for a general application of border basis methods. First, we give conditions to have a border basis up to a given degree. Next, we describe a new stopping criteria to determine when the reduction with respect to the leading terms is a normal form. This test based on the persistence and regularity theorems of Gotzmann yields a new algorithm for computing a border basis of any ideal, which proceeds incrementally degree by degree until its regularity. We detail it, prove its correctness, present its implementation and report some experimentations which illustrate its practical good behavior.
Complete list of metadatas

https://hal.inria.fr/hal-00709962
Contributor : Bernard Mourrain <>
Submitted on : Tuesday, June 19, 2012 - 5:10:24 PM
Last modification on : Thursday, March 21, 2019 - 2:19:00 PM
Long-term archiving on: Thursday, September 20, 2012 - 2:41:02 AM

Files

paper.pdf
Files produced by the author(s)

Identifiers

Citation

Bernard Mourrain, Philippe Trebuchet. Border basis representation of a general quotient algebra. International Conference on Symbolic and Algebraic Computation (ISSAC), Jul 2012, Grenoble, France. pp.265-272, ⟨10.1145/2442829.2442868⟩. ⟨hal-00709962⟩

Share

Metrics

Record views

398

Files downloads

502