Polar Varieties,Real Equation Solving,and Data Structures: The Hypersurface Case

In this paper we apply for the first time a new method for multivariate equation solving which was developed for complex root determination to therealcase. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem-adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in nonuniform sequential time that ispolynomialin the length of the input (given in straight-line program representation) and an adequately definedgeometric degree of the equation system.Replacing the notion of geometric degree of the given polynomial equation system by a suitably definedreal (or complex) degreeof certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

Representations of orthogonal polynomials

Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computers recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions.In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation.In this article we extend these results by presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible.The main technique is again to use explicit formulas for structural identities of the given polynomial systems.     

微分周形式与稀疏微分结式

代数周(Chow)形式和代数结式是代数几何的基本概念,同时还是消去理论的强大工具.一个自然的想法是在微分代数几何中发展相应的周形式和结式理论.但是由于微分结构的复杂性,在本文的研究工作之前,微分结式只有部分结果,而微分周形式与稀疏微分结式理论一直没有得到发展.本文的主要结果包括:第一,发展一般(generic)情形的微分相交理论,作为应用,证明一般情形的微分维数猜想.第二,初步建立微分周形式理论.对不可约微分代数簇定义微分周形式并证明其基本性质,特别地,给出微分周形式的Poisson分解公式,引入微分代数簇的主微分次数这一不变量并证明一类微分代数闭链的周簇和周坐标的存在性.作为应用,首次严格定义微分结式,证明其基本性质.第三,初步建立稀疏微分结式理论.引入Laurent微分本性系统的概念,定义稀疏微分结式,证明其基本性质,特别地,引入微分环面簇的概念,给出稀疏微分结式阶数和次数界的估计,并基于此给出计算稀疏微分结式的单指数时间算法.     

Estimates on the Distribution of the Condition Number of Singular Matrices

We exhibit some new techniques to study volumes of tubes about algebraic varieties in complex projective spaces. We prove the existence of relations between volumes and Intersection Theory in the presence of singularities. In particular, we can exhibit an average Bezout Equality for equidimensional varieties. We also state an upper bound for the volume of a tube about a projective variety. As a main outcome, we prove an upper bound estimate for the volume of the intersection of a tube with an equidimensional projective algebraic variety. We apply these techniques to exhibit upper bounds for the probability distribution of the generalized condition number of singular complex matrices.     

Complexity of solving parametric polynomial systems

In this paper, we present three algorithms: the first one solves zero-dimensional parametric homogeneous polynomial systems within single exponential time in the number n of unknowns; it decomposes the parameter space into a finite number of constructible sets and computes the finite number of solutions by parametric rational representations uniformly in each constructible set. The second algorithm factirizes absolutely multivariate parametic polynomials within single exponential time in n and in the upper bound d on the degree of the factorized polynomials. The third algorithm decomposes algebraic varieties defined by parametric polynomial systems of positive dimension into absolutely irreducible components uniformly in the values of the parameters. The complexity bound for this algorithm is double exponential in n. On the other hand, the lower bound on the complexity of the problem of resolution of parametric polynomial systems is double exponential in n. Bibliography: 72 titles.     

A Gröbner Free Alternative for Polynomial System Solving

Given a system of polynomial equations and inequations with coefficients in the field of rational numbers, we show how to compute a geometric resolution of the set of common roots of the system over the field of complex numbers. A geometric resolution consists of a primitive element of the algebraic extension defined by the set of roots, its minimal polynomial, and the parametrizations of the coordinates. Such a representation of the solutions has a long history which goes back to Leopold Kronecker and has been revisited many times in computer algebra. We introduce a new generation of probabilistic algorithms where all the computations use only univariate or bivariate polynomials. We give a new codification of the set of solutions of a positive dimensional algebraic variety relying on a new global version of Newton's iterator. Roughly speaking the complexity of our algorithm is polynomial in some kind of degree of the system, in its height, and linear in the complexity of evaluation of the system. We present our implementation in the Magma system which is called Kronecker in homage to his method for solving systems of polynomial equations. We show that the theoretical complexity of our algorithm is well reflected in practice and we exhibit some cases for which our program is more efficient than the other available software.     

On factoring parametric multivariate polynomials

This paper presents a new algorithm for the absolute factorization of parametric multivariate polynomials over the field of rational numbers. This algorithm decomposes the parameters space into a finite number of constructible sets. The absolutely irreducible factors of the input parametric polynomial are given uniformly in each constructible set. The algorithm is based on a parametric version of Hensel's lemma and an algorithm for quantifier elimination in the theory of algebraically closed field in order to reduce the problem of finding absolute irreducible factors to that of representing solutions of zero-dimensional parametric polynomial systems. The complexity of this algorithm is single exponential in the number n of the variables of the input polynomial, its degree d w.r.t. these variables and the number r of the parameters.     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

Computing polynomial univariate representations of zero-dimensional ideals by Grbner basis

Rational Univariate Representation(RUR) of zero-dimensional ideals is used to describe the zeros of zero-dimensional ideals and RUR has been studied extensively.In 1999,Roullier proposed an efficient algorithm to compute RUR of zero-dimensional ideals.In this paper,we will present a new algorithm to compute Polynomial Univariate Representation(PUR) of zero-dimensional ideals.The new algorithm is based on some interesting properties of Grbner basis.The new algorithm also provides a method for testing separating elements.     

Algorithms for checking rational roots of b-functions and their applications

The Bernstein–Sato polynomial of a hypersurface is an important object with many applications. However, its computation is hard, as a number of open questions and challenges indicate. In this paper we propose a family of algorithms called checkRoot for optimized checking whether a given rational number is a root of Bernstein–Sato polynomial and in the affirmative case, computing its multiplicity. These algorithms are used in the new approach to compute the global or local Bernstein–Sato polynomial and b-function of a holonomic ideal with respect to a weight vector. They can be applied in numerous situations, where a multiple of the Bernstein–Sato polynomial can be established. Namely, a multiple can be obtained by means of embedded resolution, for topologically equivalent singularities or using the formula of A?Campo and spectral numbers. We also present approaches to the logarithmic comparison problem and the intersection homology D-module. Several applications are presented as well as solutions to some challenges which were intractable with the classical methods. One of the main applications is the computation of a stratification of affine space with the local b-function being constant on each stratum. Notably, the algorithm we propose does not employ primary decomposition. Our results can be also applied for the computation of Bernstein–Sato polynomials for varieties. The examples in the paper have been computed with our implementation of the methods described in Singular:Plural.     

Solution of a stochastic Darcy equation by polynomial chaos expansion

This paper deals with solving a boundary value problem for the Darcy equation with a random hydraulic conductivity field.We use an approach based on polynomial chaos expansion in a probability space of input data.We use a probabilistic collocation method to calculate the coefficients of the polynomial chaos expansion. The computational complexity of this algorithm is determined by the order of the polynomial chaos expansion and the number of terms in the Karhunen–Loève expansion. We calculate various Eulerian and Lagrangian statistical characteristics of the flow by the conventional Monte Carlo and probabilistic collocation methods. Our calculations show a significant advantage of the probabilistic collocation method over the directMonte Carlo algorithm.     

Real zeros of the zero-dimensional parametric piecewise algebraic variety

The piecewise algebraic variety is the set of all common zeros of multivariate splines. We show that solving a parametric piecewise algebraic variety amounts to solve a finite number of parametric polynomial systems containing strict inequalities. With the regular decomposition of semi-algebraic systems and the partial cylindrical algebraic decomposition method, we give a method to compute the supremum of the number of torsion-free real zeros of a given zero-dimensional parametric piecewise algebraic variety, and to get distributions of the number of real zeros in every n-dimensional cell when the number reaches the supremum. This method also produces corresponding necessary and sufficient conditions for reaching the supremum and its distributions. We also present an algorithm to produce a necessary and sufficient condition for a given zero-dimensional parametric piecewise algebraic variety to have a given number of distinct torsion-free real zeros in every n-cell in the n-complex. This work was supported by National Natural Science Foundation of China (Grant Nos. 10271022, 60373093, 60533060), the Natural Science Foundation of Zhejiang Province (Grant No. Y7080068) and the Foundation of Department of Education of Zhejiang Province (Grant Nos. 20070628 and Y200802999)     

Intersection theory of incidence varieties and polygon spaces

In this paper smooth parameterizing spaces for polygons in projective space are introduced and their intersection theory is studied. In particular we give an expression for the Chow ring as a quotient of a polynomial ring. In addition the Chow cohomology rings of various incidence varieties are computed.     

Computation of differential Chow forms for ordinary prime differential ideals

In this paper, we propose algorithms for computing differential Chow forms for ordinary prime differential ideals which are given by characteristic sets. The algorithms are based on an optimal bound for the order of a prime differential ideal in terms of a characteristic set under an arbitrary ranking, which shows the Jacobi bound conjecture holds in this case. Apart from the order bound, we also give a degree bound for the differential Chow form. In addition, for a prime differential ideal given by a characteristic set under an orderly ranking, a much simpler algorithm is given to compute its differential Chow form. The computational complexity of the algorithms is single exponential in terms of the Jacobi number, the maximal degree of the differential polynomials in a characteristic set, and the number of variables.     

The multiplicative group action on singular varieties and Chow varieties

We answer two questions of Carrell on a singular complex projective variety admitting the multiplicative group action, one positively and the other negatively. The results are applied to Chow varieties and we obtain Chow groups of 0-cycles and Lawson homology groups of 1-cycles for Chow varieties. A brief survey on the structure of Chow varieties is included for comparison and completeness. Moreover, we give counterexamples to Shafarevich's problem on the rationality of the irreducible components of Chow varieties.     

Schubert cycles, differential forms and D-modules on varieties of unseparated flags

Proper homogeneous G-spaces (where G is semisimple algebraic group) over positive characteristic fields k can be divided into two classes, the first one being the flag varieties G/P and the second one consisting of varieties of unseparated flags (proper homogeneous spaces not isomorphic to flag varieties as algebraic varieties). In this paper we compute the Chow ring of varieites of unseparated flags, show that the Hodge cohomology of usual flag varieties extends to the general setting of proper homogeneous spaces and give an example showing (by geometric means) that the D -affinity of Beilinson and Bernstein fails for varieties of unseparated flags.