Conditions for determinantal formula for resultant of a polynomial system

ABSTRACT

Matrices constructed from a parameterized multivariate polynomial system are analyzed to ensure that such a matrix contains a condition for the polynomial system to have common solutions irrespective of whether its parameters are specialized or not. Such matrices include resultant matrices constructed using well-known methods for computing resultants over projective, toric and affine varieties. Conditions on these matrices are identified under which the determinant of a maximal minor of such a matrix is a nontrivial multiple of the resultant over a given variety. This condition on matrices allows a generalization of a linear algebra construction, called rank submatrix, for extracting resultants from singular resultant matrices, as proposed by Kapur, Saxena and Yang in ISSAC'94. This construction has been found crucial for computing resultants of non-generic, specialized multivariate polynomial systems that arise in practical applications. The new condition makes the rank submatrix construction based on maximal minor more widely applicable by not requiring that the singular resultant matrix have a column independent of the remaining columns. Unlike perturbation methods, which require introducing a new variable, rank submatrix construction is faster and effective. Properties and conditions on symbolic matrices constructed from a polynomial system are discussed so that the resultant can be computed as a factor of the determinant of a maximal non-singular submatrix.

REFERENCES

• 1: Franck Aries , Rachid Senoussi, An implicitization algorithm for rational surfaces with no base points, Journal of Symbolic Computation, v.31 n.4, p.357-365, April 1, 2001 [doi>10.1006/jsco.1999.0436]
• 2: 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]
• 3: L. Busè, M. Elkadi, and B. Mourrain. Resultant over the residual of a complete intersection. Journal of Pure and Applied Algebra, 164(1-2):35--57, 2001.
• 4: L. Busè, M. Elkadi, and B. Mourrain. Using projection operators in computer aided geometric design. In Topics in Algebraic Geometry and Geometric Modeling, volume 334 of Contemporary Mathematics, pages 321--342. American Mathematical Society, 2003.
• 5: 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]
• 6: M. Chardin. Multivariate subresultants. J. Pure and Appl. Alg., 101:129--138, 1995.
• 7: Arthur D. Chtcherba , Deepak Kapur, A new sylvester-type resultant method based on the dixon-bezout formulation, 2003
• 8: A. D. Chtcherba and D. Kapur. A Combinatorial Perspective on Constructing Dialytic Resultant Matrices. Proc. of 10th Rhine Workshop (RCWA'06), pages 67--81, 2006.
• 9: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer-Verlag, New York, first edition, 1998.
• 10: Carlos D'Andrea , Ioannis Z. Emiris, Hybrid sparse resultant matrices for bivariate polynomials, Journal of Symbolic Computation, v.33 n.5, p.587-608, May 2002 [doi>10.1006/jsco.2002.0524]
• 11: A. Dixon. The eliminant of three quantics in two independent variables. Proc. London Mathematical Society, 6:468--478, 1908.
• 12: Ioannis Zacharias Emiris, Sparse elimination and applications in kinematics, University of California at Berkeley, Berkeley, CA, 1994
• 13: Ioannis Z. Emiris , John F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, Journal of Symbolic Computation, v.20 n.2, p.117-149, Aug. 1995 [doi>10.1006/jsco.1995.1041]
• 14: 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]
• 15: I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhauser, Boston, first edition, 1994.
• 16: Hoon Hong , Richard Liska , Stanly Steinberg, Testing stability by quantifier elimination, Journal of Symbolic Computation, v.24 n.2, p.161-187, August 1997 [doi>10.1006/jsco.1997.0121]
• 17: J. Jouanolou. Le formalisme du résultant. Adv. in Math., 90:117--263, 1991.
• 18: 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]
• 19: Amit Khetan, The resultant of an unmixed bivariate system, Journal of Symbolic Computation, v.36 n.3-4, p.425-442, September 2003 [doi>10.1016/S0747-7171(03)00089-0]
• 20: Dinesh Manocha , John F. Canny, Implicit representation of rational parametric surfaces, Journal of Symbolic Computation, v.13 n.5, p.485-510, May 1992
• 21: P.Pedersen and B. Sturmfels. Product formulas for resultants and chow forms. Math. Zeitschrift, 214:377--396, 1993.
• 22: Tushar Saxena, Efficient variable elimination using resultants, State University of New York at Albany, Albany, NY, 1997
• 23: Igor R. Shafarevich , Miles Reid, Basic algebraic geometry 1 (2nd, revised and expanded ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 24: J. Zheng, T. W. Sederberg, E.-W. Chionh, and D. A. Cox. Implicitizing rational surfaces with base points using the method of moving surfaces. In Topics in Algebraic Geometry and Geometric Modeling, volume 334 of Contemporary Mathematics, pages 151--168. American Mathematical Society, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Theory

Keywords:
Bézoutian, Dixon, dialytic, rank submatrix construction, resultant, resultant matrix