Harmony of Gröbner Bases and the Modern Industrial Society

The following sections are included:

• PREFACE

• CONTENTS

In that paper, we recall the notion of the multidegree for D-modules, as exposed in a previous paper,² with a slight simplification. A particular emphasis is given on hypergeometric systems, used to provide interesting and computable examples.

Over the last decade, implementations of several desingularization algorithms have appeared in various contexts. These differ as widely in their methods and in their practical efficiency as they differ in the situations in which they may be applied. The purpose of this article is to give a brief overview over a selection of these approaches and the applicability of the respective implementations in Singular.

Let R = ℂ [x] be a polynomial ring with complex coefficients and D_X = ℂ〈x, ∂〉 be the Weyl algebra. Describing the localization R_f = R[f⁻¹] for nonzero f ∈ R as a D_X-module amounts to computing the annihilator A = Ann(f^a) ⊂ D_X of the cyclic generator f^a for a suitable negative integer a. We construct an iterative algorithm that uses truncated annihilators to build A for planar curves.

KNOPPIX/Math is a project to archive free mathematical software and documents and offer them on KNOPPIX, a Live Linux CD/DVD. KNOPPIX/Math provides a wonderful world of mathematical software systems.

The methodology of Markov basis initiated by Diaconis and Sturmfels¹ stimulated active research on Markov bases for more than ten years. It also motivated improvements of algorithms for Gröbner basis computation for toric ideals, such as those implemented in 4ti2.² However at present explicit forms of Markov bases are known only for some relatively simple models, such as the decomposable models of contingency tables. Furthermore general algorithms for Markov bases computation often fail to produce Markov bases even for moderate-sized models in a practical amount of time. Hence so far we could not perform exact tests based on Markov basis methodology for many important practical problems.

In this article we propose to use lattice bases for performing exact tests, in the case where Markov bases are not known. Computation of lattice bases is much easier than that of Markov bases. With many examples we show that the approach with lattice bases is practical. We also check that its performance is comparable to Markov bases for the problems where Markov bases are known.

We study the three-state toric homogeneous Markov chain model and three special cases of it, namely: (i) without parameters for the initial states, (ii) without self-loops, and (iii) when both cases are satisfied at the same time. Using a directed multigraph associated to the model, the state-graph, we give a bound on the number of vertices of the polytope associated to the model which does not depend on the time. Based on our computations, we also conjecture the stabilization of the f-vector of the polytope, analyze the normality of the semigroup, and give conjectural bounds on the degree of the Markov bases.

Here we introduce researchers in algebraic biology to the exciting new field of cophylogenetics. Cophylogenetics is the study of concomitantly evolving organisms (or genes), such as host and parasite species. Thus the natural objects of study in cophylogenetics are tuples of related trees, instead of individual trees. We review various research topics in algebraic statistics for phylogenetics, and propose analogs for cophylogenetics. In particular we propose spaces of cophylogenetic trees, cophylogenetic reconstruction, and cophylogenetic invariants. We conclude with open problems.

In this paper we give a review of the method of imsets introduced by Studený¹ from a geometric point of view. Elementary imsets span a polyhedral cone and its dual cone is the cone of supermodular functions. We review basic facts on the structure of these cones. Then we derive some new results on the following topics: i) extreme rays of the cone of standardized supermodular functions, ii) faces of the cones, iii) small relations among elementary imsets, and iv) some computational results on Markov basis for the toric ideal defined by elementary imsets.

Given finite simple graph one can associate the edge ideal. In this paper we discuss the non-vanishingness of the graded Betti numbers of edge ideals in terms of the original graph. In particular, we give a necessary and sufficient condition for a chordal graph on which the graded Betti number does not vanish and characterize the graded Betti number for a forest. Moreover we characterize the projective dimension for a chordal graph.

Let K be a closed convex polyhedron defined by a finite number of linear inequalities. In this paper we refine the theory of abstract tubes (Naiman and Wynn, 1997) associated with K when K is perturbed. In particular, we focus on the perturbation that is lexicographic and in an outer direction. An algorithm for constructing the abstract tube by means of linear programming and its implementation are discussed. Using the abstract tube for perturbed K combined with the recursive integration technique proposed by Miwa, Hayter and Kuriki (2003), we show that the multidimensional normal probability for a polyhedral region K can be computed efficiently. In addition, abstract tubes and the distribution functions of studentized range statistics are exhibited as numerical examples.

We give a new algorithm to compute inhomogeneous difference equations for a definite sum with parameters. The algorithm is based on the restriction algorithm for D-module by Oaku. Main tool in the algorithm is Gröbner basis method in the ring of differential operators.

We generalize the theory of A-hypergeometric systems for incomplete functions. We give a general algorithm on contiguity relations by utilizing Gröbner basis as well as a detailed study on incomplete Gauss and Lauricella hypergeometric functions.

We explain the details of the implementation of a primary decomposition package noro_pd.rr for Risa/Asir¹² which is a part of OpenXM package.¹³ A function noro_pd.syci_dec implements SYCI algorithm⁷ which is a variant of SY algorithm¹⁴ and it can efficiently decompose ideals with many embedded primary components. We also try parallelization of several parts of the algorithm and show the current performances of the implementation.

In this article we give a computational study of combinatorics of the discriminantal arrangements. The discriminantal arrangements are parametrized by two positive integers n and k such that n > k. The intersection lattice of the discriminantal arrangement with the parameter (n, k) is isomorphic to the intersection lattice of the hyperplane arrangement generated by n generic points in the d-dimensional vector space where d = n − k − 1. The combinatorics of the discriminantal arrangements is very hard, except for the special cases of the Boolean arrangements (k = 0) and the braid arrangements (k = 1). We review some results on the intersection lattices of the arrangements generated by generic points and use them to obtain some computational results on the characteristic polynomials of the discriminantal arrangements.

This is a survey of Gröbner bases of toric ideals. When we apply the theory of Gröbner bases of toric ideals to some problem, the computation of Gröbner bases tends to be rather expensive. In this paper, we give a collection of Gröbner bases and generators of toric ideals which is theoretically constructed. Such classes of Gröbner bases of toric ideals are useful to avoid the difficulty.

The purpose of this article is to introduce an example of statistical estimation based on conditional likelihood for stratified educational data. The example is based on the data that was presented in Ref. 2. The conditional likelihood estimation on stratified categorical data requires marginally constrained data enumeration, which is closely related to identifying Markov basis.

This is a review of current research in Markov chains as toric statistical models. Its content is a mixture of background information, results from the relevant recent literature, new results, and work in progress.

This paper is a survey of some of the main ideas in the algebraic analysis of system reliability. This approach uses tools from computational commutative algebra to compute and bound the reliability of coherent systems, an area with numerous applications in industry, engineering and networks.

In the previous paper, the author gave an irreducibility criterion for algebroid curve using the theory of affinoid algebra. In this paper, we give a simple proof of it in the case where the coefficient field is the complex number field.

The statistical task to learn graphical models of Bayesian network structure from data leads to the study of special polyhedra. In the paper, we offer an overview of our polyhedral approach to learning these statistical models. First, we report on the results on this topic from our recent papers. The second part of the paper brings some specific additional results inspired by this approach.

The following sections are included:

• AUTHOR INDEX