Algorithm 801: POLSYS_PLP: A partitioned linear product homotopy code for solving polynomial systems of equations

Globally convergent, probability-one homotopy methods have proven to be ver y effective for finding all the isolated solutions to polynomial systems of equations. After many years of development, homotopy path trackers based o n probability-one homotopy methods are reliable and fast. Now, theoretical advances reducing the number of homotopy paths that must be tracked, and in the handling of singular solutions, have made probability-one homotopy met hods even more practical. POLSYS-PLP consists of Fortran 90 modules for fin ding all isolated solutions of a complex coefficient polynomial system of e quations. The package is intended to be used in conjunction with HOMPACK90 (Algorithm 777) and makos extensive use of Fortran 90 derived data types to support a partitioned linear product (PLP) polynomial system structure. PL P structure is a generalization of m-homogeneous structure, whereby each co mponent of the system can have a different m-homogeneous structure. The cod e requires a PLP structure as input, and although finding the optimal PLP s tructure is a difficult combinatorial problem, generally physical or engine ering intuition about a problem yields a very good PLP structure. POLSYS-PL P employs a sophisticated power series end game for handling singular solut ions, and provides support for problem definition both at a high level and via hand-crafted code. Different PLP structures and their corresponding Bez out numbers can be systematically explored before committing to root findin g.