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. R. Corless, A. Galligo, I. Kotsireas, and S. Watt, A geometric-numeric algorithm for factoring multivariate polynomials, in Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC 2002), T. Mora, ed., ACM, 2002, pp. 37--45.]]
3. O. Cormier, M. F. Singer, B. M. Trager, and F. Ulmer, Linear differential operators for polynomial equations, J. Symbolic Comput., 34 (2002), pp. 355--398.]]
4. D. Duval, Absolute factorization of polynomials: a geometric approach, SIAM J. Comput., 20 (1991), pp. 1--21.]]
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. A. Galligo and D. Rupprecht, Irreducible decomposition of curves, J. Symbolic Comput., 33 (2002), pp. 661--677. Computer algebra (London, ON, 2001).]]
8. S. Gao, Factoring multivariate polynomials via partial differential equations, Math. Comp., 72 (2003), pp. 801--822 (electronic).]]
9. J.-C. Hohl, Massively parallel search for linear factors in polynomials with many variables, Appl. Math. Comput., 85 (1997), pp. 227--243.]]
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. --- height 2pt depth -1.6pt width 23pt, Polynomial factorization 1987--1991, in LATIN '92 (São Paulo, 1992), vol. 583 of Lecture Notes in Comput. Sci., Springer, Berlin, 1992, pp. 294--313.]]
13. --- height 2pt depth -1.6pt width 23pt, Effective Noether irreducibility forms and applications, J. Comput. System Sci., 50 (1995), pp. 274--295. 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991).]]
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. T. Sasaki, Approximate multivariate polynomial factorization based on zero-sum relations, in Proceedings of the 2001 International Symposium on Symbolic and Algebraic Computation (ISSAC 2001), B. Mourrain, ed., ACM, 2001, pp. 284--291.]]
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. A. Sommese, J. Verschelde, and C. Wampler, Symmetric functions applied to decomposing solution sets of polynomial systems, SIAM J. Numer. Anal., 40 (2002), pp. 2026--2046.]]
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. J. von zur Gathen, Irreducibility of multivariate polynomials, J. Comput. System Sci., 31 (1985), pp. 225--264.]]

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

• Mathematics of computing