No label defined (Q3973349)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 16663
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 16663 |
Statements
26 June 1992
0 references
real roots
0 references
polynomial complexity
0 references
zero dimensional ideal
0 references
0.8343775272369385
0 references
0.8164209127426147
0 references
[For the entire collection see Zbl 0721.00009.] This paper analyzes the complexity of the determination of the signs taken by a polynomial at the real points of a zero dimensional subset of the affine \(n\)-space, already given by a triangular system of polynomial equations \(f_ i\) in \(X_ 1,\ldots,X_ i\) for \(i)1,\ldots,n\). The thesis is that the mathematically significant parameter, with respect to which the complexity has to be estimated, is the dimension \(D\) (as a vector space) of the quotient by the ideal (\(f_ 1,\ldots,f_ n\)). It is shown that the straightforward recursive algorithm has an asymptotic complexity which is not polynomial in \(D\) (it is \(d^{O(n^ 2)}\), where \(d\) is the maximal degree of the \(f_ i\)). But a more elaborate algorithm is given, which has an asymptotic complexity polynomial in \(D\); the key of the amelioration is that it involves only computations with polynomials in two variables at each step. Since this paper, the revival of Hermite's method (computation of the signature of the bilinear form on the quotient given by the trace composed with the multiplication, when a Gröbner basis is given) has opened an easier and more general way for this problem. See \textit{E. Becker} and \textit{T. Wörman} [On the trace formula for quadratic forms and some applications, to appear in the Proceedings of th Special Year in Real Algebraic Geometry and Quadratic Forms, Univ. of California at Berkeley]and \textit{P. Pedersen}, \textit{M.-F. Roy} and \textit{A. Szpirglas} [Counting Real Zeros in the Multivariate Case, to appear in the Proceedings of MEGA 92, Nice].
0 references