Search

We generalize the analog of Buchberger's first criterion, stated by Boulier et al., for detecting useless S-polynomials reductions in the computation of characteristic sets of differential ideals. The original version assumes linear polynomials; this result is here extended to a product of linear differential polynomials depending of the same arbitrary differential polynomial., Comment: 12 pages. In French. With an extended abstract in English

We investigate the application of syzygies for efficiently computing (finite) Pommaret bases. For this purpose, we first describe a non-trivial variant of Gerdt's algorithm to construct an involutive basis for the input ideal as well as an involutive basis for the syzygy module of the output basis. Then we apply this new algorithm in the context of Seiler's method to transform a given ideal into quasi stable position to ensure the existence of a finite Pommaret basis. This new approach allows us to avoid superfluous reductions in the iterative computation of Janet bases required by this method. We conclude the paper by proposing an involutive variant of the signature based algorithm of Gao et al. to compute simultaneously a Grobner basis for a given ideal and for the syzygy module of the input basis. All the presented algorithms have been implemented in Maple and their performance is evaluated via a set of benchmark ideals., Comment: Computer Algebra in Scientific Computing (CASC 2018), Lille, France, 2018

In this paper, we study first the relationship between Pommaret bases and Hilbert series. Given a finite Pommaret basis, we derive new explicit formulas for the Hilbert series and for the degree of the ideal generated by it which exhibit more clearly the influence of each generator. Then we establish a new dimension depending Bezout bound for the degree and use it to obtain a dimension depending bound for the ideal membership problem.

A compact packing is a set of non-overlapping discs where all the holes between discs are curvilinear triangles. There is only one compact packing by discs of size $1$. There are exactly $9$ values of $r$ which allow a compact packing by discs of sizes $1$ and $r$. We prove here that there are exactly $164$ pairs $(r,s)$ allowing a compact packing by discs of sizes $1$, $r$ and $s$., Comment: code (SageMath) included

Discs form a compact packing of the plane if they are interior disjoint and the graph which connects the center of mutually tangent discs is triangulated. There is only one compact packing by discs all of the same size, called hexagonal compact packing. It has been previously proven that there are exactly $9$ values of $r$ such that there exists a compact packing with discs of radius $1$ and $r$. This paper shows that there are exactly $164$ pairs $(r,s)$ such that there exists a compact packing with discs of radius $1$, $r$ and $s$. In all these $164$ cases, there exists a periodic packing., Comment: In french

In this paper we consider the problem of computing all possible order ideals and also sets connected to 1, and the corresponding border bases, for the vanishing ideal of a given finite set of points. In this context two different approaches are discussed: based on the Buchberger-M\"oller Algorithm, we first propose a new algorithm to compute all possible order ideals and the corresponding border bases for an ideal of points. The second approach involves adapting the Farr-Gao Algorithm for finding all sets connected to 1, as well as the corresponding border bases, for an ideal of points. It should be noted that our algorithms are term ordering free. Therefore they can compute successfully all border bases for an ideal of points. Both proposed algorithms have been implemented and their efficiency is discussed via a set of benchmarks., Comment: 20 pages, 3 figures

In this paper, we describe improved algorithms to compute Janet and Pommaret bases. To this end, based on the method proposed by Moller et al., we present a more efficient variant of Gerdt's algorithm (than the algorithm presented by Gerdt-Hashemi-M.Alizadeh) to compute minimal involutive bases. Further, by using the involutive version of Hilbert driven technique, along with the new variant of Gerdt's algorithm, we modify the algorithm, given by Seiler, to compute a linear change of coordinates for a given homogeneous ideal so that the new ideal (after performing this change) possesses a finite Pommaret basis. All the proposed algorithms have been implemented in Maple and their efficiency is discussed via a set of benchmark polynomials., Comment: 15 pages, Computer Algebra in Scientific Computing (CASC 2016), Bucharest, Romania, 2016. Lecture Notes in Computer Science, Volume 9890, pages 58--72, 2016

We consider several notions of genericity appearing in algebraic geometry and commutative algebra. Special emphasis is put on various stability notions which are defined in a combinatorial manner and for which a number of equivalent algebraic characterisations are provided. It is shown that in characteristic zero the corresponding generic positions can be obtained with a simple deterministic algorithm. In positive characteristic, only adapted stable positions are reachable except for quasi-stability which is obtainable in any characteristic., Comment: 42 pages, to be published in Journal of Symbolic Computation, 2017

We improve certain degree bounds for Grobner bases of polynomial ideals in generic position. We work exclusively in deterministically verifiable and achievable generic positions of a combinatorial nature, namely either strongly stable position or quasi stable position. Furthermore, we exhibit new dimension- (and depth-)dependent upper bounds for the Castelnuovo-Mumford regularity and the degrees of the elements of the reduced Grobner basis (w.r.t. the degree reverse lexicographical ordering) of a homogeneous ideal in these positions., Comment: 8 pages, to be published in the proceedings of ISSAC'17

In this paper, we prove that every real analytic totally nondegenerate model CR manifold of length >= 3 has rigidity. This result was actually conjectured before by Valerii Beloshapka as the so-called "maximum conjecture". It follows that the transformation Lie group of all CR automorphisms associated with each of the mentioned models does not include any nonlinear map., Comment: Observing some problems in some certain part of the paper

We introduce a "workable" notion of degree for non-homogeneous polynomial ideals and formulate and prove ideal theoretic B\'ezout Inequalities for the sum of two ideals in terms of this notion of degree and the degree of generators. We compute probabilistically the degree of an equidimensional ideal.

We discuss the problem of determining reduction number of a polynomial ideal I in n variables. We present two algorithms based on parametric computations. The first one determines the absolute reduction number of I and requires computation in a polynomial ring with (n-dim(I))dim(I) parameters and n-dim(I) variables. The second one computes via a Grobner system the set of all reduction numbers of the ideal I and thus in particular also its big reduction number. However,it requires computations in a ring with n.dim(I) parameters and n variables., Comment: This new version replaces the earlier version arXiv:1404.1721 and it has been accepted for publication in the proceedings of CASC 2014, Warsaw, Polnad

Faugere's F5 algorithm is the fastest known algorithm to compute Groebner bases. It has a signature-based and an incremental structure that allow to apply the F5 criterion for deletion of unnecessary reductions. In this paper, we present an involutive completion algorithm which outputs a minimal involutive basis. Our completion algorithm has a nonincremental structure and in addition to the involutive form of Buchberger's criteria it applies the F5 criterion whenever this criterion is applicable in the course of completion to involution. In doing so, we use the G2V form of the F5 criterion developed by Gao, Guan and Volny IV. To compare the proposed algorithm, via a set of benchmarks, with the Gerdt-Blinkov involutive algorithm (which does not apply the F5 criterion) we use implementations of both algorithms done on the same platform in Maple., Comment: 24 pages, 2 figures

We consider the significant class of holomorphically nondegenerate CR manifolds of finite type that are represented by some weighted homogeneous polynomials and we derive some useful features which enable us to set up a fast effective algorithm to compute their Lie algebras of infinitesimal CR-automorphisms. This algorithm mainly relies upon a natural gradation of the sought Lie algebras, and it also consists in treating separately the related graded components. While some other methods are based on constructing and solving an associated pde systems which become time consuming as soon as the number of variables increases, the new method presented here is based on plain techniques of linear algebra. Furthermore, it benefits from a divide-and-conquer strategy to break down the computations into some simpler sub-computations. Moreover, we consider the new and effective concept of comprehensive Gr\"obner systems which provides us some powerful tools to treat the computations in the parametric cases. The designed algorithm is also implemented in the Maple software., Comment: The parametric case of computations is considered in the new version by means of the effective techniques of Comprehensive Groebner systems. Also, the designed algorithm is implemented in the Maple software

We perform detailed computations of Lie algebras of infinitesimal CR-automorphisms associated to three specific model real analytic CR-generic submanifolds in C^9 by employing differential algebra computer tools -- mostly within the Maple package DifferentialAlgebra -- in order to automate the handling of the arising highly complex linear systems of pde's. Before treating these new examples which prolong previous works of Beloshapka, of Shananina and of Mamai, we provide general formulas for the explicitation of the concerned pde systems that are valid in arbitrary codimension k >= 1 and in any CR dimension n >= 1. Also, we show how Ritt's reduction algorithm can be adapted to the case under interest, where the concerned pde systems admit so-called complex conjugations., Comment: 28 pages

In this paper, we consider parametric ideals and introduce a notion of comprehensive involutive system. This notion plays the same role in theory of involutive bases as the notion of comprehensive Groebner system in theory of Groebner bases. Given a parametric ideal, the space of parameters is decomposed into a finite set of cells. Each cell yields the corresponding involutive basis of the ideal for the values of parameters in that cell. Using the Gerdt-Blinkov algorithm for computing involutive bases and also the Montes algorithm for computing comprehensive Groebner systems, we present an algorithm for construction of comprehensive involutive systems. The proposed algorithm has been implemented in Maple, and we provide an illustrative example showing the step-by-step construction of comprehensive involutive system by our algorithm., Comment: 14 pages, to appear in Proc. of CASC 2012 (Maribor, Slovenia, September 3-5, 2012)

Quasi-stable ideals appear as leading ideals in the theory of Pommaret bases. We show that quasi-stable leading ideals share many of the properties of the generic initial ideal. In contrast to genericity, quasi-stability is a characteristic independent property that can be effectively verified. We also relate Pommaret bases to some invariants associated with local cohomology, exhibit the existence of linear quotients in Pommaret bases and prove some results on componentwise linear ideals., Comment: 13 pages, to appear in the proceedings of the CASC'12 conference (Maribor, Slovenia 2012)

Ihe first author presented an efficient algorithm for computing involutive (and reduced Groebner) bases. In this paper, we consider a modification of this algorithm which simplifies matters to understand it and to implement. We prove correctness and termination of the modified algorithm and also correctness of the used criteria. The proposed algorithm has been implemented in Maple. We present experimental comparison, via some examples, of performance of the modified algorithm with its original form which has been implemented in Maple too. In doing so, we have taken care to provide uniform implementation details for the both algorithms., Comment: 13 pages

This paper presents a new method to recover the relative pose between two images, using three points and the vertical direction information. The vertical direction can be determined in two ways: 1- using direct physical measurement like IMU (inertial measurement unit), 2- using vertical vanishing point. This knowledge of the vertical direction solves 2 unknowns among the 3 parameters of the relative rotation, so that only 3 homologous points are requested to position a couple of images. Rewriting the coplanarity equations leads to a simpler solution. The remaining unknowns resolution is performed by an algebraic method using Grobner bases. The elements necessary to build a specific algebraic solver are given in this paper, allowing for a real-time implementation. The results on real and synthetic data show the efficiency of this method.