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.