# A prolongation–projection algorithm for computing the finite real variety of an ideal

Author(s):M. Laurent, J.B. Lasserre, Ph. Rostalski |
Conference/Journal:Theoretical Computer Science, vol. 410, no. 27-29, pp. 2685-2700, Keywords: Real solving; Finite real variety; Numerical algebraic geometry; Semidefinite optimization |

Abstract:We provide a real algebraic symbolic–numeric algorithm for computing the real variety V_R(I) of an ideal I, assuming V_R(I) is finite (while complex variety V(I) could be infinite). Our approach uses sets of linear functionals on (R[x])^*, vanishing on a given set of polynomials generating I and their prolongations up to a given degree, as well as on polynomials of the real radical ideal sqrt[R]{I} obtained from the kernel of a suitably defined moment matrix assumed to be positive semidefinite and of maximum rank. We formulate a condition on the dimensions of projections of these sets of linear functionals, which serves as a stopping criterion for our algorithm; this new criterion is satisfied earlier than the previously used stopping criterion based on a rank condition for moment matrices. This algorithm is based on standard numerical linear algebra routines and semidefinite optimization and combines techniques from previous work of the authors together with an existing algorithm for the complex variety. | Year:2009 |

Type of Publication:(01)Article | |

Supervisor: | |

File Download:Request a copy of this publication. (Uses JavaScript) | |

% Autogenerated BibTeX entry @Article { LauLas:2009:IFA_3306, author={M. Laurent and J.B. Lasserre and Ph. Rostalski}, title={{A prolongation–projection algorithm for computing the finite real variety of an ideal}}, journal={Theoretical Computer Science}, year={2009}, volume={410}, number={27-29}, pages={2685--2700}, month=jul, url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=3306} } | |

Permanent link |