Solving large sparse systems of nonlinear equations and nonlinear least squares problems using tensor methods on sequential and parallel computers
Ali Bouaricha · 1992
This thesis describes efficient algorithms for solving large sparse systems of nonlinear equations and nonlinear least squares problems using tensor methods, and the implementation of these algorithms in modular software packages. It also describes the development of parallel versions of tensor methods, and their implementation on a distributed-memory machine. Tensor methods for nonlinear equations were introduced in Schnabel and Frank (ScF84) and extended to nonlinear least squares problems in Bouaricha (Bou86). Tensor methods base each iteration on a local quadratic model of the function. The second order term, also called the tensor term, is selected so that the model interpolates a small number of function values from previous iterations. The tensor term has a simple form that is well suited to efficient model formation and solution algorithms. The tensor model requires no more derivative or function information than the standard model, and the additional costs of forming and solving the tensor model are small compared to arithmetic cost per iteration of standard methods. The main contribution of this thesis is the extension of tensor methods to large, sparse nonlinear equations and nonlinear least squares problems. This involves an entirely new way of solving the tensor model that is efficient for sparse problems, and the consideration of a number of interesting linear algebraic implementation issues. Software packages are developed for sparse tensor methods and their standard Newton or Gauss-Newton analogs, based upon efficient sparse matrix factorization methods. Experimental test results of our tensor method for both large sparse systems of nonlinear equations and nonlinear least squares problems compared with the results of the standard method indicate that the tensor method is significantly more efficient and robust than the standard method. In this thesis we also develop parallel row-oriented tensor algorithms for solving dense systems of nonlinear equations and nonlinear least squares problems on a distributed-memory MIMD multiprocessor. Experimental results obtained on an Intel iPSC2 hypercube multiprocessor are presented and compared with sequential tensor method code executed on a single processor. These experimental results reveal that nearly full efficiency is obtained when $m over p\$ is relatively large, where $p\$ is the number of processors, and $m\$ is the row size of the problem. We also develop tensor methods for very large systems of nonlinear equations based on Krylov subspace techniques for approximately solving the linear systems that are required. ftn*Research supported by ARO, NSF, and AFOSR.