On square-free decomposition algorithms

ABSTRACT

In this paper, we will give three different (including revamped versions of Horowitz's and Musser's) algorithms for computing the SQFR decomposition of polynomials in R[x]. Some algorithm analysis will be carried out to show the (asymptotic) superiority of the algorithm we propose (last of the three).

REFERENCES

• 1: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 2: W. S. Brown, On computing with factored rational expressions, ACM SIGSAM Bulletin, v.8 n.3, p.26-34, August 1974 [doi>10.1145/1086837.1086842]
• 3: B. F. Caviness , R. J. Fateman, Simplification of radical expressions, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.329-338, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806352]
• 4: R. J. Fateman, ESSAYS IN ALGEBRAIC SIMPLIFICATION, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 5: Griesmer, J.H., Jenks, R.D., and Yun, D.Y.Y., "SCRATCHPAD User's Manual", IBM T.J. Watson Research Center Report - RA70, June 1975.
• 6: Hall, A.D., "Factored Rational Expressions in ALTRAN", Proceeding of EUROSAM '74, pp. 35-45.
• 7: Hensel, K., Zahlentheorie, Goschen, Berlin and Leipzig, 1913.
• 8: Horowitz, E., "Algorithms for Symbolic Integration of Rational Functions", Ph.D. Thesis, Computer Science Dept., University of Wisconsin, 1969.
• 9: Ellis Horowitz, Algorithms for partial fraction decomposition and rational function integration, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.441-457, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806314]
• 10: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 11: MACSYMA User's Manual, Bogen, R., et al., Project MAC, M.I.T., Cambridge, Mass., 1973.
• 12: Moses, J., "Symbolic Integration", MAC-TR-47, Project MAC, M.I.T., Dec., 1967.
• 13: Joel Moses, Symbolic integration the stormy decade, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.427-440, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806313]
• 14: David Rea Musser, Algorithms for polynomial factorization., 1971
• 15: Joel Moses , David Y. Y. Yun, The EZ GCD algorithm, Proceedings of the annual conference, p.159-166, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805698]
• 16: Miola, A. and Yun, D.Y.Y., "The Computational Aspects of Hensel-type Univariate Polynomial Greatest Common Divisor Algorithms", Proc. EUROSAM '74, Aug. 1974, pp. 46-54.
• 17: Proc. of the Second Symposium on Symbolic and Algebraic Manipulation, Petrick, S.R., ed., ACM, March 1971.
• 18: Risch, R., "The Problem of Integration in Finite Terms", Trans. AMS, Vol. 139, May 1969, pp. 167-189.
• 19: Tobey, R.G., "Algorithms for Antidifferentiation of Rational Functions", Ph.D. Thesis, Harvard, 1967.
• 20: Wang, P.S. and Rothschild, L.P., "Factoring Multivariate Polynomials over the Integers", Math. of Comp. Vol. 29, No. 131, July 1975, pp. 935-950.
• 21: Yun, D.Y.Y., "The Hensel Lemma in Algebraic Manipulation", Ph.D. Thesis, Dept. of Math. MAC-TR-138, M.I.T., Nov. 1974.
• 22: Yun, D.Y.Y., "Hensel Meets Newton—Algebraic Construction in an Analytic Setting", Analytic Computational Complexity, Proc. of CMU Symposium, Traub, J., ed., Academic Press, April 1975.
• 23: Yun, D.Y.Y., "P-adic Constructions and its Applications in Algebraic Manipulation", these proceedings.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

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

General Terms:
Algorithms, Theory