TR-94-01-02.pdf

``Triangular decomposition methods for solving reducible nonlinear systems of
equations".

John. E. Dennis Jr., Jose. Mario Martinez, and Xiaodong Zhang 

SIAM Journal on Optimization, Vol. 4. No. 2, 1994, pp. 358-382.

Abstract

This paper generalizes to the nonlinear case a standard way to solve
general sparse systems of linear equations. In particular, Duff [1977]
has suggested that row and column interchanges be applied to permute
the coefficient matrix of a linear system into block lower triangular
form. The linear system then can be solved by using the associated
block Gauss-Seidel or forward block substitution scheme. This is the
approach taken in the Harwell MA28 routine. If more than one matrix
with the same sparsity pattern is to be factored, then the reordering
need not be redone.  In extending this approach to nonlinear problems,
it is necessary to assume as in the linear case that component
equations can be evaluated separately from equations in other blocks.
The algorithm for doing the reordering is very fast, and if the
equations can be put into block lower triangular form with each block
size much less than the dimension of the system, then a large savings
is in order because only the diagonal blocks need to be factored. In
the nonlinear variants considered here, there are additional
advantages.  Not only are only the diagonal blocks of the Jacobian
matrix computed and factored, but the off-diagonal partial derivatives
need not even exist. Numerical tests and analytic results affirm the
intuition that these variants are superior locally to Newton's method.
Current work is concerned with globalizing these methods and with
variants especially suited to parallel implementations.

Back to the Publication Page.

Back to the HPCS Main Page at the Ohio State University.