Title

Introduction to Linear Homotopy
Author

 Béla Paláncz
 Organization: Budapest University of Technology and Economics
 Department: Photogrammetry and Geoinformatics
Revision date

2008-02-07
Description

Solving nonlinear systems, especially algebraic polynomial systems, is a fundamental problem which occurs frequently in various models of science and engineering like robotics, computer vision, computational geometry, signal processing. The application of symbolic elimination methods, like reduced Gröbner basis and Dixon resultant is restricted by the size and complexity of the system to be solved, therefore mostly numerical methods should be employed. Frequently, we have no proper information about the locations of the roots, which is important for using local numerical methods. Local numerical methods, like the very popular Newton-Raphson method, require initial guess, sufficiently close to the roots being sought. Therefore we need global numerical methods, which are very robust concerning the start values of the iteration. Homotopy continuation proved to be as a reliable and efficient method to solve nonlinear systems as well as polynomial systems for the last two decades, is a globally convergent method. It does not need accurate initial guess and can be used to locate all geometrically isolated solutions of a square polynomial system. In this tutorial type study linear homotopy continuation methods are introduced. The definitions and basic ideas are considered and illustrated with many examples in Mathematica. The general algorithm of linear homotopy method in form of repeating solution of homotopy equation via Newton - Raphson method as well as in form of an initial value problem of a system of ordinary differential equations, are implemented in Mathematica. In addition, a function providing automatic construction of a start system for polynomial systems is also developed. The efficiency of these functions have been illustrated by solving nonlinear as well as polynomial equation systems.
Subject

 Applied Mathematics > Numerical Methods
Keywords

global numerical method, nonlinear systems, polynomial systems, homotopia continuation method, Newton's method