Sparse Resultant under Vanishing Coefficients
Manfred Minimair
DOI: 10.1023/A:1025169426299
Abstract
The main question of this paper is: What happens to the sparse ( toric) resultant under vanishing coefficients? More precisely, let f 1,..., f n be sparse Laurent polynomials with supports A 1,..., A n A 1 
A 1. Naturally a question arises: Is the sparse resultant of f 1, f 2,..., f n with respect to the supports A 1, A 2,..., A n in any way related to the sparse resultant of f 1, f 2,..., f n with respect to the supports A 1, A 2,..., A n ? The main contribution of this paper is to provide an answer. The answer is important for applications with perturbed data where very small coefficients arise as well as when one computes resultants with respect to some fixed supports, not necessarily the supports of the f i's, in order to speed up computations. This work extends some work by Sturmfels on sparse resultant under vanishing coefficients. We also state a corollary on the sparse resultant under powering of variables which generalizes a theorem for Dixon resultant by Kapur and Saxena. We also state a lemma of independent interest generalizing Pedersen's and Sturmfels' Poisson-type product formula.
A 1. Naturally a question arises: Is the sparse resultant of f 1, f 2,..., f n with respect to the supports A 1, A 2,..., A n in any way related to the sparse resultant of f 1, f 2,..., f n with respect to the supports A 1, A 2,..., A n ? The main contribution of this paper is to provide an answer. The answer is important for applications with perturbed data where very small coefficients arise as well as when one computes resultants with respect to some fixed supports, not necessarily the supports of the f i's, in order to speed up computations. This work extends some work by Sturmfels on sparse resultant under vanishing coefficients. We also state a corollary on the sparse resultant under powering of variables which generalizes a theorem for Dixon resultant by Kapur and Saxena. We also state a lemma of independent interest generalizing Pedersen's and Sturmfels' Poisson-type product formula.Pages: 53–73
Keywords: elimination theory; resultant; product formula; Newton polytope
Full Text: PDF
References
1. L. Busé, M. Elkadi, and B. Mourrain, “Generalized resultants over unirational algebraic varieties,” J. Symbolic Computation 29(4/5) (2000), 515-526.
2. J. Canny and I. Emiris, “A subdivision-based algorithm for the sparse resultant,” J. ACM 47(3) (2000), 417- 451.
3. J. Canny, E. Kaltofen, and Y. Lakshman, “Solving systems of non-linear polynomial equations faster,” in Proc. ACM-SIGSAM 1989 Internat. Symp. Symbolic Algebraic Comput. ISSAC'89, ACM, 1989, pp. 121- 128.
4. E. Cattani, A. Dickenstein, and B. Sturmfels, “Residues and resultants,” J. Math. Sci. Univ. Tokyo 5(1) (1998), 119-148.
5. A. Cayley, “On the theory of elimination,” Cambridge and Dublin Math. J. 3 (1848), 116-120.
6. M. Chardin, “Contributions `a l'alg`ebre commutative effective et `a la théorie de l'élimination,” PhD thesis, Université Paris VI, 1990.
7. C.C. Cheng, J.H. McKay, and S.S. Wang, “A chain rule for multivariable resultants,” Proceedings of the American Mathematical Society 123(4) (1995), 1037-1047.
8. D. Cox, J. Little, and D. O'Shea, Using Algebraic Geometry, Springer Verlag, New York, Berlin, Heidelberg, 1998.
9. C. D'Andrea and A. Dickenstein, “Explicit formulas for the multivariate resultant,” Pure Appl. Algebra 164(1/2) (2001), 59-86.
10. A.-L. Dixon, “The eliminant of three quantics in two independent variables,” Proc. London Math. Soc. 7(49/69) (1908), 473-492.
11. I. Emiris and V. Pan, “The structure of sparse resultant matrices,” in Proc. Int. Symp. on Symbolic and Algebraic Computation (ISSAC), ACM Press, 1997.
12. I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkh\ddot auser, Boston, 1994.
13. L. Gonzáles-Vega, “Une théorie des sous-résultants pour les polyn\hat omes en plusieurs variables,” C.R. Acad. Sci. Paris Sér. I Math., 313(13) (1991), 905-908.
14. H. Hong and M. Minimair, “Sparse resultant of composed polynomials I,” J. Symbolic Computation 33 (2002), 447-465.
15. J.P. Jouanolou, “Le formalisme du résultant,” Adv. Math. 90(2) (1991), 117-263.
16. D. Kapur and T. Saxena, “Sparsity considerations in Dixon resultants,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), ACM, New York, 1996, pp. 184-191.
17. D. Kapur and T. Saxena, “Extraneous factors in the Dixon resultant formulation,” in Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (Kihei, HI), ACM New York, 1997, pp. 141-148.
18. R. Lewis and P. Stiller, “Solving the recognition problem for six lines using the Dixon resultant,” Math. Comput. Simulation 49(3) (1999), 205-219.
19. F.S. Macaulay, The Algebraic Theory of Modular Systems, Cambridge Mathematical Library, 1916.
20. D. Manocha and J. Canny, “Multipolynomial resultant algorithms,” J. Symbolic Computation 15(2) (1993), 99-122.
21. M. Minimair, “Dense resultant of composed polynomials,” Accepted by J. Symbolic Computation in November 2002.
22. G. Nakos and R.M. Williams, “Eliminiation with the Dixon resultant,” Mathematica for Education and Research 6(3) (1997), 11-21.
23. P. Pedersen and B. Sturmfels, “Product formulas for resultants and Chow forms,” Mathematische Zeitschrift 214 (1993), 377-396.
24. J.M. Rojas, “Solving degenerate sparse polynomial systems faster,” J. Symbolic Computation 28(1/2) (1999), 155-186. Special Issue Polynomial Elimination-Algorithms and Applications.
25. B. Sturmfels, “On the Newton polytope of the resultant,” Journal of Algebraic Combinatorics 3 (1994), 207-236.
2. J. Canny and I. Emiris, “A subdivision-based algorithm for the sparse resultant,” J. ACM 47(3) (2000), 417- 451.
3. J. Canny, E. Kaltofen, and Y. Lakshman, “Solving systems of non-linear polynomial equations faster,” in Proc. ACM-SIGSAM 1989 Internat. Symp. Symbolic Algebraic Comput. ISSAC'89, ACM, 1989, pp. 121- 128.
4. E. Cattani, A. Dickenstein, and B. Sturmfels, “Residues and resultants,” J. Math. Sci. Univ. Tokyo 5(1) (1998), 119-148.
5. A. Cayley, “On the theory of elimination,” Cambridge and Dublin Math. J. 3 (1848), 116-120.
6. M. Chardin, “Contributions `a l'alg`ebre commutative effective et `a la théorie de l'élimination,” PhD thesis, Université Paris VI, 1990.
7. C.C. Cheng, J.H. McKay, and S.S. Wang, “A chain rule for multivariable resultants,” Proceedings of the American Mathematical Society 123(4) (1995), 1037-1047.
8. D. Cox, J. Little, and D. O'Shea, Using Algebraic Geometry, Springer Verlag, New York, Berlin, Heidelberg, 1998.
9. C. D'Andrea and A. Dickenstein, “Explicit formulas for the multivariate resultant,” Pure Appl. Algebra 164(1/2) (2001), 59-86.
10. A.-L. Dixon, “The eliminant of three quantics in two independent variables,” Proc. London Math. Soc. 7(49/69) (1908), 473-492.
11. I. Emiris and V. Pan, “The structure of sparse resultant matrices,” in Proc. Int. Symp. on Symbolic and Algebraic Computation (ISSAC), ACM Press, 1997.
12. I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky, Discriminants, Resultants and Multidimensional Determinants, Birkh\ddot auser, Boston, 1994.
13. L. Gonzáles-Vega, “Une théorie des sous-résultants pour les polyn\hat omes en plusieurs variables,” C.R. Acad. Sci. Paris Sér. I Math., 313(13) (1991), 905-908.
14. H. Hong and M. Minimair, “Sparse resultant of composed polynomials I,” J. Symbolic Computation 33 (2002), 447-465.
15. J.P. Jouanolou, “Le formalisme du résultant,” Adv. Math. 90(2) (1991), 117-263.
16. D. Kapur and T. Saxena, “Sparsity considerations in Dixon resultants,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), ACM, New York, 1996, pp. 184-191.
17. D. Kapur and T. Saxena, “Extraneous factors in the Dixon resultant formulation,” in Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (Kihei, HI), ACM New York, 1997, pp. 141-148.
18. R. Lewis and P. Stiller, “Solving the recognition problem for six lines using the Dixon resultant,” Math. Comput. Simulation 49(3) (1999), 205-219.
19. F.S. Macaulay, The Algebraic Theory of Modular Systems, Cambridge Mathematical Library, 1916.
20. D. Manocha and J. Canny, “Multipolynomial resultant algorithms,” J. Symbolic Computation 15(2) (1993), 99-122.
21. M. Minimair, “Dense resultant of composed polynomials,” Accepted by J. Symbolic Computation in November 2002.
22. G. Nakos and R.M. Williams, “Eliminiation with the Dixon resultant,” Mathematica for Education and Research 6(3) (1997), 11-21.
23. P. Pedersen and B. Sturmfels, “Product formulas for resultants and Chow forms,” Mathematische Zeitschrift 214 (1993), 377-396.
24. J.M. Rojas, “Solving degenerate sparse polynomial systems faster,” J. Symbolic Computation 28(1/2) (1999), 155-186. Special Issue Polynomial Elimination-Algorithms and Applications.
25. B. Sturmfels, “On the Newton polytope of the resultant,” Journal of Algebraic Combinatorics 3 (1994), 207-236.