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.