Computing selected solutions of polynomial equations

ABSTRACT

We present efficient and accurate algorithms to compute solutions of zero-dimensional multivariate polynomial equations in a given domain. Earlier methods for solving polynomial equations are based on iterative methods, homotopy methods or symbolic elimination. The total number of solutions correspond to the Bezout bound for dense polynomial systems or the BKK bound for sparse systems. In most applications the actual number of solutions in the domain of interest is much lower than the Bezout or BKK bound. Our approach is based on global formulation of the problem using resultants and matrix computations and localizing it to find selected solutions only. The problem of finding roots is reduced to computing eigenvalues of a generalized companion matrix and we use the structure of the matrix to compute the solutions in the domain of interest only. The resulting algorithm is iterative in nature and we discuss its performance on a number of applications.

REFERENCES

• ABB+92: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• AS86: W. Auzinger and H.J. Stetter. An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In International Series of Numemcal Mathematics, volume 86, pages 11-30, 1986.
• BD93: Z. Bai and J. Demmel. Design of a parallel nonsymmetric eigenroutine toolbox, Part I. In Proceedings of the Sixth SIAM Conference on Parallel Proceesing for Scientific Computing. SIAM, 1993.
• Bea92: Gary Bishop , Henry Fuchs, Research directions in virtual environments: report of an NSF Invitational Workshop, March 23-24, 1992, University of North Carolina at Chapel Hill, ACM SIGGRAPH Computer Graphics, v.26 n.3, p.153-177, Aug. 1992 [doi>10.1145/142413.142416]
• Ber75: D.N. Bernshtein. The number of roots of a system of equations. Funktsional'nyi A naliz i Ego Prilozheniya, 9(3):1-4, 1975.
• Buc85: B. Buchberger. Groebner bases: An algorithmic method in ideal theory, in N.K. Bose, editor, Multidimensional Systems Theory, pages 184- 232. D. Reidel Publishing Co., 1985.
• Can88: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• CE93: John F. Canny , Ioannis Z. Emiris, An Efficient Algorithm for the Sparse Mixed Resultant, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.89-104, May 10-14, 1993
• CKL89: 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]
• Cra89: John J. Craig, Introduction to Robotics: Mechanics and Control, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• Dix08: A.L. Dixon. The eliminant of three quantics in two independent variables. Proceedings of London Mathematical Society, 6:49-69, 209-236, 1908.
• Fau93: Olivier Faugeras, Three-dimensional computer vision: a geometric viewpoint, MIT Press, Cambridge, MA, 1993
• FGLM93: J. C. Faugère , P. Gianni , D. Lazard , T. Mora, Efficient computation of zero-dimensional Gro¨bner bases by change of ordering, Journal of Symbolic Computation, v.16 n.4, p.329-344, Oct. 1993 [doi>10.1006/jsco.1993.1051]
• GL89: G.H. Golub and C.F. Van Loan. Matrix Computations. John Hopkins Press, Baltimore, 1989.
• GoS70: N. Go and H.A. Scherga. Ring closure and local conformational deformations of chain molecules. Macromolecules, 3(2):178-187, 1970.
• GZ79: C.B. Garcia and W.I. Zangwill. Finding all solutions to polynomial systems and other systems of equations. Math. Prog., 16:159-176, 1979.
• Hof89: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• Hof90: C.M. Hoffmann. Algebraic and numeric techniques for offsets and blends. In W. Dahmen, M. Gasca, and C. Micchelli, editors, Computations of Curves and Surfaces, pages 499-528. Kluwer Academic Publishers, 1990.
• Hor91: B.K.P. Horn. Relative orientation revisited. Journal of Optical Society of America, 8(10):1630-1638, 1991.
• HS92: Birkett Huber and Bernd Sturmfels. A polyhedral method for solving sparse polynomial systems. Cornell University, manuscript, 1992.
• Jou91: Jean-Pierre Jouanolou. Le Formalisme du Rgsultant, volume 90 of Advances in Mathematics. 1991.
• Lak92: Y.N. Lakshman. On the complexity of computing Groebner bases for zero dimensional polynomial ideals. PhD thesis, Rennselaer Polytechnic Institute, Troy, NY, 1992.
• Laz81: D. Lazard. R6solution des systemes d'equations alg~briques. Theoretical Computer Science, 15:77-110, 1981.
• Laz92: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• LL88: H.Y. Lee and C.G. Liang. A new vector theory for the analysis of spatial mechanisms. Mechanisms and Machine Theory, 23(3):209- 217, 1988.
• Mac02: F.S. Macaulay. On some formula in elimination. Proceedings of London Mathematical Society, 1(33):3-27, May 1902.
• Man92: Dinesh Manocha, Algebraic and numeric techniques in modeling and robotics, University of California at Berkeley, Berkeley, CA, 1992
• Man94: Dinesh Manocha, Solving Systems of Polynomial Equations, IEEE Computer Graphics and Applications, v.14 n.2, p.46-55, March 1994 [doi>10.1109/38.267470]
• MC27: F. Morley and A.B. Coble. New results in elimination. Amemcan Journal of Mathematics, 49:463-488, 1927.
• MC92: D. Manocha and :I.F. Canny. Real time inverse kinematics of generM 6R manipulators. In Proceedings of IEEE Conference on Robotics and Automation, pages 383-389, 1992.
• MC93: 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]
• Mil92: P.S. Milne. On the solutions of a set of polynomial equations. In Symbolic and Numerical Computation for Artificial Intelligence, pages 89-102, 1992.
• Ped91: Paul Pedersen, Multivariate Sturm Theory, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.318-332, October 07-11, 1991
• RR89: Madhusudan Raghaven , Bernard Roth, Kinematic analysis of the 6R manipulator of general geometry, The fifth international symposium on Robotics research, p.263-269, February 1991
• Sal85: G. Salmon. Lessons Introductory to the Modern Higher Algebra. G.E. Stechert ~~ Co., New York, 1885.
• SS93: M. Shub and S. Smale. Complexity of bezout's theorem, I. geometric aspects. Journal of the American Mathematical Society, 6(2):459-501, 1993.
• SZ94: B. Sturmfels and A. Zelevinsky. Multigraded resultants of sylvester type. Journal of Algebra, 1994. To appear.
• Wil59: J.H. Wilkinson. The evaluation of the zeros of ill-conditioned polynomials, parts i and II. Numet. Math., 1:150-166 and 167-180, 1959.
• Wil65: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• WM91: C. Wampler and A.P. Morgan. Solving the 6R inverse position problem using a generic-case solution methodology. Mechanisms and Machine Theory, 26(1):91-106, 1991.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

General Terms:
Algorithms, Performance