Moment Matrices, Border Bases and Real Radical Computation

Jean-Bernard Lasserre 1 Monique Laurent 2 Bernard Mourrain 3 Philipp Rostalski 4 Philippe Trébuchet 5
1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
LAAS - Laboratoire d'analyse et d'architecture des systèmes
3 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
5 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00651759
Contributor : Bernard Mourrain <>
Submitted on : Wednesday, December 14, 2011 - 10:26:04 AM
Last modification on : Friday, January 10, 2020 - 9:10:08 PM
Long-term archiving on: Thursday, March 15, 2012 - 2:26:21 AM

Files

paper-hal.pdf
Files produced by the author(s)

Identifiers

Citation

Jean-Bernard Lasserre, Monique Laurent, Bernard Mourrain, Philipp Rostalski, Philippe Trébuchet. Moment Matrices, Border Bases and Real Radical Computation. Journal of Symbolic Computation, Elsevier, 2013, 51, pp.63-85. ⟨10.1016/j.jsc.2012.03.007⟩. ⟨hal-00651759⟩

Share

Metrics

Record views

886

Files downloads

548