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


TitlePivoting in extended rings for computing approximate Gr\"obner bases.
Author(s) Faug`ere Jean-Charles, Ye Liang
TypeArticle in Journal
AbstractIt is well known that in the computation of Gröbner bases arbitrarily small perturbations in the coefficients of polynomials may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables) strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gröbner basis method so that we can use existing efficient algorithms (for instance the F 5 algorithm) to compute an approximate Gröbner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial ϵ-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems.
KeywordsApproximate Gröbner basis, Artificial discontinuity, Monomial basis, F 5 algorithm
ISSN1661-8270; 1661-8289/e
URL http://link.springer.com/article/10.1007%2Fs11786-011-0089-y
JournalMath. Comput. Sci.
PublisherSpringer (Birkh\"auser), Basel
Translation No
Refereed No