Factoring rational polynomials over the complexes

ABSTRACT

We give NC algorithms for determining the number and degrees of the absolute factors (factors irreducible over the complex numbers C) of a multi-variate polynomial with rational coefficients. NC is the class of functions computable by logspace-uniform Boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree d, coefficient length c, number of variables n, and for sparse polynomials, the number of non-zero coefficients s. For the general case, we give a random (Monte-Carlo) NC algorithm in these input measures. If n is fixed, or if the polynomial is dense, we give a deterministic NC algorithm. The algorithm also works in random NC for polynomials represented by straight-line programs, provided the polynomial can be evaluated at integer points in NC. Finally, we discuss a method for obtaining an approximation to the coefficients of each factor whose running time is polynomial in the size of the original (dense) polynomial. These methods rely on the fact that the connected components of a complex hypersurface P(z1…,zn) = 0 minus its singular points correspond to the absolute factors of P.

REFERENCES

• Borodin 82: Borodin, A., yon zur Gathen, J. and Hopcroft, J. (1982), "Fast parallel matrix and GCD computations," Inf. end Contr., Vol. 52, pp. 241- 256.
• Canny 87: Canny, 2. (1987), "A New Algebraic Method for Robot Motion Planning and Real Geometry," ~3'th Symposium on Foundations of Computer Science, pp. 39-48.
• Canny 88: John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
• Chistov 83: Chistov, A.L., and Grigoryev, D.Y. (1983), "Subexponential-Time Solving Systems of Algebraic Equations I.," Steklov institute, LOMI preprint E-9-83.
• Davenport 81: James H. Davenport , Barry M. Trager, Factorization over finitely generated fields, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.200-205, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806396]
• DiCrescenzo 84: Claire Dicrescenzo , Dominique Duval, Computations on Curves, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.100-107, July 09-11, 1984
• Duval 87: Duval,D. (1987), Diverses questions relatives au Calcul Formal A v~c Des Nombres Algebriques, Th~se, L'Universit~ Scientifique, Technologique et M ddicale de Grenoble.
• Dvornicich 87: Dvornicich , R., and Traverso, C., (1987) "Newton Symmetric Functions and the Arithmetic of Algebraically Closed Fields", Univ. of Pisa, Manuscript.
• von zur Gathen 83: yon zur Gathen, J. (1983), "Factoring Sparse Multivariate Polynomials," Proc. IEEE Syrup. FOGS, pp. 172-179.
• Griffiths 78: Griffiths, P. and Harris, J. (1978), Principles of Algebraic Geometry, John Wiley and Sons
• Hartshorne 77: Hartshorne, R. (1977), Algebraic Geometry, Springer-Verlag.
• Heintz 81: Joos Heintz , Malte Sieveking, Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.16-28, July 13-17, 1981
• Henrici 88: Peter Henrici , William R. Kenan, Applied & computational complex analysis: power series integration conformal mapping location of zero, John Wiley & Sons, Inc., New York, NY, 1988
• Kaltofen 85a: Erich Kaltofen, Fast parallel absolute irreducibility testing, Journal of Symbolic Computation, v.1 n.1, p.57-68, March 1985 [doi>10.1016/S0747-7171(85)80029-8]
• Kaltofen 85b: Kaltofen, E. (1985), "Polynomial- Time Reductions from Multivariate to B i- and U nivariate Integral Polynomial Factorization," SIAM J. Computing, Vol. 14, pp. 469-489.
• Kaltofen 85c: Kaltofen, E. (1985), "Effective Hilbert Irreducibility," In/. and Contr., Vol. 66, No. 3, pp. 123-137.
• Lenstra 82: Lenstra, A., Lenstra, H. and Lovasz, L. (1982), "Factoring Polynomials with rational coefficients," Math. Ann., Vol. 261, pp. 515-534.
• Mumford 1970: Mumford, D. (1970), Algebraic Geometry I: Complex Projective Varieties, Springer-Verlag.
• Noether 22: Noether, E. (1922), "Ein algebraisches Kriterium fur absolute Irreduzibilitat," Math. Ann., Vol. 85, pp. 26-33.
• Pan 85: Pan, V. (1985), "Fast and Efficient Algorithms for Sequential Evaluation of Polynomial Zeroes and of Matrix Polynomials," 26th IEEE Symposium on Foundations of Computer Science.
• Schwartz 80: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• Shafarevich 74: Shafarevich, I. (1974), Basic Algebraic Geometry, Springer Verlag.
• Valiant 83: Valiant, L. G., Skyum, S., Berkowitz, S., and Rackoff, C., (1983), "Fast Parallel Computation of Polynomials Using Few Processors," SIAM J. Comp., Vol. 12, No. 4, pp. 641-644.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Mechanical theorem proving

General Terms:
Algorithms, Measurement, Theory, Verification