Search

Abstract: The aim of the paper is to demonstrate the superiority of Cartan’s method over direct methods based on differential elimination for handling otherwise intractable equivalence problems. In this sense, using our implementation of Cartan’s method, we establish two new equivalence results. We establish when a system of second order ODEs is equivalent to flat system (second derivations are zero), and when a system of holomorphic PDEs with two independent variables and one dependent variable is flat. We consider the problem of finding transformation that brings a given equation to the target one. We shall see that this problem becomes algebraic when the symmetry pseudogroup of the target equation is zerodimensional. We avoid the swelling of the expressions, by using non-commutative derivations adapted to the problem. [Copyright &y& Elsevier]

Abstract: The Gröbner walk is an algorithm for conversion between Gröbner bases for different term orders. It is based on the polyhedral geometry of the Gröbner fan and involves tracking a line between cones representing the initial and target term order. An important parameter is the explicit numerical perturbation of this line. This usually involves both time and space, demanding arithmetic of integers much larger than the input numbers. In this paper we show how the explicit line may be replaced by a formal line using Robbiano’s characterization of group orders on . This gives rise to the generic Gröbner walk involving only Gröbner basis conversion over facets and computations with marked polynomials. The infinite precision integer arithmetic is replaced by term order comparisons between (small) integral vectors. This makes it possible to compute with infinitesimal numbers and perturbations in a consistent way without introducing unnecessary long integers. The proposed technique is closely related to the lexicographic (symbolic) perturbation method used in optimization and computational geometry. We report on an implementation of our algorithm specifically tailored to computations with lattice ideals. [Copyright &y& Elsevier]

Abstract: In this paper a new algorithm for computing the intersection of two rational ruled surfaces, given in parametric/parametric or implicit/parametric form, is presented. This problem can be considered as a quantifier elimination problem over the reals with an additional geometric flavor which is one of the central themes in V. Weispfenning research. After the implicitization of one of the surfaces, the intersection problem is reduced to finding the zero set of a bivariate equation which represents the parameter values of the intersection curve, as a subset of the other surface. The algorithm, which involves both symbolic and numerical computations, determines the topology of the intersection curve as an intermediate step and eliminates extraneous solutions that might arise in the implicitization process. [Copyright &y& Elsevier]

In this paper we study plane conic geometry, particularly different representations of geometric constructions and relations in plane conic geometry, with Cayley and bracket algebras. We propose three powerful simplification techniques for bracket computation involving conic points, and an algorithm for rational Cayley factorization in conic geometry. The factorization algorithm is not a general one, but works for all the examples tried so far. We establish a series of elimination rules for various geometric constructions based on the idea of bracket-oriented representation and elimination, and an algorithm for optimal representation of the conclusion in theorem proving. These techniques can be used in any applications involving brackets and conics. In theorem proving, our algorithm based on these techniques can produce extremely short proofs for difficult theorems in conic geometry. [Copyright &y& Elsevier]