Factoring Rational Polynomials over the Complex Numbers
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.
- Probabilistic absolute irreducibility test for polynomials
- Linear differential operators for polynomial equations
- Lifting and recombination techniques for absolute factorization
- Improved dense multivariate polynomial factorization algorithms
- A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
- scientific article; zbMATH DE number 6974151 (Why is no real title available?)
- Factoring multivariate polynomials via partial differential equations
- Rational solutions of Riccati-like partial differential equations
- Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
- Numerical factorization of multivariate complex polynomials
- On a generalization of Stickelberger's theorem
- Computing monodromy via continuation methods on random Riemann surfaces
This page was built for publication: Factoring Rational Polynomials over the Complex Numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4032941)