Moment matrices, border bases and radical computation

J.B. Lasserre, M. Laurent, B. Mourrain, P. Rostalski, P. Trébuchet

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper, we describe new methods 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 Mourrain and Trébuchet (2005) are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (Lasserre et al., 2008) 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.
Original languageEnglish
Pages (from-to)63-85
JournalJournal of Symbolic Computation
Volume51
Issue numberApril 2013
Early online date4 Jul 2012
DOIs
Publication statusPublished - 2013

Fingerprint

Moment Matrix
Polynomials
Dual Method
Real Roots
Semidefinite Programming
Polynomial equation
Multiple Solutions
Quotient
Eliminate
Roots
Polynomial
Computing

Cite this

Lasserre, J. B., Laurent, M., Mourrain, B., Rostalski, P., & Trébuchet, P. (2013). Moment matrices, border bases and radical computation. Journal of Symbolic Computation, 51(April 2013), 63-85. https://doi.org/10.1016/j.jsc.2012.03.007
Lasserre, J.B. ; Laurent, M. ; Mourrain, B. ; Rostalski, P. ; Trébuchet, P. / Moment matrices, border bases and radical computation. In: Journal of Symbolic Computation. 2013 ; Vol. 51, No. April 2013. pp. 63-85.
@article{28f7492074d54fd4847e0f90e183268e,
title = "Moment matrices, border bases and radical computation",
abstract = "In this paper, we describe new methods 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 Mourrain and Tr{\'e}buchet (2005) are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (Lasserre et al., 2008) 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{\"o}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.",
author = "J.B. Lasserre and M. Laurent and B. Mourrain and P. Rostalski and P. Tr{\'e}buchet",
year = "2013",
doi = "10.1016/j.jsc.2012.03.007",
language = "English",
volume = "51",
pages = "63--85",
journal = "Journal of Symbolic Computation",
issn = "0747-7171",
publisher = "Academic Press Inc.",
number = "April 2013",

}

Lasserre, JB, Laurent, M, Mourrain, B, Rostalski, P & Trébuchet, P 2013, 'Moment matrices, border bases and radical computation', Journal of Symbolic Computation, vol. 51, no. April 2013, pp. 63-85. https://doi.org/10.1016/j.jsc.2012.03.007

Moment matrices, border bases and radical computation. / Lasserre, J.B.; Laurent, M.; Mourrain, B.; Rostalski, P.; Trébuchet, P.

In: Journal of Symbolic Computation, Vol. 51, No. April 2013, 2013, p. 63-85.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Moment matrices, border bases and radical computation

AU - Lasserre, J.B.

AU - Laurent, M.

AU - Mourrain, B.

AU - Rostalski, P.

AU - Trébuchet, P.

PY - 2013

Y1 - 2013

N2 - In this paper, we describe new methods 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 Mourrain and Trébuchet (2005) are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (Lasserre et al., 2008) 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.

AB - In this paper, we describe new methods 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 Mourrain and Trébuchet (2005) are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (Lasserre et al., 2008) 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.

U2 - 10.1016/j.jsc.2012.03.007

DO - 10.1016/j.jsc.2012.03.007

M3 - Article

VL - 51

SP - 63

EP - 85

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

SN - 0747-7171

IS - April 2013

ER -