Factoring Rational Polynomials over the Complex Numbers (Q4032941)

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 165028
Language Label Description Also known as
default for all languages
No label defined
    English
    Factoring Rational Polynomials over the Complex Numbers
    scientific article; zbMATH DE number 165028

      Statements

      Factoring Rational Polynomials over the Complex Numbers (English)
      0 references
      0 references
      0 references
      0 references
      0 references
      17 May 1993
      0 references
      algorithms
      0 references
      multivariate polynomial
      0 references
      irreducible factors
      0 references
      deterministic NC algorithm
      0 references
      squarefree polynomial in two variables
      0 references
      The paper describes algorithms which are in NC, for determining the number and the degrees of the factors, irreducible over \(\mathbb{C}\), of a multivariate polynomial with coefficients in \(\mathbb{Q}\) and for approximating the irreducible factors. (NC is the class of functions which are computable by logspace-uniform Boolean circuits of polynomial size and of polylogarithmic depth.) The measures of size of the input polynomial are its degree, the coefficient length and the number \(n\) of variables. For fixed \(n\) a deterministic NC algorithm is given; if \(n\) is not fixed the algorithm to find the number and the degrees of the irreducible factors is random NC. To determine the number of irreducible factors the general case is reduced (via Bertini's theorem) to the case of a squarefree polynomial in two variables, and in this case the number of irreducible factors is determined by calculating the connectivity of a suitably constructed graph, using Sturm sequences. The approximation of the irreducible factors is based on a result of \textit{C. A. Neff} [Proc. 31st Ann. Sympos. Found. Comput. Sci., 152-162 (1990)] on finding zeros of polynomials in one variable in NC.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references