Search

Your search keyword '"F5 algorithm"' showing total 24 results
Start Over Descriptor "F5 algorithm"
24 results on '"F5 algorithm"'

1. A single exponential time algorithm for homogeneous regular sequence tests.

Author

Hashemi, Amir, Alizadeh, Benyamin M., Parnian, Hossein, and Seiler, Werner M.

Subjects
*HOMOGENEOUS polynomials, *ARITHMETIC, *POLYNOMIALS, *ALGORITHMS
Abstract

Assume that we are given a sequence F of k homogeneous polynomials in n variables of degree at most d and the ideal ℐ generated by this sequence. The aim of this paper is to present a new and effective method to determine, within the arithmetic complexity d O (n) , whether F is regular. This algorithm has been implemented in Maple and its efficiency (compared to the classical approaches for regular sequence test) is evaluated via a set of benchmark polynomials. Furthermore, we show that if F is regular then we can transform ℐ into Nœther position and at the same time compute a reduced Gröbner basis for the transformed ideal within the arithmetic complexity d O (n 2) . Finally, under the same assumption, we establish the new upper bound 2 (d k / 2) 2 n − k − 1 for the maximum degree of the elements of any reduced Gröbner basis of ℐ in the case that n > k. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

2. A Controllable Image Steganography with Chaos and User Key

Author

Liu, Jianyi, Wang, Yuhan, Yang, Zhen, Zhang, Ruifan, Zhang, Ru, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Peng, Yuxin, editor, Hu, Shi-Min, editor, Gabbouj, Moncef, editor, Zhou, Kun, editor, Elad, Michael, editor, and Xu, Kun, editor

Published
2021
Full Text
View/download PDF

3. Axioms for a theory of signature bases.

Author

Lairez, Pierre

Subjects
*GROBNER bases, *NONCOMMUTATIVE rings
Abstract

Twenty years after the discovery of the F5 algorithm, Gröbner bases with signatures are still challenging to understand and to adapt to different settings. This contrasts with Buchberger's algorithm, which we can bend in many directions keeping correctness and termination obvious. I propose an axiomatic approach to Gröbner bases with signatures with the purpose of uncoupling the theory and the algorithms, giving general results applicable in many different settings (e.g. Gröbner for submodules, F4-style reduction, noncommutative rings, non-Noetherian settings, etc.), and extending the reach of signature algorithms. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

4. DNA Based Image Steganography

Author

Vinodhini, R. E., Malathi, P., Tavares, João Manuel R.S., Series Editor, Jorge, Renato Natal, Series Editor, Hemanth, D. Jude, editor, and Smys, S., editor

Published
2018
Full Text
View/download PDF

5. An Enhanced Steganographic Code and its Application in Voice-Over-IP Steganography

Author

Lejun Zhang, Xiaoyan Hu, Waqas Rasheed, Tianwen Huang, and Chunhui Zhao

Subjects
F5 algorithm, steganography, streaming media, voice over IP, wet paper code, Electrical engineering. Electronics. Nuclear engineering, TK1-9971
Abstract

Voice-over IP (VoIP) technology is a kind of digital transmission technology based on IP network. It is one of the important methods to use voice service in VoIP as steganographic carrier to ensure secure transmission. However, the traditional steganographic code has some problems, such as low embedding efficiency and weak concealment, which cannot meet the requirements of VoIP streaming media information hiding for the security of secret information. Therefore, a steganographic algorithm combining F5 and simplified wet paper code (SWPC) algorithm is proposed. The main idea is to embed secret messages in each row of the carrier matrix using the F5 algorithm, and then the SWPC algorithm is used to embed the columns according to the wet and dry characteristics of the wet paper code without affecting the results before row embedding. We use the VoIP streams encoded by the ITU-T G.729a codec as a carrier to verify the proposed scheme. The experimental results demonstrate that the proposed scheme can achieve relatively better IP speech data steganographic transparency and that it can outperform F5-WPC and SWPC approaches.

Published
2019
Full Text
View/download PDF

6. On affine tropical F5 algorithms.

Author

Vaccon, Tristan, Verron, Thibaut, and Yokoyama, Kazuhiro

Subjects
*GROBNER bases, *ALGORITHMS, *DEFINITIONS, *POLYNOMIAL rings
Abstract

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p -adic field that are more stable than that of classical Gröbner bases. Beforehand, these strategies were only available for homogeneous polynomials. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We also provide a competitor with an adaptation of the F4 strategy to tropical Gröbner bases computations. We provide numerical examples to illustrate time-complexity and p -adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p -adics. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

8. Axioms for a theory of signature bases

Author

Lairez, Pierre, Calcul formel, mathématiques expérimentales et interactions (MATHEXP), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), and European Project: 101040794,10000 DIGITS

Subjects
Computer Science - Symbolic Computation, FOS: Computer and information sciences, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], FOS: Mathematics, signature basis, F5 algorithm, Symbolic Computation (cs.SC), Mathematics - Commutative Algebra, Commutative Algebra (math.AC), Gröbner basis
Abstract

Twenty years after the discovery of the F5 algorithm, Gr\"obner bases with signatures are still challenging to understand and to adapt to different settings. This contrasts with Buchberger's algorithm, which we can bend in many directions keeping correctness and termination obvious. I propose an axiomatic approach to Gr\"obner bases with signatures with the purpose of uncoupling the theory and the algorithms, and giving general results applicable in many different settings (e.g. Gr\"obner for submodules, F4-style reduction, noncommutative rings, non-Noetherian settings, etc.).

Published
2022

9. Matrix-F5 algorithms and tropical Gröbner bases computation.

Author

Vaccon, Tristan

Subjects
*ALGORITHMS, *MATHEMATICAL programming, *NUMERICAL analysis, *POLYNOMIALS, *ALGEBRA
Abstract

Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K . Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a p -adic field. We design a strategy to compute such tropical Gröbner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster. Our study is performed both over any exact field with valuation and some inexact fields like Q p or F q ( ( t ) ) . In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Gröbner bases when the valuation is non-trivial. Numerical examples are provided. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

10. Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects

Author

Faugère, Jean-Charles, Perret, Ludovic, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Vaudenay, Serge, editor

Published
2006
Full Text
View/download PDF

11. Matrix-F5 algorithms over finite-precision complete discrete valuation fields.

Author

Vaccon, Tristan

Subjects
*MATRICES (Mathematics), *DISCRETE systems, *MATHEMATICAL sequences, *HOMOGENEOUS polynomials, *IDEALS (Algebra)
Abstract

Let ( f 1 , … , f s ) ∈ Q p [ X 1 , … , X n ] s be a sequence of homogeneous polynomials with p -adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since Q p is not an effective field, classical algorithm does not apply. We provide a definition for an approximate Gröbner basis with respect to a monomial order w . We design a strategy to compute such a basis, when precision is enough and under the assumption that the input sequence is regular and the ideals 〈 f 1 , … , f i 〉 are weakly- w -ideals. The conjecture of Moreno-Socias states that for the grevlex ordering, such sequences are generic. Two variants of that strategy are available, depending on whether one leans more on precision or time-complexity. For the analysis of these algorithms, we study the loss of precision of the Gauss row-echelon algorithm, and apply it to an adapted Matrix-F5 algorithm. Numerical examples are provided. Moreover, the fact that under such hypotheses, Gröbner bases can be computed stably has many applications. Firstly, the mapping sending ( f 1 , … , f s ) to the reduced Gröbner basis of the ideal they span is differentiable, and its differential can be given explicitly. Secondly, these hypotheses allow to perform lifting on the Grobner bases, from Z / p k Z to Z / p k + k ′ Z or Z . Finally, asking for the same hypotheses on the highest-degree homogeneous components of the entry polynomials allows to extend our strategy to the affine case. [ABSTRACT FROM AUTHOR]

Published
2017
Full Text
View/download PDF

12. A NEW FRAMEWORK FOR COMPUTING GRÖBNER BASES.

Author

SHUHONG GAO, VOLNY VI, FRANK, and MINGSHENG WANG

Subjects
*GROBNER bases, *IDEALS (Algebra), *SYZYGIES (Mathematics), *POLYNOMIALS, *COMMUTATIVE algebra, *FREE resolutions (Algebra)
Abstract

This paper presents a new framework for computing Gröbner bases for ideals and syzygy modules. It is proposed to work in a module that accommodates any given ideal and the corresponding syzygy module (for the given generators of the ideal). A strong Gröbner basis for this module contains Gröbner bases for both the ideal and the syzygy module. The main result is a simple characterization of strong Gröbner bases. This characterization can detect useless S-polynomials without reductions, thus yields an efficient algorithm. It also explains all the rewritten rules used in F5 and the recent papers in the literature. Rigorous proofs are given for the correctness and finite termination of the algorithm. For any term order for an ideal, one may vary signature orders (i.e. the term orders for the syzygy module). It is shown by computer experiments on benchmark examples that signature orders based on weighted terms are much better than other signature orders. This is useful for practical computation. Also, since computing Göbner bases for syzygies is a main computational task for free resolutions in commutative algebra, the algorithm of this paper should be useful for computing free resolutions in practice. [ABSTRACT FROM AUTHOR]

Published
2016
Full Text
View/download PDF

13. An Enhanced Steganographic Code and its Application in Voice-Over-IP Steganography

Author

Waqas Rasheed, Chunhui Zhao, Tianwen Huang, Lejun Zhang, and Xiaoyan Hu

Subjects
General Computer Science, computer.internet_protocol, Computer science, Speech coding, 02 engineering and technology, Data_CODINGANDINFORMATIONTHEORY, wet paper code, Internet protocol suite, 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), Codec, General Materials Science, F5 algorithm, steganography, Secure transmission, Voice over IP, Steganography, business.industry, 020208 electrical & electronic engineering, streaming media, General Engineering, voice over IP, Information hiding, lcsh:Electrical engineering. Electronics. Nuclear engineering, business, computer, lcsh:TK1-9971, Data transmission, Computer network
Abstract

Voice-over IP (VoIP) technology is a kind of digital transmission technology based on IP network. It is one of the important methods to use voice service in VoIP as steganographic carrier to ensure secure transmission. However, the traditional steganographic code has some problems, such as low embedding efficiency and weak concealment, which cannot meet the requirements of VoIP streaming media information hiding for the security of secret information. Therefore, a steganographic algorithm combining F5 and simplified wet paper code (SWPC) algorithm is proposed. The main idea is to embed secret messages in each row of the carrier matrix using the F5 algorithm, and then the SWPC algorithm is used to embed the columns according to the wet and dry characteristics of the wet paper code without affecting the results before row embedding. We use the VoIP streams encoded by the ITU-T G.729a codec as a carrier to verify the proposed scheme. The experimental results demonstrate that the proposed scheme can achieve relatively better IP speech data steganographic transparency and that it can outperform F5-WPC and SWPC approaches.

Published
2019

14. Signature-based algorithms for Gröbner bases over Tate algebras

Author

Tristan Vaccon, Xavier Caruso, Thibaut Verron, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Johannes Kepler Universität Linz, Lithe and fast algorithmic number theory (LFANT), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Johannes Kepler Universität Linz (JKU), The first author is supported by the French ANR grant CLap–CLap, referenced ANR18-CE40-0026-01. The third author is supported by the Austrian FWF grant P31571-N32, and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
Computer Science - Symbolic Computation, Power series, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Polynomial, GeneralLiterature_INTRODUCTORYANDSURVEY, Mathematics::Number Theory, 010102 general mathematics, 010103 numerical & computational mathematics, Algebraic geometry, P-adic precision, 01 natural sciences, Formalism (philosophy of mathematics), Analytic geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Gröbner bases, F5 algorithm, 0101 mathematics, Tate algebra, Algorithm, Algorithms, Mathematics
Abstract

Introduced by Tate in [Ta71], Tate algebras play a major role in the context of analytic geometry over the-adics, where they act as a counterpart to the use of polynomial algebras in classical algebraic geometry. In [CVV19] the formalism of Gr{\"o}bner bases over Tate algebras has been introduced and effectively implemented. One of the bottleneck in the algorithms was the time spent on reduction , which are significantly costlier than over polynomials. In the present article, we introduce two signature-based Gr{\"o}bner bases algorithms for Tate algebras, in order to avoid many reductions. They have been implemented in SageMath. We discuss their superiority based on numerical evidences., Comment: ISSAC 2021 - International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata / Virtual, Greece

Published
2020

15. Matrix-F5 algorithms and tropical Gröbner bases computation

Author

Tristan Vaccon, Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)

Subjects
Computer Science - Symbolic Computation, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], Computation, Polynomial ring, Field (mathematics), 0102 computer and information sciences, 01 natural sciences, [ MATH.MATH-AC ] Mathematics [math]/Commutative Algebra [math.AC], Matrix (mathematics), F5 algorithm, 0101 mathematics, Valuation (algebra), Mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebra and Number Theory, $p$-adic algorithm, Mathematics::Commutative Algebra, 010102 general mathematics, $p$-adic precision, Mathematics - Commutative Algebra, [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC], Valuation (logic), Computational Mathematics, tropical geometry, 010201 computation theory & mathematics, Gröbner bases, Algorithm, Numerical stability
Abstract

International audience; Let $K$ be a field equipped with a valuation. Tropical varieties over $K$ can be defined with a theory of Gröbner bases taking into account the valuation of $K$. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a $p$-adic fields.We design a strategy to compute such tropical Gröbner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster.Our study is performed both over any exact field with valuation and some inexact fields like $\mathbb{Q}_p$ or $\mathbb{F}_q \llbracket t \rrbracket.$ In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Gröbner bases when the valuation is non-trivial. Numerical examples are provided.

Published
2018

16. GVW algorithm over principal ideal domains.

Author

Li, Dongmei, Liu, Jinwang, Liu, Weijun, and Zheng, Licui

Abstract

GVW algorithm was given by Gao, Wang, and Volny in computing a Gröbner bases for ideal in a polynomial ring, which is much faster and more simple than F5. In this paper, the authors generalize GVW algorithm and present an algorithm to compute a Gröbner bases for ideal when the coefficient ring is a principal ideal domain. [ABSTRACT FROM AUTHOR]

Published
2013
Full Text
View/download PDF

17. The F5 algorithm in Buchberger's style.

Author

Sun, Yao and Wang, Dingkang

Abstract

The famous F5 algorithm for computing Gröbner basis was presented by Faugère in 2002. The original version of F5 is given in programming codes, so it is a bit difficult to understand. In this paper, the F5 algorithm is simplified as F5B in a Buchberger's style such that it is easy to understand and implement. In order to describe F5B, we introduce F5-reduction, which keeps the signature of labeled polynomials unchanged after reduction. The equivalence between F5 and F5B is also shown. At last, some versions of the F5 algorithm are illustrated. [ABSTRACT FROM AUTHOR]

Published
2011
Full Text
View/download PDF

19. On Affine Tropical F5 Algorithms

Author

Tristan Vaccon, Kazuhiro Yokoyama, Thibaut Verron, Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Johannes Kepler Universität Linz (JKU), Department of Mathematics [Rikkyo], Rikkyo University [Tokyo], and Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Computer Science - Symbolic Computation, Polynomial ring, Computation, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], Stability (learning theory), p-adic precision, Field (mathematics), 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), Commutative Algebra (math.AC), 01 natural sciences, CCS CONCEPTS, Tropical geometry, • Computing methodologies → Algebraic algorithms, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, F5 algorithm, 0101 mathematics, p-adic, Valuation (algebra), Mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebra and Number Theory, Mathematics::Commutative Algebra, 010102 general mathematics, Mathematics - Commutative Algebra, Computational Mathematics, Homogeneous, KEYWORDS, Gröbner bases, precision, Affine transformation, Algorithm, Algorithms
Abstract

This article is an extended version of: https://hal.archives-ouvertes.fr/hal-01792165; International audience; Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gröbner bases has proved to provide settings for computations over polynomial rings over a p-adic field that are more stable than that of classical Gröbner bases. Beforehand, these strategies were only available for homogeneous polynomi-als. In this article, we extend the F5 strategy to a new definition of tropical Gröbner bases in an affine setting. We also provide a competitor with an adaptation of the F4 strategy to tropical Gröbner bases computations. We provide numerical examples to illustrate time-complexity and p-adic stability of this tropical F5 algorithm. We also illustrate its merits as a first step before an FGLM algorithm to compute (classical) lex bases over p-adics.

Published
2018

20. On the complexity of the F5 Gröbner basis algorithm

Author

Magali Bardet, Jean-Charles Faugère, Bruno Salvy, Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), Polynomial Systems (PolSys), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), ANR-11-BS02-0013,HPAC,Calcul Algébrique Haute-Performance(2011), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Algebra and Number Theory, Degree (graph theory), Complexity, Reduction (complexity), Computational Mathematics, symbols.namesake, Matrix (mathematics), Gröbner basis, Noether Position, Gaussian elimination, Regular Sequences, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems, Position (vector), Strassen algorithm, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, symbols, Multiplication, Computer Science::Symbolic Computation, Gröbner bases, F5 algorithm, Algorithm, Mathematics
Abstract

International audience; We study the complexity of Gr¨obner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We give a bound on the number of polynomials of degree d in a Gr¨obner basis computed by Faug'ere's F5 algorithm (2002) in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gr¨obner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gr¨obner bases with signatures that F5 computes and use it to bound the complexity of the algorithm. Our estimates show that the version of F5 we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen's multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.

Published
2015

22. Matrix-F5 algorithms over finite-precision complete discrete valuation fields

Author

Tristan Vaccon, Rikkyo University [Tokyo], Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Labex Lebesgue, Université Européenne de Bretagne (UEB), école doctorale Matisse, projet ANR Peace, ANR-12-BS01-0010,PEACE,Espaces de paramètres pour une arithmétique efficace et une évaluation de la sécurité des courbes(2012), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), and ANR-12-BS01-0010,PEACE,Espaces de paramètres pour une arithmétique efficace et une évaluation de la sécurité des courbes ( 2012 )

Subjects
FOS: Computer and information sciences, Computer Science - Symbolic Computation, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], Field (mathematics), 010103 numerical & computational mathematics, Symbolic Computation (cs.SC), Commutative Algebra (math.AC), 01 natural sciences, [ MATH.MATH-AC ] Mathematics [math]/Commutative Algebra [math.AC], Combinatorics, Matrix (mathematics), Gröbner basis, FOS: Mathematics, Ideal (ring theory), Differentiable function, F5 algorithm, 0101 mathematics, Discrete valuation, Monomial order, Mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Discrete mathematics, Sequence, Algebra and Number Theory, $p$-adic algorithm, Basis (linear algebra), 010102 general mathematics, Gauss, $p$-adic precision, Mathematics - Commutative Algebra, [ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC], Computational Mathematics, Moreno-Socias conjecture, Gröbner bases, Algorithm
Abstract

Let ( f 1 , … , f s ) ∈ Q p [ X 1 , … , X n ] s be a sequence of homogeneous polynomials with p-adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since Q p is not an effective field, classical algorithm does not apply. We provide a definition for an approximate Grobner basis with respect to a monomial order w. We design a strategy to compute such a basis, when precision is enough and under the assumption that the input sequence is regular and the ideals 〈 f 1 , … , f i 〉 are weakly-w-ideals. The conjecture of Moreno-Socias states that for the grevlex ordering, such sequences are generic. Two variants of that strategy are available, depending on whether one leans more on precision or time-complexity. For the analysis of these algorithms, we study the loss of precision of the Gauss row-echelon algorithm, and apply it to an adapted Matrix-F5 algorithm. Numerical examples are provided. Moreover, the fact that under such hypotheses, Grobner bases can be computed stably has many applications. Firstly, the mapping sending ( f 1 , … , f s ) to the reduced Grobner basis of the ideal they span is differentiable, and its differential can be given explicitly. Secondly, these hypotheses allow to perform lifting on the Grobner bases, from Z / p k Z to Z / p k + k ′ Z or Z . Finally, asking for the same hypotheses on the highest-degree homogeneous components of the entry polynomials allows to extend our strategy to the affine case.

Published
2014

23. New Algorithms for Computing Groebner Bases

Author

Volny, Frank

Subjects
Buchberger's algorithm, colon ideal, f5 algorithm, Groebner basis, signature based algorithm, syzygy module, Applied Mathematics
Abstract

In this thesis, we present new algorithms for computing Groebner bases. The first algorithm, G2V, is incremental in the same fashion as F5 and F5C. At a typical step, one is given a Groebner basis G for an ideal I and any polynomial g, and it is desired to compute a Groebner basis for the new ideal , obtained from I by joining g. Let (I : g) denote the colon ideal of I divided by g. Our algorithm computes Groebner bases for I, g and (I : g) simultaneously. In previous algorithms, S-polynomials that reduce to zero are useless, in fact, F5 tries to avoid such reductions as much as possible. In our algorithm, however, these 'useless' S-polynomials give elements in (I : g) and are useful in speeding up the subsequent computations. Computer experiments on some benchmark examples indicate that our algorithm is much more efficient (two to ten times faster) than F5 and F5C. Next, we present a more general algorithm that matches Buchberger's algorithm in simplicity and yet is more flexible than G2V. Given a list of polynomials, the new algorithm computes simultaneously a Groebner basis for the ideal generated by the polynomials and a Groebner basis for the leading terms of the syzygy module of the polynomials. For any term order for the ideal, one may vary the term order for the syzygy module. Under one term order for the syzygy module, the new algorithm specializes to the G2V algorithm, and under another term order for the syzygy module, the new algorithm may be several times faster than G2V, as indicated by computer experiments on benchmark examples. Finally, we present a solid theoretical framework for G2V and GVW which makes the algorithm much more understandable. This theory also gives a major improvement of the GVW algorithm. A proof of termination is provided for all algorithms, and an argument is made that GVW computes the fewest number of generators for the signature based algorithms used by GVW and F5 (similarly for G2V and F5C).

Published
2011

24. Extended F5 criteria

Author

Hashemi, Amir and Ars, Gwénolé

Subjects
Gröbner bases, F5 algorithm, F5 criteria
Abstract

T Faugère’s F5 is one of the fastest known algorithm to compute Gröbner bases (see Faugère, 2002). The efficiency of this algorithm comes from two criteria namely F5 criteria, for which it assigns to each polynomial a signature. In this paper, we study the importance of choosing an ordering on the signatures, and we propose a novel ordering on the signatures. Using this ordering, we extend the F5 criteria, and we describe a new algorithm like F5 based on these extended criteria which (despite of F5) does not depend on the order of input polynomials. We have implemented our algorithm in Magma for computing the Gröbner basis of a general ideal, and we evaluate its performance via some examples. We show that the new algorithm is more stable and more efficient than F5, and experimentally it stops at a lower degree than F5.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results