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
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
0.7988177537918091
0 references
0.7913133502006531
0 references
0.7815309762954712
0 references
0.7812358736991882
0 references
0.7780877351760864
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