Introduction

The efficient and robust numerical solution of a system of nonlinear equations can be a rather challenging problem - especially in cases where only little a priori information on the solution is available. A quite outstanding method for solving nonlinear equations is the Newton method, an iterative scheme which is known to converge quadratically near the solution, but only, if the initial guess is sufficiently close to the solution. Now, in order to extend the convergence domain of Newton's method, some globalizations are in common use, e.g. damped Newton methods, steepest descend methods and Levenberg-Marquardt methods. Based on the latter techniques, some state-of-the-art software has been developed, e.g. the codes from IMSL, NAG and MINPACK. In contrast to this, the codes which are presented here are based on the affine invariant damped Newton techniques due to Deuflhard. [1], [2],[3] Within these algorithms the usual local Newton techniques are combined with a special damping strategy in order to create globally convergent Newton schemes. One essential property of these algorithms - as well as of the underlying theory - is their affine invariance. As far as possible, this property of the algorithms is preserved by the codes. Furthermore, the damping strategy and the convergence checks are implemented in a scaling invariant form - a feature which is extremely useful especially for real life applications.

The codes presented here are revised and extended versions of former research codes due to Deuflhard. Within the new codes the most recent theoretical results of [3] are regarded and, furthermore, some new algorithmic variants are realized. The main new features of the implementation are the internal workspace management, an option setting concept and the modular programming. The new interface allows on one hand an easy-to-use application and on the other hand an easy selection and control of special features of the codes. The codes are still considered to be research codes, in the sense, that a variety of algorithmic options may be set by the user and that they are not optimized with respect to performance.

Within the course of the Newton iteration a sequence of linear problems must be solved. As long as the dimension n of the nonlinear system is of moderate size, this can be done very efficiently by applying direct methods, e.g. Gaussian elimination techniques. Using special implementations of direct methods, like band mode elimination or sparse matrix techniques, even large systems with special structures can be attacked. But for very large scale problems, e.g. discretized partial differential equations in 2 or 3 dimensions, an iterative solution of the linear systems may be the only method of choice. In this case, one has two nested iteration processes: the Newton iteration, appearing as the outer iteration, and the iterative solution of the arising linear systems appearing as the inner iteration. In view of an efficient realization the question of how to choose the (required) accuracy for the inner iteration is of essential importance. Too weak accuracy requirements may destroy convergence (or slow down convergence speed) of the outer (Newton) iteration. Too stringent accuracy requirements will increase computing time drastically without increasing convergence speed of the outer iteration. Besides this, note that an only approximate solution of the linear systems means that only a so called inexact Newton scheme is available. The derivation of a cheaply implementable extension of affine invariant Newton methods to the case of inexact Newton methods, including an accuracy matching strategy, has been studied by Deuflhard [4].

The above described techniques have been realized within the software package GIANT (mnemotechnically for Global Inexact Affine invariant Newton Techniques). In order to get a running code, two iterative linear solvers are presently included in the GIANT package. First, there is the well-known and widely used "Generalized Minimum Residual" (GMRES) code due to Brown/Hindmarsh/Seager from the SLAP package of Seager/Greenbaum. [9],[6] As the underlying minimization principle of GMRES does not match the theoretical background of global affine invariant Newton methods, a recently developed iterative linear solver due to Deuflhard/Freund/Walter [5] has been implemented and adapted for the use in GIANT. This fast secant method GBIT1, which uses so-called "Good Broyden" updates and a special, adapted line search principle, fits perfectly into the theoretical frame of GIANT. Both iterative methods for the solution of the linear systems may be combined with preconditioning techniques to improve their convergence properties.

For more details on the algorithm and its implementation please refer to the Technical Reports TR90-11 and TR91-10.

ANT - Introduction   Codes - Introduction  NLEQ1   NLEQ1S
NLEQ2                    GIANT                        References