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

      0 references
      0 references
      26 June 1992
      0 references
      real roots
      0 references
      polynomial complexity
      0 references
      zero dimensional ideal
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references