On the efficiency and optimality of Dixon-based resultant methods

ABSTRACT

Structural conditions on polynomial systems are developed for which the Dixon-based resultant methods often compute exact resultants. For cases when this cannot be done, the degree of the extraneous factor in the projection operator computed using the Dixon-based methods is typically minimal. A method for constructing a resultant matrix based on a combination of Sylvester-dialytic and Dixon methods is proposed. A heuristic for variable ordering for this construction often leading to exact resultants is developed.

REFERENCES

• 1: Laurent Busé , Mohamed Elkadi , Bernard Mourrain, Generalized resultants over unirational algebraic varieties, Journal of Symbolic Computation, v.29 n.4-5, p.515-526, April/May 2000 [doi>10.1006/jsco.1999.0304]
• 2: John F. Canny , Ioannis Z. Emiris, A subdivision-based algorithm for the sparse resultant, Journal of the ACM (JACM), v.47 n.3, p.417-451, May 2000 [doi>10.1145/337244.337247]
• 3: J. Cardinal and B. Mourrain. Algebraic approach of residues and applications. In J. Renegar, M. Shub, and S. Smale, editors, AMS-SIAM Summer Seminar on Math. of Numerical Analysis, Lectures in Applied Mathematics, volume 32, pages 189-210. Am. Math. Soc. Press, 1996.
• 4: Eng-Wee Chionh, Rectangular corner cutting and Dixon A -resultants, Journal of Symbolic Computation, v.31 n.6, p.651-669, June 2001 [doi>10.1006/jsco.2001.0448]
• 5: Arthur D. Chtcherba , Deepak Kapur, Conditions for exact resultants using the Dixon formulation, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.62-70, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345583]
• 6: A. D. Chtcherba and D. Kapur. Extracting sparse resultant matrices from Dixon resultant formultation. Proc. of 7th Rhine Workshop, pages 167-182, 2000.
• 7: A. D. Chtcherba and D. Kapur. A complete analysis of resultants and extraeneous factors for unmixed bivariate polynomial systems using the Dixon formulation. Proc. of 8th Rhine Workshop on Computer Algebra, Mar 2002.
• 8: A. D. Chtcherba and D. Kapur. Efficiency and optimality considerations of Dixon-based resultant method. Technical report, Computer Science Dept., Univ. of New Mexico, 2002.
• 9: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer-Verlag, New York, first edition, 1998.
• 10: A. Dixon. The eliminant of three quantics in two independent variables. Proc. London Mathematical Society, 6:468-478, 1908.
• 11: Ioannis Z. Emiris , Bernard Mourrain, Matrices in elimination theory, Journal of Symbolic Computation, v.28 n.1-2, p.3-44, July/Aug. 1999 [doi>10.1006/jsco.1998.0266]
• 12: I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhauser, Boston, first edition, 1994.
• 13: Computing invariants using elimination methods, Proceedings of the International Symposium on Computer Vision, p.97, November 21-23, 1995
• 14: Deepak Kapur , Tushar Saxena, Comparison of various multivariate resultant formulations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.187-194, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220370]
• 15: Deepak Kapur , Tushar Saxena, Sparsity considerations in Dixon resultants, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.184-191, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237862]
• 16: Deepak Kapur , Tushar Saxena, Extraneous factors in the Dixon resultant formulation, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.141-148, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258768]
• 17: Deepak Kapur , Tushar Saxena , Lu Yang, Algebraic and geometric reasoning using Dixon resultants, Proceedings of the international symposium on Symbolic and algebraic computation, p.99-107, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190372]
• 18: F. Macaulay. The algebric theory of modular systems. Cambridge Tracts in Math. and Math. Phys., 19, 1916.
• 19: Alexander Morgan , Andrew Sommese, A homotopy for solving general polynomial systems that respects m-homogenous structures, Applied Mathematics and Computation, v.24 n.2, p.101-113, Nov. 1987 [doi>10.1016/0096-3003(87)90063-4]
• 20: P. Pedersen and B. Sturmfels. Product formulas for Resultants and Chow forms. Math. Zeitschrift, 214:377-396, 1993.
• 21: Tushar Saxena, Efficient variable elimination using resultants, State University of New York at Albany, Albany, NY, 1997
• 22: Bernd Sturmfels, On the Newton Polytope of the Resultant, Journal of Algebraic Combinatorics: An International Journal, v.3 n.2, p.207-236, April 1994 [doi>10.1023/A:1022497624378]
• 23: J. Sylvester. On a theory of syzygetic relations of two rational integral functions, comprising an application to the theory of sturm's functions, and that of the greatest algebraic common measure. Philosophical Trans., 143:407-548, 1853.
• 24: Ming Zhang , Ron Goldman, Rectangular corner cutting and Sylvester A-resultants, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.301-308, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345659]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

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

General Terms:
Measurement

Keywords:
BKK bound, Bezoutians, Dixon method, Sylvester-type matrices, dialytic method, extraneous factor, multiplier matrices, resultant, support