TENSOR METHODS FOR LARGE SPARSE SYSTEMS OF NONLINEAR EQUATIONS

This paper introduces tensor methods for solving large sparse systems of nonlinear equations. Tensor methods for nonlinear equations were de veloped in the context of solving small to medium-sized dense problems . They base each iteration on a quadratic model of the non linear equa tions, where the second-order term is selected so that the model requi res no more derivative or function information per iteration than stan dard linear model-based methods, and hardly more storage or arithmetic operations per iteration. Computational experiments on small to mediu m-sized problems have shown tensor methods to be considerably more eff icient than standard Newton-based methods, with a particularly large a dvantage on singular problems. This paper considers the extension of t his approach to solve large sparse problems. The key issue considered is how to make efficient use of sparsity in forming and solving the te nsor model problem at each iteration. Accomplishing this turns out to require an entirely new way of solving the tensor model that successfu lly exploits the sparsity of the Jacobian, whether the Jacobian is non singular or singular. We develop such an approach and, based upon it, an efficient tensor method for solving large sparse systems of nonline ar equations. Test results indicate that this tensor method is signifi cantly more efficient and robust than an efficient sparse Newton-based method, in terms of iterations, function evaluations, and execution t ime. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.