Carles Checa
Ioannis Emiris
ABSTRACT
The Canny-Emiris formula [3] gives the sparse resultant as a ratio between the determinant of a Sylvester-type matrix and a minor of it, by a subdivision algorithm. The most complete proof of the formula was given by D'Andrea et al. in [9] under general conditions on the underlying mixed subdivision. Before the proof, Canny and Pedersen had proposed [5] a greedy algorithm which provides smaller matrices, in general. The goal of this paper is to give an explicit class of mixed subdivisions for the greedy approach such that the formula holds, and the dimensions of the matrices are reduced compared to the subdivision algorithm. We measure this reduction for the case when the Newton polytopes are zonotopes generated by n line segments (where n is the rank of the underlying lattice), and for the case of multihomogeneous systems. This article comes with a JULIA implementation of the treated cases.
- M. R. Bender, J.C. Faugere, A. Mantzaflaris, and E. Tsigaridas. 2021. Koszul-type determinantal formulas for families of mixed multilinear systems. SIAM Jrnl. on App. AG, 5, 4, 589--619. doi: 10.1137/20M1332190.Google Scholar
- M.R. Bender, J.-C. Faugère, and E. Tsigaridas. 2018. Towards mixed gröbner basis algorithms: the multihomogeneous and sparse case. ISSAC - 43rd Intern. Symp. on Symbolic & Algebraic Computation. doi: 10.1145/3208976.3209018. https: //hal.inria.fr/hal-01787423.Google ScholarDigital Library
- J.F. Canny and I.Z. Emiris. 1993. An efficient algorithm for the sparse mixed resultant. Appl. algebra, algebraic algor. & error-correcting codes, 673, 89--104.Google Scholar
- J.F. Canny and I.Z. Emiris. 1995. Efficient incremental algorithms for the sparse resultant and the mixed volume. Jour. Symb. Comput., 20, 117--149. doi: 10.1006/jsco.1995.1041.Google ScholarDigital Library
- J.F. Canny and P. Pedersen. 1993. An Algorithm for the Newton Resultant. Technical report. Cornell University, NY, USA.Google Scholar
- D. Cox, J. Little, and D. O'Shea. 2015. Using Algebraic Geometry. Volume 185. isbn: 0--387--20706--6. doi: 10.1007/b138611.Google Scholar
- C. D'Andrea. 2001. Macaulay style formulas for sparse resultants. Trans. AMS, 354, (August 2001). doi: 10.2307/3073009.Google Scholar
- C. D'Andrea and I.Z. Emiris. 2001. Computing sparse projection operators. Contemporary Mathematics, 286, 121--140.Google ScholarCross Ref
- C. D'Andrea, G. Jeronimo, and M. Sombra. 2020. The cannyemiris conjecture for the sparse resultant. CoRR, abs/2004.14622. arXiv: 2004.14622. https://arxiv.org/abs/2004.14622.Google Scholar
- C. D'Andrea and M. Sombra. 2015. A poisson formula for the sparse resultant. Proc. London Math. Society, 110, 4, 932--964. issn: 0024--6115. doi: 10.1112/plms/pdu069. http://dx.doi.org/10.1112/plms/pdu069.Google ScholarCross Ref
- A. Dickenstein and I.Z. Emiris. 2003. Multihomogeneous resultant formulae by means of complexes. Journal of Symbolic Computation, 36, 317--342. doi: 10.1016/S0747--7171(03)00086--5.Google ScholarCross Ref
- I. Emiris and A. Mantzaflaris. 2012. Multihomogeneous resultant formulae for systems with scaled support. J. Symbolic Computation, 820--842. doi: 10.1016/j.jsc.2011.12.010. https://hal.inria.fr/inria-00355881.Google ScholarDigital Library
- I.Z. Emiris and A. Rege. 1994. Monomial bases and polynomial system solving. Proc. Intern. Symp. Symbolic & Algebraic Computation, 114--122. M.A.H. MacCallum, editor. doi: 10. 1145/190347.190374. https://doi.org/10.1145/190347.190374.Google ScholarDigital Library
- M. Gelfand, M. Kapranov, and A. Zelevinsky. 1994. Discriminants, resultants, and multidimensional determinants. Birkhauser.Google Scholar
- F.S. Macaulay. 1903. Some formulae in elimination. Proc. Lond. Math. Soc. 35, 3--27.Google Scholar
- T. Michiels and R. Cools. 2000. Decomposing the secondary cayley polytope. Discrete and Computational Geometry, 23, 3, 367--380. issn: 1432-0444. doi: https://doi.org/10.1007/PL00009506.Google ScholarCross Ref
- R. P. Stanley. 2016. Smith normal form in combinatorics. Journal of Combinatorial Theory, Series A, 144, 476--495. Fifty Years of the Journal of Combinatorial Theory. issn: 0097--3165. doi: https://doi.org/10.1016/j.jcta.2016.06.013.Google ScholarDigital Library
- B. Sturmfels. 1994. On the Newton polytope of the resultant. J. Algebraic Combin., 3, 207--236.Google ScholarDigital Library
- B. Sturmfels and A. Zelevinsky. 1994. Multigraded resultants of sylvester type. Journal of Algebra, 163, 115--127.Google ScholarCross Ref
- G.M. Ziegler. 1995. Lectures on Polytopes. (1st edition). Number 152 in Grad Texts in Math. Springer, New York.Google Scholar
Index Terms
- A Greedy Approach to the Canny-Emiris Formula
Recommendations
The Canny–Emiris Conjecture for the Sparse Resultant
AbstractWe present a product formula for the initial parts of the sparse resultant associated with an arbitrary family of supports, generalizing a previous result by Sturmfels. This allows to compute the homogeneities and degrees of this sparse resultant, ...
Single-lifting Macaulay-type formulae of generalized unmixed sparse resultants
Resultants are defined in the sparse (or toric) context in order to exploit the structure of the polynomials as expressed by their Newton polytopes. Since determinantal formulae are not always possible, the most efficient general method for computing ...
Recurrence equations and their classical orthogonal polynomial solutions
Orthogonal systems and applicationsThe classical orthogonal polynomials are given as the polynomial solutions p"n(x) of the differential equation@s(x)y''(x)+@t(x)y^'(x)+@l"ny(x)=0,where @s(x) is a polynomial of at most second degree and @t(x) is a polynomial of first degree. In this ...
Comments