Search

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Gröbner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo–Mumford regularity. [ABSTRACT FROM AUTHOR]

The isotropic Grassmannian parametrizes isotropic subspaces of a vector space equipped with a quadratic form. In this paper, we show that any maximal isotropic Grassmannian in its Plücker embedding can be defined by pulling back the equations of G r iso (3 , 7) or G r iso (4 , 8). [ABSTRACT FROM AUTHOR]

Staged trees or coloured probability tree models are statistical models coding conditional independence between events depicted in a tree graph. They include the very important class of Bayesian networks as a special case and provide a straightforward graphical tool for handling additional context-specific relationships. In this paper, we study the algebraic properties of their ideal of model invariants. We hereby find that the tree also provides a straightforward combinatorial tool to generalise the existing geometric characterisation of decomposable graphical models and Bayesian networks. In particular, from a staged tree we can directly understand the interplay between local and global sum-to-one conditions, read the generators of that ideal, and determine conditions under which the model is a toric variety intersected with the probability simplex. [ABSTRACT FROM AUTHOR]

Abstract This paper provides new equivalence theorems for regular chains and regular differential chains, which are generalizations of Ritt's characteristic sets. These theorems focus on regularity properties of elements of residue class rings defined by these chains, which are revealed by resultant computations. New corollaries to these theorems have quite simple formulations. [ABSTRACT FROM AUTHOR]

Abstract: In many theorem proving applications, a proper treatment of equational theories or equality is mandatory. In this paper, we show how to integrate a modern treatment of equality in the Model Evolution calculus (), a first-order version of the propositional DPLL procedure. The new calculus, , is a proper extension of the calculus without equality. Like it maintains an explicit candidate model, which is searched for by DPLL-style splitting. For equational reasoning uses an adapted version of the superposition inference rule, where equations used for superposition are drawn (only) from the candidate model. The calculus also features a generic, semantically justified simplification rule which covers many simplification techniques known from superposition-style theorem proving. Our main theoretical result is the correctness of the calculus in the presence of very general redundancy elimination criteria. We also describe our implementation of the calculus, the E-Darwin system, and we report on practical experiments with it on the TPTP problem library. [Copyright &y& Elsevier]

Abstract: Multiobjective discrete programming is a well-known family of optimization problems with a large spectrum of applications. The linear case has been tackled by many authors during the past few years. However, the polynomial case has not been studied in detail due to its theoretical and computational difficulties. This paper presents an algebraic approach for solving these problems. We propose a methodology based on transforming the polynomial optimization problem to the problem of solving one or more systems of polynomial equations and we use certain Gröbner bases to solve these systems. Different transformations give different methodologies that are theoretically stated and compared by some computational tests via the algorithms that they induce. [Copyright &y& Elsevier]

Abstract: A Reed–Solomon code of length can be list decoded using the well-known Guruswami–Sudan algorithm. By a result of the interpolation part in this algorithm can be done in complexity , where denotes the designed list size and the multiplicity parameter. The parameters and are sometimes considered to be constants in the complexity analysis, but for high rate Reed–Solomon codes, their values can be very large. In this paper we will combine ideas from and the concept of key equations to get an algorithm that has complexity . This compares favorably to the complexities of other known interpolation algorithms. [Copyright &y& Elsevier]

Abstract: In this paper we deal with the verification of safety properties of infinite-state systems modeled by term rewriting systems. An over-approximation of the set of reachable terms of a term rewriting system is obtained by automatically constructing a finite tree automaton. The construction is parameterized by a set of equations on terms, and we also show that the approximating automata recognize at most the set of -reachable terms. Finally, we present some experiments carried out with the implementation of our algorithm. In particular, we show how some approximations from the literature can be defined using equational approximations. [Copyright &y& Elsevier]

Abstract: A canal surface is an envelope of a one-parameter family of spheres. In this paper we present an efficient algorithm for computing the implicit equation of a canal surface generated by a rational family of spheres. By using Laguerre and Lie geometries, we relate the equation of the canal surface to the equation of a dual variety of a certain curve in 5-dimensional projective space. We define the -basis for arbitrary dimension and give a simple algorithm for its computation. This is then applied to the dual variety, which allows us to deduce the implicit equations of the dual variety, the canal surface and any offset to the canal surface. [Copyright &y& Elsevier]

Abstract: Triangular decompositions for systems of polynomial equations with variables, with exact coefficients, are well developed theoretically and in terms of implemented algorithms in computer algebra systems. However there is much less research concerning triangular decompositions for systems with approximate coefficients. In this paper we discuss the zero-dimensional case of systems having finitely many roots. Our methods depend on having approximations for all the roots, and these are provided by the homotopy continuation methods of Sommese, Verschelde and Wampler. We introduce approximate equiprojectable decompositions for such systems, which represent a generalization of the recently developed analogous concept for exact systems. We demonstrate experimentally the favorable computational features of this new approach, and give a statistical analysis of its error. [Copyright &y& Elsevier]

Abstract: Elimination is a classical subject. The problem is algorithmically solvable by using resultants or by one calculation of Groebner basis with respect to an elimination term order. However, there is no existing method that is both efficient and reliable enough for applicable size problems, say implicitization of bi-cubic Bezier surfaces with degree six in five variables. This basic and useful operation in computer aided geometric design and geometric modeling defies a solution even when approximation using floating-point or modular coefficients is used for Groebner basis computation. An elimination term order can be used to eliminate for any ideal in . However, for most practical problems we are given a fixed ideal, which means that an elimination term order may be too much for our calculation. In this paper, the author proposes a new approach for elimination. Instead of using a classical elimination term order for all problems or ideals as usual, the author proposes to use algebraic structures of the given system of equations for finding more suitable term orders for elimination of the given problem only. Experimental results showed that these ideal-specific term orders are much more efficient for elimination. In particular, when ideal specific term orders for elimination are used with Groebner walk conversion, one can completely avoid all perturbations. This is a significant result because researchers have been struggling with how to perturb basis conversions for a long time. [Copyright &y& Elsevier]

Abstract: In statistical inference, mixture models consisting of several component subpopulations are used widely to model data drawn from heterogeneous sources. In this paper, we consider maximum likelihood estimation for mixture models in which the only unknown parameters are the component proportions. By applying the theory of multivariable polynomial equations, we derive bounds for the number of isolated roots of the corresponding system of likelihood equations. If the component densities belong to certain familiar continuous exponential families, including the multivariate normal or gamma distributions, then our upper bound is, almost surely, the exact number of solutions. [Copyright &y& Elsevier]

Abstract: Let be a field and a finite directed multi-graph. The focus of this paper is to offer a complete description of all path algebras and admissible orders with the property that all of their finitely generated ideals have finite Gröbner bases and of those which contain a finitely generated ideal whose Gröbner bases are all infinite. [Copyright &y& Elsevier]

This paper presents a simple method for converting rational parametric equations of curves and surfaces into implicit equations. The method proceeds via writing out the implicit polynomial F of estimated degree with indeterminate coefficients ui, substituting the rational expressions for the given parametric curve or surface into F to yield a rational expression g/h in the parameter s (or s and t), equating the coefficients of g in terms of s (and t) to 0 to generate a sparse, partially triangular system of linear equations in ui with constant coefficients, and finally solving the linear system for ui. If a nontrivial solution is found, then an implicit polynomial is obtained; otherwise, one repeats the same process, increasing the degree of F. Our experiments show that this simple method is efficient. It performs particularly well in the presence of base points and may detect the dependency of parameters incidentally. [Copyright &y& Elsevier]

This paper proposes a new symbolic method for solving a class of higher-order equations with an unknown function over the complex domain. Our method exploits the closure property of group structure (for functions) in order to allow an equivalent system of equations to be expressed and solved in the first-order setting.Our work is an initial step towards the relatively unexplored realm of higher-order constraint solving, in general; and higher-order equational solving, in particular. We shall provide some theoretical background for the proposed method, and also prototype an implementation under Mathematica. [Copyright &y& Elsevier]

The μ-basis of a rational ruled surface P(s,t)=P0(s)+tP1(s) is defined in Chen et al. (Comput. Aided Geom. Design 18 (2001) 61) to consist of two polynomials p(x,y,z,s) and q(x,y,z,s) that are linear in x, y, z. It is shown there that the resultant of p and q with respect to s gives the implicit equation of the rational ruled surface; however, the parametric equation P(s,t) of the rational ruled surface cannot be recovered from p and q. Furthermore, the μ-basis thus defined for a rational ruled surface does not possess many nice properties that hold for the μ-basis of a rational planar curve (Comput. Aided Geom. Design 18 (1998) 803). In this paper, we introduce another polynomial r(x,y,z,s,t) that is linear in x, y, z and t such that p, q, r can be used to recover the parametric equation P(s,t) of the rational ruled surface; hence, we redefine the μ-basis to consist of the three polynomials p, q, r. We present an efficient algorithm for computing the newly-defined μ-basis, and derive some of its properties. In particular, we show that the new μ-basis serves as a basis for both the moving plane module and the moving plane ideal corresponding to the rational ruled surface. [Copyright &y& Elsevier]