Syzygy modules of polynomial ideals are fundamental objects in commutative algebra and computational tools for basic properties of the ideals, for example their Betti numbers. In this paper we study the minimal generating sets of the syzygy modules of ladder determinantal ideals, which are ideals generated by minors from generic ladder matrices.

The determinantal ideal It is the ideal generated by all the t-minors of a generic matrix. With the minimal generators of the initial ideal of the product \(I_{t_1}\cdots I_{t_r}\) not explicitly known and its Gröbner basis computationally intractable, in this paper we study the degree bounds on the minimal generators of the initial ideal of \(I_{t_1}\cdots I_{t_r}\) and thus on the polynomials in its reduced Gröbner basis. Specifically, we show that an upper bound on the degrees of the minimal generators is \(t_1+\sum _{k=2}^{r}k(t_k-1)\) by analyzing the divisibility between monomials in the initial ideal via special functions applied to increasing decompositions of the monomials. For the special case of products IaIb of two determinantal ideals, we prove the existence of minimal generators of each degree between a + b and the presented upper bound and thus fully characterize the degrees of the polynomials in the reduced Gröbner bases of such products.

The problem of collision detection plays an important role in many fields of science and engineering. This article presents a collision detection method for general convex objects bounded by pieces of implicit surfaces. There are two key ideas that underlie our method: one is the introduction of a new kind of pseudodistance, called the$\delta$-distance, for implicitly represented convex objects which has the desired properties of convexity and square differentiability; the other is the use of$\delta$-distance functions to construct a virtual potential field in the real space, so that the problem of collision detection can be reduced to a problem of unconstrained convex optimization. The method is extended and applied to detect whether two objects collide when they are moving continuously along linearly translational trajectories, which is a special case of one of the continuous collision detection subproblems. We have implemented collision detection algorithms in C++ and conducted a large number of experiments, with test examples involving objects modeled by planar, quadric, superquadric, superellipsoidal, and hyperquadric surfaces, as well as pieces of them, in both stationary and linearly translational moving states. The experimental results show that our method has good performance and it is computationally efficient and widely applicable.

In this paper, we first introduce a new vertex order of graphs called the substrong elimination ordering based on maximal cliques of the graphs and prove that such an ordering can fully characterize strongly chordal graphs. By using this ordering we propose a new strategy for selecting polynomials for computation in algorithms for triangular decomposition over <?TeX $\mathbb {F}_2$?> Math 1 . Then we show that when this ordering is used as the variable order for triangular decomposition of a polynomial set whose associated graph is strongly chordal, the variables of any polynomial occurring in the decomposition are contained in certain maximal cliques, which gives a uniform description of the structural changes in the decomposition when combined with a bounded treewidth. Consequently, we prove that for any input set of ℓ polynomials in n variables with a strongly chordal associated graph of treewidth m, the complexity for triangular decomposition over <?TeX $\mathbb {F}_2$?> Math 2 with the proposed selection strategy is <?TeX $O \left(4^m \ell n \left(\frac{m\ell }{n-1} \right)^{n-1} \right)$?> Math 3 , smaller than the original O(ℓn) when m ≪ n.

Many biological systems are modeled mathematically as dynamic systems in the form of polynomial or rational differential equations. In this paper we apply sparse triangular decomposition to compute the equilibria of biological dynamic systems by exploiting the inherent sparsity of parameter-free systems via the chordal graph and by constructing suitable elimination orderings for parametric systems using the newly introduced block chordal graph. Our experiments with parameter-free systems provide practical information on suitable algorithms for chordal completion and verify the performance gains of sparse triangular decomposition against the ordinary one in the settings of computation of the equilibria. Then we establish full characterizations of block chordal graphs and propose algorithms for testing block chordality and constructing minimal block chordal completions. Based on these results, which are of their own merits in graph theory, we present a new algorithm of sparse triangular decomposition for parametric systems and apply it to detect the equilibria of parametric biological dynamic systems, with remarkable speedups against ordinary triangular decomposition verified by the experiments.

This paper presents an algorithm that decomposes an arbitrary set F of multivariate polynomials involving parameters into finitely many sets Γi of (lexicographical) Gröbner bases G ij such that associated with each Γi there is a system Ai of parametric constraints, all the Ai's partition the parameter space, all the Gij's in each Γi remain Gröbner bases under specialization of the parameters satisfying the constraints in Ai, and for each i the Gröbner bases Gij together with their corresponding W-characteristic sets form a normal characteristic decomposition of F. The sets of Gröbner bases computed by the algorithm provide a comprehensive characteristic decomposition of F that is structure-invariant under the associated constraints and possesses many algebraic and geometric properties, including most of the notable properties on comprehensive Gröbner systems and comprehensive triangular decomposition. Some of these properties are highlighted in the paper and advantages of the proposed algorithm are discussed briefly from the aspects of methodological simplicity and computational performance using illustrative examples and preliminary experiments.

In this paper we extend existing theoretical results on chordal graphs in algebraic triangular decomposition in top-down style to the ordinary differential case. We first propose the concept of differential associated graph of an ordinary differential polynomial set, and then for two typical algorithms in top-down style for ordinary differential triangular decomposition based on the pseudo-division and subresultant regular subchain respectively, we prove that when the input differential polynomial set has a chordal differential associated graph G and one perfect elimination ordering of G is used, the differential associated graph of any polynomial set in the decomposition process by these two algorithms is a subgraph of G.

In this paper the chordal graph structures of polynomial sets appearing in triangular decomposition in top-down style are studied when the input polynomial set has a chordal associated graph. We prove that the associated graph of one specific triangular set computed in any algorithm for triangular decomposition in top-down style is a subgraph of the chordal graph of the input polynomial set and that all the polynomial sets, including all the computed triangular sets, appearing in one specific algorithm for triangular decomposition in top-down style (Wang's method) have associated graphs which are subgraphs of the chordal graph of the input polynomial set.

Let I in K[x1,...,xn] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Gröbner bases of I is crucial in polynomial system solving. Through the algorithm FGLM, this task is classically tackled by linear algebra operations in K[x1,...,n]/I. With recent progress on Gröbner bases computations, this step turns out to be the bottleneck of the whole solving process.