Search

We extend the theory and the algorithms of Border Bases to systems of Laurent polynomial equations, defining "toric" roots. Instead of introducing new variables and new relations to saturate by the variable inverses, we propose a more efficient approach which works directly with the variables and their inverse. We show that the commutation relations and the inversion relations characterize toric border bases. We explicitly describe the first syzygy module associated to a toric border basis in terms of these relations. Finally, a new border basis algorithm for Laurent polynomials is described and a proof of its termination is given for zero-dimensional toric ideals.

In this paper, we describe a new method to compute the minimum of a real polynomial function and the ideal defining the points which minimize this polynomial function, assuming that the minimizer ideal is zero-dimensional. Our method is a generalization of Lasserre relaxation method and stops in a finite number of steps. The proposed algorithm combines Border Basis, Moment Matrices and Semidefinite Programming. In the case where the minimum is reached at a finite number of points, it provides a border basis of the minimizer ideal., Comment: arXiv admin note: text overlap with arXiv:1112.3197

In this paper, we describe new methods to compute the radical (resp. real radical) of an ideal, assuming it complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While the border basis algorithms of [17] are efficient and numerically stable for computing complex roots, algorithms based on moment matrices [12] allow the incorporation of additional polynomials, e.g., to re- strict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gr\"obner bases. It thus combines the strength of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal.

This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one provided in [MT'05]. This general border basis algorithm weakens the monomial ordering requirement for \grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Gr\"obner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.

Let f1, ..., fs be a polynomial family in Q[X1,..., Xn] (with s less than n) of degree bounded by D. Suppose that f1, ..., fs generates a radical ideal, and defines a smooth algebraic variety V. Consider a projection P. We prove that the degree of the critical locus of P restricted to V is bounded by D^s(D-1)^(n-s) times binomial of n and n-s. This result is obtained in two steps. First the critical points of P restricted to V are characterized as projections of the solutions of Lagrange's system for which a bi-homogeneous structure is exhibited. Secondly we prove a bi-homogeneous B\'ezout Theorem, which bounds the sum of the degrees of the equidimensional components of the radical of an ideal generated by a bi-homogeneous polynomial family. This result is improved when f1,..., fs is a regular sequence. Moreover, we use Lagrange's system to design an algorithm computing at least one point in each connected component of a smooth real algebraic set. This algorithm generalizes, to the non equidimensional case, the one of Safey El Din and Schost. The evaluation of the output size of this algorithm gives new upper bounds on the first Betti number of a smooth real algebraic set. Finally, we estimate its arithmetic complexity and prove that in the worst cases it is polynomial in n, s, D^s(D-1)^(n-s) and the binomial of n and n-s, and the complexity of evaluation of f1,..., fs.