Complexity of finding irreducible components of a semialgebraic set
type: Item
instance of: scholarly article
title: Complexity of finding irreducible components of a semialgebraic set
zbMATH Open document ID: 0821.14037
published in: Journal of Complexity
publication date: 1995-04-05T00:00:00Z
review text: Let \(W \subset \mathbb{R}^ n\) be a semialgebraic set determined by a Boolean combination of \(k\) atomic subformulas of the form \(f > 0\) or \(f = 0\), where the polynomials \(f \in \mathbb{Z} [X_ 1, \dots, X_ n]\), the degrees \(\deg_{X_ 1, \dots, X_ n} (f) < d\), and the maxima of bit lengths of coefficients \(l(f) < M\) for \(d\), \(M \in \mathbb{N}\). The author proposes an algorithm for producing the complexification, the Zariski closure and for finding all irreducible components of \(W\). An upper bound for the running time is \(M^{0(1)} (kd)^{n^{0(1)}}\). The procedure is applied to computing a Whitney system for a semialgebraic set and the real radical of a polynomial ideal.
Mathematics Subject Classification ID: 14Q99
Mathematics Subject Classification ID: 14P10
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 741001
zbMATH Keywords: semialgebraic set
zbMATH Keywords: algorithm
zbMATH Keywords: complexification
zbMATH Keywords: Zariski closure
zbMATH Keywords: irreducible components
author: André Galligo
author: Nicolai Vorobjov
MaRDI profile type: Publication
full work available at URL: jcom.1995.1007
OpenAlex ID: W2094402074
DOI: 10.1006/JCOM.1995.1007
description: scientific article; zbMATH DE number 741001