Search

A new method is given for use with vector computers on applications that require multiple solutions with identically patterned triangular factors and different right-hand sides. A key feature is that a vectorization algorithm is used to place the nonzeros from the factors in a few long vectors. The method is shown to work well when incorporated into the mathematical programming system MINOS and tested on 30 linear programming test problems. Keywords: Triangular systems; Linear programming; Vector computers.

This paper is concerned with the numerical behavior of Gauss-Newton methods for nonlinear least-squares problems. Here we assume that the defining feature of a Gauss-Newton method is that the direction from one iterate to the next is the numerical solution of a particular linear least-squares problem, with a steplength subsequently determined by a linesearch procedure. It is well known that Gauss-Newton methods cannot be successfully applied to nonlinear least-squares problems as a class without modification. Our purpose is to give specific examples illustrating some of the difficulties that arise in practice which we believe have not been fully described in the literature.

Schwarz alternating method is an old mathematical technique dating from 1869. It was commonly believed that SAM was a useful tool for theoretical analysis but not a very practical approach for computations. The earlier experiences showed that SAM converged slowly. In this thesis, SAM is reexamined and generalized. The governing factors of convergence of SAM are explored through the analysis for the model problem. Based on this knowledge, many acceleration schemes can be combined with SAM to yield a new type of iterative method for large sparse matrix problems. In particular, when these techniques are applied to the solution of the model problem, an optimal complexity can be achieved. Some generalizations of SAM, namely Schwarz splittings (SS), are presented here. For many important applications, such as performing parallel computations in a non-shared memory environment, using composite grids and also applying fast solvers in an irregular region, (SS)s are found to be useful techniques. In order to identify the types of problems for which (SS)s are most suitable, a new structure for the linear operators called template operators has been developed. Some decay results for the elements of the inverses of sparse operators are given. These results provide a theoretical basis for determining when these SS techniques can be used successfully.

Abstract: "This paper addresses the nonlinear least-squares problem min [formula], where f(x) is a vector in [symbol] whose components are smooth nonlinear functions. The problem arises most often in data fitting applications. Much research has focused on the development of specialized algorithms that attempt to exploit the structure of the nonlinear least-squares objective. We survey numerical methods developed for problems in which sparsity in the derivatives of f is not taken into account in formulationg algorithms."

This dissertation addresses the nonlinear least-squares problem where f(x) is a vector whose components are smooth nonlinear functions. The problem arises most often in data fitting applications. Much research has focused on the development of specialized algorithms that attempt to exploit the structure of the nonlinear least-squares objective. We assume that n and m are relatively small, so that limited storage and sparsity in the derivatives of f need not be taken into account in formulating algorithms. We first discuss existing numerical algorithms for nonlinear least squares, nearly all of which involve iterative minimization of quadratic function. Methods for general unconstrained optimization, Gauss-Newton methods, Levenberg-Marquardt methods, and special quasi-Newton methods are among the algorithms surveyed. Our emphasis is on those methods that form the basis of widely-distributed software, and numerical results are given for a large set of test problems. The main contribution of this research is to propose new algorithms that make use of more general quadratic programming subproblems. Options are investigated that are based on convergence properties of sequential quadratic programming methods for constrained optimization, and on geometric considerations in nonlinear least squares. Numerical results are given, demonstrating that the new methods may be useful in practice.