Algebraic and geometric reasoning using Dixon resultants

ABSTRACT

Dixon's method for computing multivariate resultants by simultaneously eliminating many variables is reviewed. The method is found to be quite restrictive because often the Dixon matrix is singular, and the Dixon resultant vanished identically yielding no information about solutions for many algebraic and geometry problems. We extend Dixon's method for the case when the Dixon matrix is singular, but satisfies a condition. An efficient algorithm is developed based on the proposed extension for extracting conditions for the existence of affine solutions of a finite set of polynomials. Using this algorithm, numerous geometric and algebraic identities are derived for examples which appear intractable with other techniques of triangulation such as the successive resultant method, the Gro¨bner basis method, Macaulay resultants and Characteristic set method. Experimental results suggest that the resultant of a set of polynomials which are symmetric in the variables is relatively easier to compute using the extended Dixon's method.

REFERENCES

• 1: Bayer D., Stillman M., Macaulay User's Manual, Cotnell University, Ithaca, NY.
• 2: B. Buchberger, GrSbner bases: An Algorithmic method in Polynomial Ideal theory, in Multidimensional Systems Theory, N.K. Bose, ed., D. Reidel Publishing Co., 184-232, 1985.
• 3: John Canny, Generalised characteristic polynomials, Journal of Symbolic Computation, v.9 n.3, p.241-250, March 1990 [doi>10.1016/S0747-7171(08)80012-0]
• 4: Cayley, A., On the theory of elimination. Cambridge and Dublin Mathematical Journal, III, 1865, 210-270.
• 5: Eng-wee Chionh, Base points, resultants, and the implicit representation of rational surfaces, University of Waterloo, Waterloo, Ont., Canada, 1990
• 6: S-C. Chou , X-S. Gao, Methods for mechanical geometry formula deriving, Proceedings of the international symposium on Symbolic and algebraic computation, p.265-270, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96946]
• 7: Dixon, A.L., The eliminant of three quantics in two independent variables. Proc. London Mathematical Society, 6, 1908, 468-478.
• 8: Gao, X.-S., Wang, D.-K., On the Automatic Derivation of a Set of Geometric Formulae. Mathematics Mechanization Research Preprints No. 8, 1992, 26-37, Academia Sinica, China.
• 9: Gerber, L., The Orthocentric Simplex as an Extreme Simplex. Pacific Journal of Mathematics 56, 1975, 97- 111.
• 10: Herstein, I. N., Topics in Algebra - Second Edition John Wiley & Sons, Inc., USA, 1975.
• 11: Heymann, W. Problem der Winkehalbierenden Ztschr. f. Math. and Phys. No. 35, 1890.
• 12: Kapur, D., Lakshman, Y., Elimination Methods: an Introduction. Symbolic and Numerical Computation for Artificial lntelligence Donald, Kaput and Mundy (eds.), Academic Press, 1992.
• 13: Dinesh Manocha, MultiPolynomial Resultant Algorithms, University of California at Berkeley, Berkeley, CA, 1991
• 14: W. Wu, On the decision Problem and the mechanization of theorem proving in elementary geometry, Scientia Sinica, 21, (1978), 150-172. Also in Bledsoe and Loveland, eds., Theorem Proving: After 25 years, Contemporary Mathematics, 29, 213-234. 1984.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices; Computations on polynomials
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Experimentation