THE PARALLEL COMPLEXITY OF EMBEDDING ALGORITHMS FOR THE SOLUTION OF SYSTEMS OF NONLINEAR EQUATIONS

Embedding algorithms for nonlinear systems of equations construct a co ntinuous family of systems, and solve the given system by tracking the continuous curve of solutions to the family. Solving nonlinear equati ons by a globally convergent embedding algorithm requires the evaluati on and factoring of a Jacobian matrix at many points along the embeddi ng curve. This paper describes how to optimize the evaluation of the J acobian matrix on a hypercube. Several static and dynamic strategies f or assigning components of the Jacobian to processors on the hypercube are investigated, and it is found that a static rectangular grid mapp ing is the preferred choice for inclusion in a robust parallel mathema tical software package. The static linear mapping is a viable alternat ive when there are many common subexpressions in the component evaluat ion, while the dynamic assignment strategy should only be considered w hen there is large variation in the evaluation times for the component s, leading to a load imbalance on the processors.