Solving algebraic systems using matrix computations

ABSTRACT

Finding zeros of algebraic sets is a fundamental problem in scientific and geometric computation. It arises in symbolic and numeric techniques used to manipulate sets of polynomial equations. In this paper, we outline algorithms and applications for solving zero and one dimensional algebraic sets using matrix computations. These algorithms make use of techniques from elimination theory and reduce the problem to finding singular sets of matrix polynomials. We make use of algorithms for eigen-decomposition, singular value decomposition and Gaussian elimination to compute the singular sets. These algorithms have been implemented and perform very well in practice. We describe their application to computing conformations of molecular chains, inverse kinematics of serial robots, solid modeling and manufacturing.

REFERENCES

• 1: Shreeram S. Abhyankar , Chandrajit L. Bajaj, Computations with Algebraic Curves, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.274-284, July 04-08, 1988
• 2: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 3: [Abh90] S. S. Abhyankar. Algebraic Geometry for Scientists and Engineers. American Mathematical Society, Providence, R. I., 1990.
• 4: Stefan Arnborg , Huichun Feng, Algebraic decomposition of regular curves, Journal of Symbolic Computation, v.5 n.1-2, p.131-140, February/April 1988 [doi>10.1016/S0747-7171(88)80009-9]
• 5: Dennis S. Arnon, Topologically reliable display of algebraic curves, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.219-227, July 1983
• 6: [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 Numerical Mathematics, volume 86, pages 11-30, 1986.
• 7: [BA82] Ulrich Burkert and Norman Allinger. Molecular Mechanics. ACS Monographs. Americal Chemical Society, Washington, D.C., 1982.
• 8: [BDM89] Z. Bai, J. Demmel, and A. McKenney. On the conditioning of the nonsymmetric eigenproblem: Theory and software. Computer Science Dept. Technical Report 469, Courant Institute, New York, NY, October 1989. (LAPACK Working Note #13).
• 9: [BDMS79] J. Bunch, J. Dongarra, C. Moler, and G. W. Stewart. LINPACK User's Guide. SIAM, Philadelphia, 1979.
• 10: [Ber75] D. N. Bernshtein. The number of roots of a system of equations. Funktsional'nyi Analiz i Ego Prilozheniya, 9(3):1-4, 1975.
• 11: [BGW88] C. Bajaj, T. Garrity, and J. Warren. On the applications of multi-equational resultants. Technical Report CSD-TR-826, Department of Computer Science, Purdue University, 1988.
• 12: [Can88] J. F. Canny. The Complexity of Robot Motion Planning. ACM Doctoral Dissertation Award. MIT Press, 1988.
• 13: 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
• 14: [Col75] G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Lecture Notes in Computer Science , number 33, Springer-Verlag, 1975.
• 15: [Dix08] A. L. Dixon. The eliminant of three quantics in two independent variables. Proceedings of London Mathematical Society, 6:49-69, 209- 236, 1908.
• 16: O. D. Faugeras , Steve Maybank, Motion from point matches: multiple of solutions, International Journal of Computer Vision, v.4 n.3, p.225-246, Jun. 1990 [doi>10.1007/BF00054997]
• 17: [GBDM77] B. S. Garbow, J. M. Boyle, J. Dongarra, and C. B. Moler. Matrix Eigensystem Routines - EISPACK Guide Extension, volume 51. Springer-Verlag, Berlin, 1977.
• 18: [GKZ88] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky. Equations of hypergeometric type and newton polyhedra. Doklady AN SSSR, 300:529-534, 1988.
• 19: [GL89] G. H. Golub and C. F. Van Loan. Matrix Computations . John Hopkins Press, Baltimore, 1989.
• 20: [GoS70] N. Go and H. A. Scherga. Ring closure and local conformational deformations of chain molecules. Macromolecules, 3(2):178-187, 1970.
• 21: [GOS73] N. Go and H. A. Scherga. Ring closure in chain molecules with cn, i or S2n symmetry. Macromolecules, 6(2):273-281, 1973.
• 22: [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.
• 23: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 24: [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.
• 25: [Hor91] B. K. P. Horn. Relative orientation revisited. Journal of Optical Society of America, 8(10):1630-1638, 1991.
• 26: John Keith Johnstone, The sorting of points along an algebraic curve, Cornell University, Ithaca, NY, 1987
• 27: [Jou91] Jean-Pierre Jouanolou. Le Formalisme du Résultant, volume 90 of Advances in Mathematics . 1991.
• 28: Shankar Krishnan , Dinesh Manocha, Numeric-symbolic algorithms for evaluating one-dimensional algebraic sets, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.59-67, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220354]
• 29: [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.
• 30: [Mac02] F. S. Macaulay. On some formula in elimination. Proceedings of London Mathematical Society, 1(33):3-27, May 1902.
• 31: Dinesh Manocha, Algebraic and numeric techniques in modeling and robotics, University of California at Berkeley, Berkeley, CA, 1992
• 32: Dinesh Manocha, Computing selected solutions of polynomial equations, Proceedings of the international symposium on Symbolic and algebraic computation, p.1-8, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190349]
• 33: 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]
• 34: [MC27] F. Morley and A. B. Coble. New results in elimination. American Journal of Mathematics , 49:463-488, 1927.
• 35: [MC91] D. Manocha and J. F. Canny. A new approach for surface intersection. International Journal of Computational Geometry and Applications , 1(4):491-516, 1991. Special issue on Solid Modeling.
• 36: 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]
• 37: J.-P. Merlet, Direct kinematics and assembly modes of parallel manipulators, International Journal of Robotics Research, v.11 n.2, p.150-162, April 1992 [doi>10.1177/027836499201100205]
• 38: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 39: [Mor25] F. Morley. The eliminant of a net of curves. American Journal of Mathematics, 47:91-97, 1925.
• 40: [Mor87] A. P. Morgan. Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems. Prentice-Hall, Englewood Cliffs, New Jersey, 1987.
• 41: [Mor92] A. P. Morgan. Polynomial continuation and its relationship to the symbolic reduction of polynomial systems. In Symbolic and Numerical Computation for Artificial Intelligence, pages 23-45, 1992.
• 42: [MZW95] D. Manocha, Y. Zhu, and W. Wright. Conformational analysis of molecular chains using nano-kinematics. Computer Application of Biological Sciences (CABIOS), pages 71- 86, 1995.
• 43: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 44: [PK92] J. Ponce and D. J. Kriegman. Elimination theory and computer vision: Recognition and positioning of curved 3d objects from range, intensity, or contours. In Symbolic and Numerical Computation for Artificial Intelligence , pages 123-146, 1992.
• 45: 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
• 46: [Sal85] G. Salmon. Lessons Introductory to the Modern Higher Algebra. G. E. Stechert & Co., New York, 1885.
• 47: Thomas W. Sederberg , Tomoyuki Nishita, Geometric Hermite approximation of surface patch intersection curves, Computer Aided Geometric Design, v.8 n.2, p.97-114, May 1991 [doi>10.1016/0167-8396(91)90036-B]
• 48: [SS83] J. T. Schwartz and M. Sharir. On the piano movers probelem ii, general techniques for computing topological properties of real algebraic manifolds. Advances of Applied Maths, 4:298-351, 1983.
• 49: [Ste76] G. W. Stewart. Simultaneous iteration for computing invariant subspaces of nonhermitian matrices. Numerische Mathematik, 25:123-136, 1976.
• 50: [Stu91] B. Sturmfels. Sparse elimination theory. In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra. Cambridge University Press, 1991.
• 51: Mark W. Spong, Robot Dynamics and Control, John Wiley & Sons, Inc., New York, NY, 1989
• 52: [SZ94] B. Sturmfels and A. Zelevinsky. Multigraded resultants of sylvester type. Journal of Algebra , 1994. To appear.
• 53: [Wae50] B. L. Van Der Waerden. Modern Algebra (third edition). F. Ungar Publishing Co., New York, 1950.
• 54: [Wal50] R. J. Walker. Algebraic Curves. Princeton University Press, New Jersey, 1950.
• 55: [Wil59] J. H. Wilkinson. The evaluation of the zeros of ill-conditioned polynomials, parts i and ii. Numer. Math., 1:150-166 and 167-180, 1959.
• 56: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 57: [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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  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, Measurement, Performance, Theory