Absolute polynomial factorization in two variables and the knapsack problem

ABSTRACT

A recent algorithmic procedure for computing the absolute factorization of a polynomial P(X,Y), after a linear change of coordinates, is via a factorization modulo X³. This was proposed by A. Galligo and D. Rupprecht in [7],[16]. Then absolute factorization is reduced to finding the minimal zero sum relations between a set of approximated numbers b;_i;, i =1 to n such that ∑ⁿ;_{i =1;} b;_i; =0, (see also [17]). Here this problem with an a priori exponential complexity, is efficiently solved for large degrees (n›100). We rely on LLL algorithm, used with a strategy of computation inspired by van Hoeij's treatment in [23]. For that purpose we prove a theorem on bounded integer relations between the numbers b;_i;,, also called linear traces in [19].

REFERENCES

• 1: G. Chèze and A. Galligo, From an approximate to an exact factorization. Submitted to JSC, 2003.
• 2: Robert M. Corless , André Galligo , Ilias S. Kotsireas , Stephen M. Watt, A geometric-numeric algorithm for absolute factorization of multivariate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.37-45, July 07-10, 2002, Lille, France [doi>10.1145/780506.780512]
• 3: Olivier Cormier , Michael F. Singer , Barry M. Trager , Felix Ulmer, Linear differential operators for polynomial equations, Journal of Symbolic Computation, v.34 n.5, p.355-398, November 2002 [doi>10.1006/jsco.2002.0564]
• 4: Dominique Duval, Absolute factorization of polynomials: a geometric approach, SIAM Journal on Computing, v.20 n.1, p.1-21, Feb. 1991 [doi>10.1137/0220001]
• 5: A. Edelman and E. Kostlan, How many zeros of a random polynomial are real?, Bull. Amer. Math. Soc. (N.S.), 32 (1995), pp. 1--37.
• 6: A. Galligo, Real factorization of multivariate polynomials with integer coefficients, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 258 (1999), pp. 60--70, 355.
• 7: André Galligo , David Rupprecht, Irreducible decomposition of curves, Journal of Symbolic Computation, v.33 n.5, p.661-677, May 2002 [doi>10.1006/jsco.2002.0528]
• 8: Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003 [doi>10.1090/S0025-5718-02-01428-X]
• 9: Jean-Christophe Hohl, Massively parallel search for linear factors in polynomials with many variables, Applied Mathematics and Computation, v.85 n.2-3, p.227-243, Sept. 1, 1997 [doi>10.1016/S0096-3003(96)00138-5]
• 10: M. Kac, On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc., 49 (1943), pp. 314--320.
• 11: E. Kaltofen, Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput., 14 (1985), pp. 469--489.
• 12: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 13: Erich Kaltofen, Effective Noether irreducibility forms and applications, Selected papers of the 23rd annual ACM symposium on Theory of computing, p.274-295, April 1995, New Orleans, Louisiana, United States
• 14: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), pp. 515--534.
• 15: K. Nagasaka and T. Sasaki, Approximate factorization of multivariable polynomials and its computational complexity, Sūrikaisekikenkyūsho Kōkyūroku, (1998), pp. 111--118. Research on the theory and applications of computer algebra (Japanese) (Kyoto, 1997).
• 16: D. Rupprecht, Elements de géométrie algébrique approchée: Etude du pgcd et de la factorisation, PhD thesis, Univ. Nice Sophia Antipolis, 2000.
• 17: Tateaki Sasaki, Approximate multivariate polynomial factorization based on zero-sum relations, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.284-291, July 2001, London, Ontario, Canada [doi>10.1145/384101.384139]
• 18: T. Sasaki, M. Suzuki, M. Kolář, and M. Sasaki, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Japan J. Indust. Appl. Math., 8 (1991), pp. 357--375.
• 19: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems, SIAM Journal on Numerical Analysis, v.40 n.6, p.2026-2046, 2002 [doi>10.1137/S0036142901397101]
• 20: --- height 2pt depth -1.6pt width 23pt, Numerical factorization of multivariate complex polynomials. Accepted for publication in a special issue of Theoretical Computer Science on Algebraic and Numerical Algorithms, 2003.
• 21: B. Trager, On the integration of algebraic functions, PhD thesis, M.I.T., 1985.
• 22: C. Traverso, A study on algebraic algorithms: the normalization, Rend. Sem. Mat. Univ. Politec. Torino, (1986), pp. 111--130 (1987). Conference on algebraic varieties of small dimension (Turin, 1985).
• 23: M. van Hoeij, Factoring polynomials and the knapsack problem, J. Number Theory, 95 (2002), pp. 167--189.
• 24: Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.0 GENERAL

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms

Keywords:
0-1 vectors, LLL algorithm, absolute factorization, knapsack problem