ZERO -- Zeros of Functions and Systems

The following table shows performance of Newtons method for the problem f1=x**2-y-2=0 and f2=x*y+1=0 with initial guess -4,4

x1 x2 f1 f2 ||inv(jacob)||
-4.0000 4.0000 10.000 -15.000 .33333
-2.4722 1.7778 2.3341 -3.3951 .48011
-1.8176 .87522 .42851 -.59082 .60279
-1.6346 .63831 .33506E-01 -.43366E-01 .65321
-1.6182 .61819 .26912E-03 -.33013E-03 .65832

See also the picture. The solutions of the system occur where the three colors corresponding to the surfaces z=f1(x,y), z=f2(x,y) and z=0 (red, dark blue and light blue) meet. The iterates are represented by vertical bars.

Cinque Terre


Single Variable

f77-zero,
C++ version,
C version
f is a function of one real variable (Brent-Decker method), using function values only, zerofinder , needs inclusion by change of sign on interval
SERVER server routines for brent.shar (C)
DFZERO SLATEC root finder Java version
polyzero f is a polynomial of one complex variable and has real coefficients (least squares method, interactive/file input, f77/C)
MultRoot f polynomial with real (inexact) coefficients, especially for multiple roots (Matlab)
companion
C-version
f polynomial with real coefficients, QR for eigenvalues of companion matrix
Aberth
C-version
f is a polynomial with complex coefficients
MPSolve multiple precision, complex coefficients, f77/f90
Muller
C-version
f is a general function of one complex variable
ZERO search for a zero in a given interval
RPOLY find all zeroes of a real polynomial (Jenkins-Traub method) f90-version, C++-version, Javascript for RPOLY
Madsen find all zeroes of a real polynomial, C++ version
CPOLY find all zeroes of a complex polynomial (Jenkins-Traub method) f90-version, C-version, C++ version
RootFinder find all zeroes of a complex polynomial (several methods, root refinement, Windows version, web-based version)
RROOT safely enclosing zeroes of a continuous function in an interval


Multiple Variable

MULTIPLICITY Matlab software for computing multiplicity structure of nonlinear systems, paper
RATIONAL Four different rational solvers for sparse and dense LINEAR SYSTEMS using GMP, large test set (C)
KINSOL part of the SUNDIALS suite for ODE/DAE (C, Fortran interface)
ALIAS Solve systems of equations or inequalities with interval arithmetic (C++)
TRESNEI Solve systems of equations or inequalities with least squares approach (Matlab)
box_zeros f depends on one or more complex variables, zeros sought in box (based on TOMS666)
HYBRJ f not too nonlinear, exact Jacobian (Powell's hybrid method)
HYBRD
f90 version
not too nonlinear, Powells hybrid method, finite difference Jacobian
DogLeg Powell's dogleg method (Matlab)
csolve Robust solver by C. Sims (Matlab)
STRSCNE Trust region method for bound-constrained nonlinear systems (Matlab)
CoDoSol Constrained dogleg method for nonlinear systems with simple bounds(Matlab)
CRBond's code real/complex one/multidimensional rootfinders and LS solvers (C/C++)
Filtrane part of Galahad, nonlinear constraint solver, filter method, f90
PITCON f not too nonlinear, no good initial guess available, continuation method
ALCON1 Continuation method for systems of algebraic equations f(x,tau)=0. Optional computation of turning and (simple) bifurcation points
ALCON2 Continuation method for systems of algebraic equations f(x,tau)=0. Optional computation of turning and (simple) bifurcation points Optional automatic construction of complete bifurcation diagrams.
LOCA Library of continuation algorithms; uses bordering algorithm to permit very large dimensions; distributed memory parallel (C)
Continuation Toolbox MatCont Includes continuation of limit cycles and codim 1 bifurcations (Matlab)
MATDS Another Matlab continuation toolbox (for dynamical systems)
nleq1 f strongly nonlinear, damped Newtons method; f77/Matlab
nleq2 damped Newtons method, provision for singular Jacobian
NLEQ-paper PDF file on above nleq* codes
SNES part of PETSC , serial and MPI parallel versions
SALSA Self-Adapting Large-scale Solver Architecture for linear and nonlinear systems
PEQN/PEQL inexact Newton and inverse column update methods, for large/sparse problems
giant damped Newtons method, large and sparse problems, iterative linear algebra
nnes zeros sought in box: l<=x<=u, see also users' guide
DAFNE differential equations approach with second order system inspired by mechanics
CHABIS characteristic bisection method
BERTINI Solving polynomial systems by homotopy continuation (C)
Bertini-Lab Solving polynomial systems by homotopy continuation (Matlab)
EPSILON Maple-based package for operations on polynomials including solving systems
HOMPACK globally convergent continuation method for polynomial systems
HOMPACK90 f90 version of HOMPACK
POLSYS_PLP more sophisticated version of HOMPACK90
PHoM Polyhedral Homotopy Continuation Method for Polynomial Systems (C++), module CMPS also in Matlab
TENSOLVE A Software Package for Solving Systems of Nonlinear Equations and Nonlinear Least-squares Problems Using Tensor Methods f90 version
toms/795, PHCPACK A general-purpose solver for polynomial systems by homotopy continuation
INTBIS interval method, f77


(Constrained) minimization approach

Rootfinders based on Newtons method or its modification will run into considerable trouble when presented with a problem where singularities of the Jacobian occur. In this case the use of unconstrained or constrained minimization might help, since there exist minimization methods which are rather robust if the constraint gradients are linearly dependent. To use an unconstrained minimizer, choose e.g. f(x)=||F(X)||^2 (the Euclidean length squared) and minimize this with some code proposed in the unconstrained minimization section. To use a constrained minimizer, choose simply f==0 as an objective function and minimize this under the constraint F(x)=0. The following code works often successfully in this situation:

LANCELOT A or LANCELOT B augmented Lagrangian based method