×

Moment matrices, border bases and real radical computation. (English) Zbl 1276.13021

Some new methods are described to compute the radical (resp. real radical) of an ideal, assuming its 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 B. Mourrain and P. Trébuchet [Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation, 253–260 (2005)] are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (see J.-B. Lasserre, M. Laurent and P. Rostalski [Found. Comput. Math. 8, No. 5, 607–647 (2008; Zbl 1176.14010)]) allow the incorporation of additional polynomials, e.g., to restrict 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öbner 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.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
16N80 General radicals and associative rings
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
13P15 Solving polynomial systems; resultants

Citations:

Zbl 1176.14010

Software:

ISOLATE
PDFBibTeX XMLCite
Full Text: DOI arXiv