Factoring sparse resultants of linearly combined polynomials

ABSTRACT

This paper is part of the author's work on determining the irreducible factors of sparse (toric) resultants of composed polynomials. The motivation behind this work is to use the factors for efficient elimination of variables, by sparse resultant computation, from composed polynomials. Previous works considered the sparse (toric) resultant of polynomials having arbitrary (mixed) supports composed with (i.e. evaluated at) polynomials having the same (unmixed) supports and of polynomials having the same (unmixed) supports composed with polynomials having arbitrary (mixed) supports, resp. Here, we consider the sparse resultant of linear polynomials having arbitrary (mixed) supports composed with polynomials having arbitrary (mixed) supports, also called "linearly combined polynomials", (under a natural assumption on their exponents). The main contribution of this paper is to determine the irreducible factors, together with their exponents, of the sparse resultant of these linearly combined polynomials. This result essentially generalizes a result by Gelfand, Kapranov and Zelevinsky factoring the sparse resultant of unmixed dense linear polynomials composed with polynomials with unmixed supports. It is expected that this result can be applied to eliminate variables from linearly combined polynomials with improved efficiency.

REFERENCES

• 1: P. H. Berman and M. F. Singer. Calculating the Galois group of $Lsb 1(Lsb 2(y))=0$, $Lsb 1,Lsb 2$ completely reducible operators. J. Pure Appl. Algebra, 139(1-3):3--23, 1999. Effective methods in algebraic geometry (Saint-Malo, 1998).
• 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: 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]
• 4: J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74556]
• 5: E. Cattani, A. Dickenstein, and B. Sturmfels. Residues and resultants. J. Math. Sci. Univ. Tokyo, 5(1):119--148, 1998.
• 6: A. Cayley. On the theory of elimination. Cambridge and Dublin Math. J., 3:116--120, 1848.
• 7: M. Chardin. Contributions à l'algèbre commutative effective et à la théorie de l'élimination. PhD thesis, Université Paris VI, 1990.
• 8: C. C. Cheng, J. H. McKay, and S. S. Wang. A chain rule for multivariable resultants. Proceedings of the American Mathematical Society, 123(4):1037--1047, April 1995.
• 9: D. Cox, J. Little, and D. O'Shea. Using Algebraic Geometry. Springer Verlag, New York, Berlin, Heidelberg, 1998.
• 10: C. D'Andrea and A. Dickenstein. Explicit formulas for the multivariate resultant. Pure Appl. Algebra, 164(1-2):59--86, 2001.
• 11: A.-L. Dixon. The eliminant of three quantics in two independent variables. Proc. London Math. Soc., 7:49--69, 473--492, November 1908.
• 12: Ioanis Z. Emiris , Victor Y. Pan, The structure of sparse resultant matrices, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.189-196, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258779]
• 13: I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston, 1994.
• 14: L. González-Vega. Une théorie des sous-résultants pour les polynômes en plusieurs variables. C. R. Acad. Sci. Paris Sér. I Math., 313/13:905--908, 1991.
• 15: Jaime Gutierrez , Rosario Rubio San Miguel, Reduced Gro¨bner bases under composition, Journal of Symbolic Computation, v.26 n.4, p.433-444, Oct. 1998 [doi>10.1006/jsco.1998.0222]
• 16: Joe Harris. Algebraic Geometry. Springer-Verlag, New York, Berlin, Heidelberg, 1992.
• 17: Hoon Hong, Subresultants under composition, Journal of Symbolic Computation, v.23 n.4, p.355-365, April 1997 [doi>10.1006/jsco.1996.0093]
• 18: Hoon Hong, Groebner basis under composition I, Journal of Symbolic Computation, v.25 n.5, p.643-663, May 1998 [doi>10.1006/jsco.1997.0192]
• 19: Hoon Hong , Manfred Minimair, Sparse resultant of composed polynomials I^* mixed-unmixed case, Journal of Symbolic Computation, v.33 n.4, p.447-465, April 2002 [doi>10.1006/jsco.2001.0516]
• 20: J. P. Jouanolou. Le formalisme du résultant. Adv. Math., 90(2):117--263, 1991.
• 21: 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]
• 22: 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]
• 23: Robert H. Lewis , Peter F. Stiller, Solving the recognition problem for six lines using the Dixon resultant, Mathematics and Computers in Simulation, v.49 n.3, p.205-219, Aug. 1999 [doi>10.1016/S0378-4754(99)00050-6]
• 24: F. S. Macaulay. The algebraic theory of modular systems. Cambridge Mathematical Library, 1916.
• 25: Dinesh Manocha , John F. Canny, Multipolynomial resultant algorithms, Journal of Symbolic Computation, v.15 n.2, p.99-122, Feb. 1993 [doi>10.1006/jsco.1993.1009]
• 26: Manfred Minimair, Dense resultant of composed polynomials mixed-mixed case, Journal of Symbolic Computation, v.36 n.6, p.825-834, December 2003 [doi>10.1016/S0747-7171(03)00039-7]
• 27: Manfred Minimair, Sparse resultant of composed polynomials II unmixed--mixed case, Journal of Symbolic Computation, v.33 n.4, p.467-478, April 2002 [doi>10.1006/jsco.2001.0517]
• 28: Manfred Minimair, Sparse Resultant under Vanishing Coefficients, Journal of Algebraic Combinatorics: An International Journal, v.18 n.1, p.53-73, July 2003 [doi>10.1023/A:1025169426299]
• 29: G. Nakos and R. M. Williams. Elimination with the Dixon resultant. Mathematica for Education and Research, 6/3:11--21, 1997.
• 30: Patrik Nordbeck, SAGBI bases under composition, Journal of Symbolic Computation, v.33 n.1, p.67-76, 01/01/2002 [doi>10.1006/jsco.2001.0498]
• 31: P. Pedersen and B. Sturmfels. Product formulas for resultants and Chow forms. Mathematische Zeitschrift, 214:377--396, 1993.
• 32: J. Maurice Rojas, Solving degenerate sparse polynomial systems faster, Journal of Symbolic Computation, v.28 n.1-2, p.155-186, July/Aug. 1999 [doi>10.1006/jsco.1998.0271]
• 33: Igor R. Shafarevich , Miles Reid, Basic algebraic geometry 1 (2nd, revised and expanded ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 34: 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation

General Terms:
Theory

Keywords:
composition, linear combination, resultant