Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Introduction to Linear Homotopy

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


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.

*Applied Mathematics > Numerical Methods

global numerical method, nonlinear systems, polynomial systems, homotopia continuation method, Newton's method
Downloads Download Wolfram CDF Player

MathSourceHomotopyLast.nb (5.7 MB) - Mathematica Notebook