Sylvester-type matrices for sparse resultants
DOI:
https://doi.org/10.11113/mjfas.v6n1.173Keywords:
multihomogeneous polynomial systems, optimal Sylvester-type matrices, sparse resultant matrix,Abstract
The resultant matrix of a polynomial system depends on the geometry of its input Newton polytopes. Therefore for sparse inputs, the matrix is lower in dimension. The aim of the study is to infer conditions on the class of polynomial systems that can give a resultant matrix whose size is minimized, that is an optimal or Sylvester-type sparse resultant matrix. From the work of Emiris, the ‘incremental algorithm’ has been claimed to produce optimal matrices for the class of multi-homogeneous (or multigraded) systems of special structure. Cyclic polynomial systems for n-root problems also fall under this classification. We have applied the Maple multires package to obtain Sylvester-type matrices for some examples. The ultimate aim of the study is to verify whether the multigraded systems constitute to the only class of polynomial systems that can give sparse resultant optimal matrix; hence giving a necessary and sufficient condition for producing exact sparse resultants.
References
J. F. Canny, The Complexity of Robot Motion Planning, doctoral dissertation, (1993), MIT, Cambridge, Mass.
J. F. Canny, and I. Z. Emiris, In Proceeding of AAECC, In Lect. Notes in Comp. Science, Berlin, Springer-Verlag, (1993) 89 – 104.
J. F. Canny, and P. Pederson, Tech. Report 1394, (1993), Computer Science Department, Cornell University.
J. F. Canny, and I. Z. Emiris, Journal of the ACM, Vol. 47, 3, (2000) 417 – 451.
E. W. Chionh, R. Goldman, and M. Zhang, In Proc. 8th IMA Conf. Math. Of Surfaces, (1998) 193 – 212.
A. D. Chtcherba, A New Sylvester-type Resultant Method based on the Dixon-Bezout Formulation, Ph.D Thesis, Computer Science, University of
New Mexico, New Mexico, (2003).
A. D. Chtcherba, and D. Kapur, In Proceedings of ISSAC,2002, Lille, France.
D. Cox, J. Little, and D. O’Shea, Using Algebraic Geometry. in Graduate Texts in Mathematics, Springer-Verlag, New York, 185 (1998).
R. M. Corless, P. M. Gianni, and B. M. Trager, Proceedings of ISSAC, New York, ACM Press, (1997) 133 – 140.
C. D’Andrea, and I. Z. Emiris, Proceedings of ISSAC’01, Ontario, Canada. ACM Press, (2001) 24 – 31.
A. Dickenstein, and I. Z. Emiris, ISSAC, Lille, France, ACM Press,(2002) 46 – 54.
I. Z. Emiris, Sparse Elimination and Applications in Kinematics, Doctoral Thesis, Computer Science Division, University of California., Berkeley,
I. Z. Emiris, and J. F. Canny, J. Symbolic Computation, 20(2) (1995) 117-149.
I. Z. Emiris, and V. Y. Pan, In proceed ACM ISSAC’97, Hawaii, July 21-21, ACM New York, (1997) 189 – 196.
I. Z. Emiris, and B. Mourrain, Journal of Symbolic Computation, 28(1-2) (1999) 3-43.
I. Z. Emiris, and A. Mantzaflaris, Technical Report 355881, INRIA, Sophia-Antipolis, France, (2009).
I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinski, Math.Theory Appl., Birkhauser, Boston, (1994).
D. Kapur, and T. Saxena, ISSAC’95 Montreal Canada, ACM, (1995) 187 – 194.
T. Saxena. Efficient variable elimination using resultants, Doctoral Thesis, Computer Science Department, State University of New York.,
Albany., College of art and sciences, (1997).
B. Sturmfels, B. “Sparse Elimination Theory”, In Computation Algebraic Geometry and Commut. Algebra, D. Eisenbud and L. Robbiano, eds.,
Cortona, Italy. Proc, Symp. Math. Xxxiv, June (1991) 264 – 298.
M. Zhang, Topics in Resultants and Implicitization. PhD thesis, Dept. Comp. Science, Rice University, Houston, Texas, 2000.
M. Zhang, and R.Goldman. Proc of the ISSAC, St Andrews, Scotland. ACM Press, (2000).
