John F. Canny
Ioannis Z. Emiris
Skip Abstract Section
Abstract
Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a determinantal formula for the sparse resultant of an arbitrary system of n + 1 polynomials in n variables. This resultant generalizes the classical one and has significantly lower degree for polynomials that are sparse in the sense that their mixed volume is lower than their Bézout number. Our algorithm uses a mixed polyhedral subdivision of the Minkowski sum of the Newton polytopes in order to construct a Newton matrix. Its determinant is a nonzero multiple of the sparse resultant and the latter equals the GCD of at most n + 1 such determinants. This construction implies a restricted version of an effective sparse Nullstellensatz. For an arbitrary specialization of the coefficients, there are two methods that use one extra variable and yield the sparse resultant. This is the first algorithm to handle the general case with complexity polynomial in the resultant degree and simply exponential in n. We conjecture its extension to producing an exact rational expression for the sparse resultant.
- AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. Google Scholar
- AUZINGER, W., AND STETTER, H. J. 1988. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Proceedings of the International Conference on Numerical Mathematics, International Series of Numerical Mathematics, vol. 86. Birkhfiuser, Basel, Switzerland, pp. 12-30.Google Scholar
- BAJAJ, C., GARRITY, T., AND WARREN, J. 1988. On the applications of multi-equational resultants. Tech. Rep. 826. Purdue Univ., West Lafayette, Ind.Google Scholar
- BERNSTEIN, D.N. 1975. The number of roots of a system of equations. Funct. Anal, Appl. 9, 2, 183-185.Google Scholar
- BILLERA, L. J., AND STURMFELS, B. 1992. Fiber polytopes. Ann. Math. 135, 527-549.Google Scholar
- BROWNAWELL, D. 1987. Bounds for the degree in the Nullstellensatz. Ann. Math., Second Ser. 126, 3, 577-591.Google Scholar
- CANNY, J.F. 1988. The Complexity of Robot Motion Planning. MIT Press, Cambridge, Mass. Google Scholar
- CANNY, J., AND EMIRIS, I. 1993. An efficient algorithm for the sparse mixed resultant. In Proceedings of the International Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes (Puerto Rico), G. Cohen, T. Mora, and O. Moreno, Eds. Lecture Notes in Computer Science, vol. 263. Springer-Verlag, Berlin, Germany, pp. 89-104. Google Scholar
- CANNY, J., AND PEDERSEN, P. 1993. An algorithm for the Newton resultant. Tech. Rep. 1394. Comput. Science Dept., Cornell Univ., Ithaca, N.Y. Google Scholar
- CHISTOV, A. 1986. Polynomial-Time factoring algorithm for polynomials and finding components of varieties in subexponential time. J. Soviet Math. 36, 1838-1882.Google Scholar
- CHISTOV, A. L., AND GRIGORYEV, D.Y. 1984. Complexity of quantifier elimination in the theory of algebraically closed fields. In Proceedings of the Symposium on Mathematical Foundations of Computer Science, M. P. Chytil and V. Koubel, Eds. Lecture Notes in Computer Science, vol. 176. Springer-Verlag, New York, pp. 17-31. Google Scholar
- COPPERSMITH, D., AND WINOGRAD, S. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Computat. 9, 251-280. Google Scholar
- EHRART, E. 1967. Sur un problSme de gdomdtrie diophantienne, I. Polyedres et reseaux. J. Reine Agnew. Math. 226, 1-29.Google Scholar
- EMIRIS, I.Z. 1996. On the complexity of sparse elimination. J. Complex. 12, 134-166.{ref14} Google Scholar
- EMIRIS, I.Z. 1997. A general solver based on sparse resultants: Numerical issues and kinematic applications. Tech. Rep. 3110. INRIA, Sophia-Antipolis, France.Google Scholar
- EMIRIS, I.Z. 1998. A complete implementation for computing general dimensional convex hulls. Int. J. Computat. Geom. Appl., Special Issue on Geometric Software 8, 2, 223-253.Google Scholar
- EMIRIS, I. Z., AND CANNY, J.F. 1995. Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symb. Computat. 20, 2 (Aug.), 177-149. Google Scholar
- EMIRIS, I. Z., AND MOURRAIN, B. 1999. Computer algebra methods for studying and computing molecular conformations. Algorithmica (Special Issue on Algorithms for Computational Biology) 25, 372-402.Google Scholar
- EMIRIS, I. Z., AND PAN, V.Y. 1997. The structure of sparse resultant matrices. In Proceedings of the 1997 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC '97) (Maui, Hawaii, July 21-23). ACM, New York, pp. 189-196. Google Scholar
- GELFAND, I. M., KAPRANOV, M. M., AND ZELEVINSKY, A.V. 1994. Discriminants and Resultants. Brikhfiuser, Boston, Mass.Google Scholar
- GRIGORYEV, D. 1986. Polynomial factoring over a finite field and solving systems of algebraic equations. J. Soviet Math. 34, 1762-1803.Google Scholar
- GRC)TSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1993. Geometric Algorithms and Combinatorial Optimization. 2nd ed. Springer-Verlag, Berlin, Germany.Google Scholar
- GUISTI, M., AND HEINTZ, J. 1991. Algorithmes-disons rapides-pour la ddcomposition d'une varidt6 algdbrique en composantes irrdductibles et 6quidimensionelles. In Effective Methods in Algebraic Geometry, T. Mora and C. Traverso, Eds. Progress in Mathematics, vol. 94. Birkhfiuser, Boston, Mass., pp. 169-193.Google Scholar
- GUISTI, M., HEINTZ, J., MORAIS, J. E., AND PARDO, L.M. 1995. When polynomial equation systems can be "solved" fast? In Proceedings of the International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, G. Cohn, M. Giusti, and T. Mora, Eds. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, pp. 205-231. Google Scholar
- HAFNER, J. L., AND MCCURLEY, K.S. 1991. Asymptotically fast triangularization of matrices over rings. SIAM J. Comput. 20, 6, 1068-1083. Google Scholar
- HUBER, B., AND STRUMFELS, B. 1995. A polyhedral method for solving sparse polynomial systems. Math. Comput. 64, 212, 1542-1555. Google Scholar
- KAPUR, D., AND SAXENA, T. 1995. Comparison of various multivariate resultant formulations. In Proceedings of the 1995 A CM International Symposium on Symbolic and Algebraic Computation (ISSAC '95) (Montreal, Ont., Canada, July 10-12). ACM, New York, pp. 187-194. Google Scholar
- KARMARKAR, N. 1984. A new polynomial-time algorithm for linear programming. Combinatorica 4, 373-395. Google Scholar
- KHOVANSKII, A. G. 1978. Newton polyhedra and the genus of complete intersections. Funktsional'nyi Analiz i Ego Prilozheniya 12, 1 (Jan.-Mar.), 51-61.Google Scholar
- KHOVANSKII, A.G. 1991. Fewnomials. AMS Press. Providence, R.I.Google Scholar
- KOLLAR, J. 1988. Sharp effective Nullstellensatz. J. Amer. Math. Soc. 1, 963-975.Google Scholar
- KRISHNAN, S., AND MANOCHA, D. 1995. Numeric-symbolic algorithms for evaluating one-dimensional algebraic sets. In Proceedings of the 1995 ACM International Symposium on Symbolic and Algebraic (ISSAC '95) Computation (Montreal, Ont., Canada, July 10-12). ACM, New York, pp. 59-67. Google Scholar
- KUSHNIRENKO, A. G. 1976. Newton polytopes and the Bezout theorem. Funktsional'nyi Analiz i Ego Prilozheniya 10, 3 (July-Sept.).Google Scholar
- LAZARD, D. 1981. Rdsolution des systSmes d'l~quations algdbriques. Theoret. Comput. Sci. 15, 77-110.Google Scholar
- LICKTEIG, T., AND MEER, K. 1995. A note on testing the resultant. J. Complex. 11, 3, 344-351. Loos, R. 1982. Generalized polynomial remainder sequences. In Computer Algebra: Symbolic and Algebraic Computation, 2nd ed. B. Buchberger, G. E. Collins, and R. Loos, Eds. Springer-Verlag, Wien, Austria, pp. 115-137. Google Scholar
- MANOCHA, D. 1994. Solving systems of polynomial equations. IEEE Comput. Graphics Appl. Special Issue on Solid Modeling, 46-55. Google Scholar
- MANOCHA, D., AND CANNY, J. 1993. Multipolynomial resultant algorithms. J. Symb. Computat. 15, 2, 99-122. Google Scholar
- {ref11}MOURRAIN, B. 1997. Isolated points, duality and residues. J. Pure Appl. Algebra. Special Issue on Algorithms for Algebra 117 & 118 (May), 469-494.Google Scholar
- MOURRAIN, B. 1998. Computing isolated roots by matrix methods. J. Symb. Computat. 26, 715-738. Google Scholar
- PEDERSEN, P., AND STURMFELS, B. 1993. Product formulas for resultants and Chow forms. Math. Z. 214, 337-396.Google Scholar
- PEDERSEN, P., AND STURMFELS, B. 1996. Mixed monomial bases. In Effective Methods in Algebraic Geometry, L. Gonzalez-Vega and T. Recio, Eds. Progress in Mathematics, vol. 143. Birkhfiuser, Boston, Mass. pp. 307-315. Google Scholar
- RAGHAVAN, M., AND ROTH, B. 1995. Solving polynomial systems for the kinematics analysis and synthesis of mechanisms and robot manipulators. Trans. ASME, Special 50th Anniversary Design Issue 117 (June), 71-79.Google Scholar
- RENEGAR, J. 1992. On the computational complexity of the first-order theory of the reals. J. Symb. Computat. 13, 3, 255-352. Google Scholar
- ROJAS, J. M. 1999. Solving degenerate sparse polynomial systems faster. J. Symb. Computat. Special Issue on Elimination 28, 155-186. Google Scholar
- SCHWARTZ, J.T. 1980. Fast probabilistic algorithms for verification of polynomial identies. J. ACM 27, 4 (Oct.), 701-717. Google Scholar
- SCHNEIDER, R. 1993. Convex Bodies: The Brunn-Minkowski Theory. Cambridge University Press, Cambridge, England.Google Scholar
- STANLEY, R.P. 1980. Decompositions of rational convex polyhedra. In Combinatorial Methematics, Optimal Designs and Their Applications, J. Srivastava, Ed. Ann. Disc. Math. 6. North-Holland, Amsterdam, The Netherlands, pp. 333-342.Google Scholar
- STURMFELS, B. 1993. Sparse elimination theory. In Proceedings of Computational Algebraic Geometry and Commut. Algebra 1991 (Cortona, Italy). Cambridge University Press, Cambridge, England, pp. 264-298.Google Scholar
- STURMFELS, B. 1994. On the Newton polytope of the resultant. J. Algeb. Combinat. 3, 207-236. Google Scholar
- VAN DER WAERDEN, B.L. 1950. Modern Algebra, 3rd ed. F. Unger Publishing Co., New York.Google Scholar
- VERSCHELDE, J., GATERMANN, K., AND COOLS, R. 1996. Mixed volume computation by dynamic lifting applied to polynomial system solving. Disc. Comput. Geom. 16, 1, 69-112.Google Scholar
- ZIPPEL, R. Effective Polynomial Computation. Kluwer Academic Publishers, Boston, Mass.Google Scholar
Index Terms
- A subdivision-based algorithm for the sparse resultant
Recommendations
Sparse Resultant under Vanishing Coefficients
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 \cal A 1,…, \cal A n and let \tilde{\cal A} ...
A Sparse Effective Nullstellensatz
We present bounds for the sparseness in the Nullstellensatz. These bounds can give a much sharper characterization than degree bounds of the monomial structure of the polynomials in the Nullstellensatz in case that the input system is sparse. As a ...
On the complexity of the multivariate resultant
The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variables is satisfiable (the resultant is a polynomial in the system's ...
Comments