Search

Your search keyword '"[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC]"' showing total 4 results
Start Over Descriptor "[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC]" Publisher acm
4 results on '"[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC]"'

1. 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
Full Text
View/download PDF

2. The M4RIE library for dense linear algebra over small fields with even characteristic

Author

Martin R. Albrecht, 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
FOS: Computer and information sciences, G.4, Discrete mathematics, Numerical linear algebra, Quaternion algebra, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], 010102 general mathematics, 010103 numerical & computational mathematics, computer.software_genre, 01 natural sciences, Basic Linear Algebra Subprograms, Categories and Subject Descriptors G4 [Mathematical Software]: Efficiency General Terms Linear Algebra, Matrix multiplication, Filtered algebra, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Linear algebra, Associative algebra, Cellular algebra, Computer Science - Mathematical Software, Implementations, 0101 mathematics, Mathematical Software (cs.MS), computer, Finite Fields, Mathematics
Abstract

International audience; In this work, we present the M4RIE library which implements efficient algorithms for linear algebra with dense matrices over GF(2^e) for 2

Published
2012
Full Text
View/download PDF

3. PARDI!

Author

Boulier, François, Lemaire, François, Moreno Maza, Marc, Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Calcul Formel (CALFOR), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Ontario Research Center for Computer Algebra (ORCCA), and University of Waterloo [Waterloo]-University of Western Ontario (UWO)

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], change of ranking, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, differential algebra, characteristic set, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], gcd, PDE
Abstract

International audience; We propose a new algorithm for converting a characteristic set of a prime differential ideal from one ranking into another. This differential algebra algorithm computes characteristic sets by change of ranking (ordering) for prime ideals. It identifies the purely algebraic subproblems which arise during differential computations and solves them algebraically. There are two improvements w.r.t. other approaches: formerly unsolved problems could be carried out; it is conceptually simple. Different variants are implemented.

Published
2001
Full Text
View/download PDF

4. Computation of free non-commutative gröbner bases over Z with Singular:Letterplace

Author

Viktor Levandovskyy, Karim Abou Zeid, Tobias Metzlaff, Institute for Industrial Management [RWTH Aachen University] (FIR e.V. an der RWTH Aachen), AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), The first and third authors (V. Levandovskyy and K. Abou Zeid) have been supported by Project II.6 of SFB-TRR 195 'Symbolic Toolsin Mathematics and their Applications' of the German Research Foundation (DFG).The work of the second author (T. Metzlaff ) has been supportedby European Union’s Horizon 2020 research and innovation pro-gramme under the Marie Skłodowska-Curie Actions, grant agree-ment 813211 (POEMA)., European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019), and European Project: 813211,H2020,POEMA(2019)

Subjects
Pure mathematics, Polynomial, Algebraic structure, Polynomial ring, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], 02 engineering and technology, 01 natural sciences, [MATH.MATH-GM]Mathematics [math]/General Mathematics [math.GM], Principal ideal, 0202 electrical engineering, electronic engineering, information engineering, Coefficients in rings, 0101 mathematics, [MATH]Mathematics [math], Commutative property, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], Zero divisor, Associative property, Mathematics, Non-commutative algebra, Mathematics::Commutative Algebra, 010102 general mathematics, Extension (predicate logic), [MATH.MATH-DG]Mathematics [math]/Differential Geometry [math.DG], 020201 artificial intelligence & image processing, Gröbner bases, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Algorithms
Abstract

International audience; The extension of Gröbner bases concept from polynomial algebras over fields to polynomial rings over rings allows to tackle numerous applications, both of theoretical and of practical importance. Gröbner and Gröbner-Shirshov bases can be defined for various non-commutative and even non-associative algebraic structures. We study the case of associative rings and aim at free algebras over principal ideal rings. We concentrate ourselves on the case of commutative coefficient ring without zero divisors (i. e. a domain). Even working over Z allows one to do computations, which can be treated as universal for fields of arbitrary characteristic. By using the systematic approach, we revisit the theory and present the algorithms in the implementable form. We show drastic differences in the behavior of Gröbner bases between free algebras and algebras, close to commutative. Even the formation of critical pairs has to be reengineered, together with the criteria for their quick discarding. We present an implementation of algorithms in the Singular subsystem called Letterplace, which internally uses Letterplace techniques (and Letterplace Gröbner bases), due to La Scala and Levandovskyy. Interesting examples accompany our presentation.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results