Mixed-volume computation by dynamic lifting applied to polynomial system solving

1. D. Avis and K. Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra.Discrete Comput Geom., 8(3):295–313, 1992.

   Article  MATH  MathSciNet  Google Scholar 

2. J. Backelin and R. Fröberg. How we proved that there are exactly 924 cyclic 7-roots.Proceedings of ISSAC-91, pages 103–111, ACM, New York, 1991.

   Google Scholar 

3. D. N. Bernshteîn. The number of roots of a system of equations.Functional Anal. Appl., 9(3):183–185, 1975. Translated fromFunksional. Anal. i Prilozhen., 9(3):1–4, 1975.

   Article  MATH  Google Scholar 

4. M. Grötschel, L. Lovász, and A. Schrijver.Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, volume 2. Springer-Verlag, Berlin, 1988.

   MATH  Google Scholar 

5. L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams.Algorithmica, 7(4):381–413, 1992.

   Article  MATH  MathSciNet  Google Scholar 

6. B. Huber. Numerically solving sparce polynomial systems. Presented at AMS-IMS-SIAM Summer Research Conference on Continuous Algorithms and Complexity, Mount Holyoke College, South Hadley, MA, June 1994.

7. B. Huber and B. Sturmfels. A polyhedral method for solving sparse polynomial systems.Math. Comp., 64(212):1541–1555, 1995.

   Article  MATH  MathSciNet  Google Scholar 

8. M. M. Kapranov, B. Sturmfels, and A. V. Zelevinsky. Chow polytopes and general resultants.Duke Math. J., 67(1):189–218, 1992.

   Article  MATH  MathSciNet  Google Scholar 

9. A. G. Khovanskiî. Newton polyhedra and the genus of complete intersections.Functional Anal. Appl. 12(1):38–46, 1978. Translated fromFunktsional. Anal. i Prilozhen., 12(1), 51–61, 1978.

   Google Scholar 

10. A. G. Kushnirenko. Newton polytopes and the Bézout theorem.Functional Anal. Appl., 10(3):233–235, 1976. Translated fromFunktsional. Anal. i Prilozhen., 10(3), 82–83, 1976.

    Article  MATH  Google Scholar 

11. S. R. Lay,Convex Sets and Their Applications, Wiley, New York, 1982.

    MATH  Google Scholar 

12. C. W. Lee. Regular triangulations of convex polytopes. In P. Gritzmann and B. Sturmfels, editors,Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, pages 443–456. DIMACS Series, volume 4, AMS, Providence, RI, 1991.

    Google Scholar 

13. A. Morgan.Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall, Englewood Cliffs, NJ, 1987.

    MATH  Google Scholar 

14. A. Morgan and V. Shapiro. Box-bisection for solving second-degree systems and the problem of clustering.ACM Trans. Math. Software, 13(2):152–167, 1987.

    Article  MATH  MathSciNet  Google Scholar 

15. A. P. Morgan and A. J. Sommese. Coefficient-parameter polynomial continuation.Appl. Math. Comput., 29(2):123–160, 1989. Errata: 51:207, 1992.

    Article  MATH  MathSciNet  Google Scholar 

16. A. P. Morgan, A. J. Sommese and C. W. Wampler. A product-decomposition theorem for bounding Bézout numbers.SIAM J. Numer. Anal., 32(4):1308–1325, 1995.

    Article  MATH  MathSciNet  Google Scholar 

17. A. P. Morgan, A. Sommese and L. T. Watson. Mathematical reduction of a heart dipole model.J. Comput. Appl. Math., 27:407–410, 1989.

    Article  MATH  Google Scholar 

18. C. V. Nelsen and B. C. Hodgkin. Determination of magnitudes, directions, and locations of two independent dipoles in a circular conducting region from boundary potential measurements.IEEE Trans. Biomed. Engrg., 28(12):817–823, 1981.

    Article  Google Scholar 

19. P. Pedersen. Private communication, 1994.

20. F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, Berlin, 1985.

    Google Scholar 

21. J. M. Rojas. A convex geometric approach to counting the roots of a polynomial system.Theoret. Comput. Sci., 133(1):105–140, 1994.

    Article  MATH  MathSciNet  Google Scholar 

22. R. Schneider. Polytopes and Brunn-Minkowski theory. In R. Schneider, T. Bisztriczky, P. McMullen, and A. I. Weiss, editors.Polytopes: Abstract, Convex and Computational, pages 273–300. Kluwer, Boston, MA, 1994.

    Google Scholar 

23. A. Schrijver.Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, Chichester, 1986.

    MATH  Google Scholar 

24. M. Shub and S. Smale. Complexity of Bézout's theorem, I: Geometric aspects.J. Amer. Math. Soc. 6(2):459–501, 1993.

    Article  MATH  MathSciNet  Google Scholar 

25. B. Sturmfels. On the Newton polytope of the resultant.J. Algebraic Combin., 3:207–236, 1994.

    Article  MATH  MathSciNet  Google Scholar 

26. J. Verschelde and R. Cools. Symbolic homotopy construction.Appl. Algebra Engrg. Commun. Comput., 4(3):169–183, 1993.

    Article  MATH  MathSciNet  Google Scholar 

27. J. Verschelde and K. Gatermann. Symmetric Newton polytopes for solving sparse polynomial systems.Adv. in Appl. Math., 16(1):95–127, 1995.

    Article  MATH  MathSciNet  Google Scholar 

28. J. Verschelde and A. Haegemans. Homotopies for solving polynomial systems within a bounded domain.Theoret. Comput. Sci., 133(1):141–161, 1994.

    Article  MathSciNet  Google Scholar 

29. J. Verschelde, P. Verlinden, and R. Cools. Homotopies exploiting Newton polytopes for solving sparse polynomial systems.SIAM J. Numer. Anal., 31(3):915–930, 1994.

    Article  MATH  MathSciNet  Google Scholar 

30. C. W. Wampler. Bézout number calculations for multi-homogeneous polynomial systems.Appl. Math. Comput., 51(2–3):143–157, 1992.

    Article  MathSciNet  Google Scholar 

31. U. Betke. Mixed volumes of polytopes.Arch. Math.,58:388–391, 1992.

    Article  MATH  MathSciNet  Google Scholar 

32. L. J. Billera and B. Sturmfels. Fiber polytopes,Ann of Math., 135(3):527–549, 1992.

    Article  MathSciNet  Google Scholar 

33. G. Björk and R. Fröberg. A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclicn-roots.J. Symbolic Comput. 12(3):329–336, 1991.

    MathSciNet  Google Scholar 

34. G. Björk and R. Fröberg. Methods to “divide out” certain solutions from systems of algebraic equations, applied to find all cyclic 8-roots. In M. Gyllenberg and L. E. Persson, editors,Analysis, Algebra and Computers in Mathematical Research, pages 57–70. Lecture Notes in Mathematics, volume 564, Dekker, New York, 1994.

    Google Scholar 

35. A. D. Bryuno and A. Soleev. Local uniformization of branches of a space curve, and Newton polyhedra.St. Petersburg Math. J., 3(1):53–82, 1992. Translated fromAlgebra i Analiz 3(1):67–101, 1991.

    MathSciNet  Google Scholar 

36. Yu. D. Burago and V. A. Zalgaller.Geometric Inequalities, Grundlehren der mathematischen Wisenschaften, volume 285. Springer-Verlag, Berlin, 1988.

    MATH  Google Scholar 

37. J. F. Canny and I. Emiris. An efficient algorithm for the sparse mixed resultant.Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pages 89–104. Springer-Verlag, New York, 1993.

    Google Scholar 

38. J. Canny and J. M. Rojas. An optimal condition for determining the exact number of roots of a polynomial system.Proceedings of the 1991International Symposium on Symbolic and Algebraic Computation, pages 96–101. ACM, New York, 1991.

    Google Scholar 

39. K. L. Clarkson, K. Melhorn, and R. Seidel. Four results on randomized incremental constructions. In A. Finkel and M. Jantzen, editors,Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 1992, pages 463–474. Lecture Notes in Computer Science, volume 577, Springer-Verlag, Berlin, 1992.

    Google Scholar 

40. M. E. Dyer and A. M. Frieze. On the complexity of computing the volume of a polyhedron.SIAM J. Comput. 17(5):967–974, 1988.

    Article  MATH  MathSciNet  Google Scholar 

41. M. Dyer, P. Gritzmann, and A. Hufnagel. On the complexity of computing mixed volumes.SIAM J. Comput., to appear.

42. H. Edelsbrunner.Algorithms in Combinatorial Geometry. ETACS Monographs on Theoretical Computer Science, volume 10, Springer-Verlag, Berlin, 1987.

    MATH  Google Scholar 

43. H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations.Proceedings of the Eighth Annual Symposium on Computational Geometry, pages 43–52. ACM, New York, 1992.

    Chapter  Google Scholar 

44. I. Z. Emiris. Sparse Elimination and Applications in Kinematics. Ph.D. thesis, Computer Science Division, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA, 1994.

    Google Scholar 

45. I. Emiris and J. Canny. Efficient incremental algorithms for the sparse resultant and the mixed volume. Technical Report 839, Computer Science Division, University of California, Berkeley, CA, 1994. Also inJ. Symbolic Comput., 11(1):1–33, 1996.

    Google Scholar 

46. M. A. Facello. Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions.Comput. Aided Geom. Design., 12(4):349–370, 1995.

    Article  MATH  MathSciNet  Google Scholar 

47. O. D. Faugeras and S. Maybank. Motion from point matches: multiplicity of solutions.Internat. J. Comput. Vision, 4:225–246, 1990.

    Article  Google Scholar 

48. M. R. Garey and D. S. Johnson.Computers and Intractability. A Guide to the Theory of NP-Completeness. Freemann, San Francisco, CA, 1979.

    MATH  Google Scholar 

49. I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky. Generalized Euler integrals and A-hypergeometric functions.Adv. in Math., 84:255–271, 1990.

    Article  MATH  MathSciNet  Google Scholar 

50. I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky,Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, MA, 1994.

    MATH  Google Scholar 

51. P. Gritzmann and V. Klee. Mathematical programming and convex geometry. In P. M. Gruber and J. M. Wills, editors,Handbook of Convex Geometry, volume A, chapter 2.7, pages 627–674. North-Holland, Amsterdam, 1993.

    Google Scholar 

52. P. Gritzmann and V. Klee. On the complexity of some basic problems in computational convexity: II. Volume and mixed volumes. In R. Schneider, T. Bisztriczky, P. McMullen, and A. I. Weiss, editors,Polytopes: Abstract, Convex and Computational, pages 373–466, Kluwer, Boston, MA, 1994.

    Google Scholar 

53. P. Gritzmann and B. Sturmfels. Minkowski addition of polytopes: computational complexity and applications to Gröbner bases.SIAM J. Discrete Math., 6(2):246–269, 1993.

    Article  MATH  MathSciNet  Google Scholar 

54. C. Wampler and A. Morgan. Solving the 6R inverse position problem using a generic case solution methodology.Mech. Mach. Theory, 26(1):91–106, 1991.

    Article  Google Scholar 

55. C. W. Wampler, A. P. Morgan, and A. J. Sommese. Complete solution of the nine-point path synthesis problem for four-bar linkages.ASME J. Mech. Design, 114(1):153–159, 1992.

    Article  Google Scholar 

56. G. M. Ziegler.Lectures on Polytopes. Graduate Texts in Mathematics, volume 152. Springer-Verlag, New York, 1995.

    MATH  Google Scholar 

Download references