Numerical algebraic geometry and kinematics

ABSTRACT

Numerical algebraic geometry uses numerical methods, principally numerical tracking of paths defined by polynomial homotopies, to find and manipulate algebraic sets defined by systems of polynomial equations. Kinematics is the study of the geometrical aspects of mechanical motion. The kinematical problems arising in the analysis and design of most robots and mechanisms are essentially algebraic, because these devices are well-modeled as rigid bodies in contact along algebraic surfaces. In particular, the constraints imposed by the most common types of joints, such as simple hinges or ball-and-socket joints, are equivalent to containments of linear features (points, lines, and planes) that are maintained during rigid body motion of the parts. Kinematical studies have driven the development of numerical algebraic geometry and remain one of its most important application areas. Numerical algebraic geometry has proven to be particularly apt for the natural parameterizations presented by problems from kinematics. This extended abstract gives brief overviews of basic numerical algebraic geometry and kinematics.

REFERENCES

• 1: D.A. Bates, J. Hauenstein, A.J. Sommese, and C.W. Wampler. Software for numerical algebraic geometry: a paradigm and progress towards its implementation. Proc. of IMA Workshop on Software for Algebraic Geometry, Oct. 23--27, 2006, submitted. Software at http://www.nd.edu/~sommese/bertini/
• 2: Dan Bates , Chris Peterson , Andrew J. Sommese, A numerical-symbolic algorithm for computing the multiplicity of a component of an algebraic set, Journal of Complexity, v.22 n.4, p.475-489, August 2006 [doi>10.1016/j.jco.2006.04.003]
• 3: Eduardo Cattani , David A. Cox , Guillaume Chèze , Alicia Dickenstein , Mohamed Elkadi , Ioannis Z. Emiris , André Galligo , Achim Kehrein , Martin Kreuzer , Bernard Mourrain, Solving Polynomial Equations: Foundations, Algorithms, and Applications (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 4: Barry H. Dayton , Zhonggang Zeng, Computing the multiplicity structure in solving polynomial systems, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.116-123, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073902]
• 5: M. Giusti and J. Heintz. La détermination de la dimension et des points isolées d'une variété algébrique peuvent s'effectuer en temps polynomial. In Computational Algebraic Geometry and Commutative Algebra, Cortona 1991, edited by D. Eisenbud and L. Robbiano, Symposia Mathematica XXXIV, pages 216--256. Cambridge UP, 1993.
• 6: Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860893]
• 7: Grégoire Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Journal of Complexity, v.19 n.4, p.564-596, August 2003 [doi>10.1016/S0885-064X(03)00031-1]
• 8: Anton Leykin , Jan Verschelde , Ailing Zhao, Newton's method with deflation for isolated singularities of polynomial systems, Theoretical Computer Science, v.359 n.1, p.111-122, 14 August 2006 [doi>10.1016/j.tcs.2006.02.018]
• 9: T.Y. Li. Numerical solution of polynomial systems by homotopy continuation methods. In Handbook of Numerical Analysis. Volume XI. Special Volume: Foundations of Computational Mathematics, edited by F. Cucker, pages 209--304. North-Holland, 2003.
• 10: Y. Lu, D.A. Bates, A.J. Sommese,and C.W. Wampler. Finding All Real Points of a Complex Curve. In Proceedings of the Midwest Algebra, Geometry and Its Interactions Conference, Contemporary Mathematics, AMS, accepted 2007.
• 11: M. Raghavan. The Stewart platform of general geometry has 40 configurations. ASME J. of Mech. Design, 115:277--282, 1993.
• 12: Andrew J. Sommese, Numerical homotopies to compute generic points on positive dimensional algebraic sets, Journal of Complexity, v.16 n.3, p.572-602, Sept. 2000 [doi>10.1006/jcom.2000.0554]
• 13: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components, SIAM Journal on Numerical Analysis, v.38 n.6, p.2022-2046, 2001 [doi>10.1137/S0036142900372549]
• 14: A.J. Sommese, J. Verschelde, and C.W. Wampler. Using monodromy to decompose solution sets of polynomial systems into irreducible components. In Application of Algebraic Geometry to Coding Theory, Physics and Computation, edited by C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher. Proceedings of a NATO Conference, February 25 - March 1, 2001, Eilat, Israel, pages 297--315, Kluwer Academic Publishers.
• 15: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems, SIAM Journal on Numerical Analysis, v.40 n.6, p.2026-2046, 2002 [doi>10.1137/S0036142901397101]
• 16: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical factorization of multivariate complex polynomials, Theoretical Computer Science, v.315 n.2-3, p.651-669, 6 May 2004 [doi>10.1016/j.tcs.2004.01.011]
• 17: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Homotopies for Intersecting Solution Components of Polynomial Systems, SIAM Journal on Numerical Analysis, v.42 n.4, p.1552-1571, 2004 [doi>10.1137/S0036142903430463]
• 18: A.J. Sommese, J. Verschelde, and C.W. Wampler. Advances in polynomial continuation for solving problems in kinematics. ASME J. Mechanical Design, Vol. 126, No. 2, 2004, pp. 262--268.
• 19: A.J. Sommese, J. Verschelde, and C.W. Wampler. Solving polynomial systems equation by equation. Proc. IMA Workshop on Algorithms in Algebraic Geometry, Sept. 18--22, 2006, to appear.
• 20: A.J. Sommese and C.W. Wampler. Numerical algebraic geometry. In The Mathematics of Numerical Analysis, edited by J. Renegar, M. Shub, and S. Smale, volume 32 of Lectures in Applied Mathematics, pages 749--763, 1996. Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah.
• 21: A.J. Sommese and C.W. Wampler. Numerical solution of systems of polynomials arising in engineering and science. World Scientific Press, Singapore (2005).
• 22: A.J. Sommese, C.W. and Wampler. Exceptional sets and fiber products. Foundations of Computational Mathematics, accepted 2007.
• 23: L.W. Tsai, and A.P. Morgan. Solving the kinematics of the most general six- and five-degree-of-freedom manipulators by continuation methods. ASME J. Mech., Trans., Auto. Design, 107:48--57, 1985.
• 24: Jan Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.251-276, June 1999 [doi>10.1145/317275.317286]
• 25: C.W. Wampler. On a rigid body subject to point-plane constraints. ASME J. of Mechanical Design, 128(1):151--158, Jan. 2006.
• 26: C.W. Wampler, and A.P. Morgan. Solving the 6R inverse position problem using a generic-case solution methodology. Mechanism and Machine Theory, 26:1:91--106, 1991.
• 27: 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:153--159, 1992.
• 28: Zhonggang Zeng, Algorithm 835: MultRoot---a Matlab package for computing polynomial roots and multiplicities, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.218-236, June 2004 [doi>10.1145/992200.992209]
• 29: Zhonggang Zeng , Barry H. Dayton, The approximate GCD of inexact polynomials, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.320-327, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005331]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

General Terms:
Algorithms, Theory

Keywords:
homotopy continuation, kinematics, numerical algebraic geometry, robotics