Algebraic factoring and rational function integration

ABSTRACT

This paper presents a new, simple, and efficient algorithm for factoring polynomials in several variables over an algebraic number field. The algorithm is then used iteratively, to construct the splitting field of a polynomial over the integers. Finally the factorization and splitting field algorithms are applied to the problem of determining the transcendental part of the integral of a rational function. In particular, a constructive procedure is given for finding the least degree extension field in which the integral can be expressed.

REFERENCES

• 1: George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
• 2: Gaal, L., Classical Galois Theory with Examples, Markham, Chicago, 1971, reprinted by Chelsea, New York.
• 3: Horowitz, E., Algorithms for Symbolic Integration of Rational Functions, Ph.D. Thesis, U. of Wisconsin, 1970.
• 4: Loos, R. G. K., "A Constructive Approach to Algebraic Numbers", Computer Science Dept., Stanford University, Palo Alto, Calif.
• 5: MacDuffee, C., An Introduction to Abstract Algebra, Dover, 1966.
• 6: Mack, D., On Rational Integration, Computer Science Dept., Utah Univ., UCP-38, 1975.
• 7: MACSYMA Reference Manual. Mathlab Group, Project MAC, M.I.T., Cambridge, Mass., November 1975.
• 8: Manove, M., Bloom, S., and Engelman, C., "Rational functions in MATHLAB", Proc. IFIP Conf. on Symbolic Manipulation Languages, Pisa, Italy, 1968.
• 9: Joel Moses, Symbolic integration: the stormy decade, Communications of the ACM, v.14 n.8, p.548-560, Aug. 1971 [doi>10.1145/362637.362651]
• 10: Tobey, R.G., Algorithms for Antidifferentiation of Rational Functions, Ph.D. Thesis, Harvard, 1967.
• 11: van der Waerden, B.L., Modern Algebra, vol 1, tr. Fred Blum, Frederick Ungar Publishing Co., New York, 1953.
• 12: Wang, P.S. and Rothschild, L.P., "Factoring Multivariate Polynomials Over the Integers," Mathematics of Computation, vol 29, no. 131, pp 935-950, 1975.
• 13: Wang, P.S., "Factoring Multivariate Polynomials over Algebraic Number Fields", Mathematics of Computation, vol. 30, no. 134, April 1976.
• 14: Wayl, Hermann, Algebraic Theory of Numbers, Princeton University Press, 1940.
• 15: Yun, D.Y.Y., The Hensel Lemma in Symbolic Manipulation, Ph.D. Thesis, M.I.T;, MAC TR-138, 1974.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.9 Integral Equations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory