An Artificial Intelligence Approach to the Symbolic Factorization of Multivariable Polynomials

A new heuristic factorization scheme that uses learning to improve the efficiency of determining the symbolic factorization of multivariable polynomials with integer coefficients and an arbitrary number of variables and terms is described. The factorization scheme makes extensive use of Artificial Intelligence techniques, e.g. model-building, learning, and automatic classification in an attempt to reduce the amount of searching for the irreducible factors of a polynomial. The approach taken to polynomial factorization is quite different from previous attempts because: (1) it is distinct from numerial techniques, (2) possibilities for terms in a factor are generated from the terms in the polynomial, and (3) a reclassification technique is used to allow the application of different sets of heuristics to a polynomial during factorization attempts on it. Tables are presented that demonstrate the importance of learning to the efficiency of operation of the scheme. Factorizat5.on times of polynomials factored by both the scheme described in this paper and Wang's implementation of Berlekamp's algorithm are given and compared and an analysis of variance experiment provides an indication of the significant sources of variation influencing the factorization time.