## Sparse Quasi-Newton Methods and the Continuation ProblemThe problem of tracing a smooth path arises in many engineering problems, the solution of parametric differential equations and eigenvalue problems; it also finds application in the solution of nonlinear systems of equations by homotopy techniques. In many instances, the path is defined implicitly as the solution of a system of equations whose Jacobian matrix is large and sparse. Robust simplicial path-following techniques cannot be applied to large problems since the work involved rises rapidly with increasing dimension. This dissertation addresses the numerical problems involved in tracing the path for large sparse systems by the use of a predictor-corrector algorithm. We investigate the use of sparse quasi-Newton techniques to reduce the expense of the convector phase of the predictor-corrector algorithm inherent in Newton's method. In order to avoid the drawbacks of the sparse Broyden method - the need for a matrix factorization on each iterate and the need to store both the Jacobian matrix and its factors - we examine techniques for directly updating the LU factors of the approximation to the Jacobian matrix. Under reasonable assumptions on the systems of equations to be solved, a proof of local Q-superlinear convergence is presented for two sparse updating techniques. A predictor-corrector algorithm employing these sparse updating techniques is implemented in a Fortran code and numerical results are obtained demonstrating the advantages to be gained from the use of quasi-Newton methods for the large sparse continuation problem. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

THE PREDICTORCORRECTOR METHOD | 18 |

DIRECT SECANT UPDATES OF SPARSE MATRIX FACTORS | 44 |

COMPUTATIONAL EXPERIENCE | 99 |

1 other sections not shown

### Common terms and phrases

approximation arclength Broyden update Chapter computational continuation methods continuation problem convergence problem corrector sequence corrector steps corrector technique curve Dennis and Marwil Denote Deuflhard differential equations Dimension Cycles Level Eaves Evaluations 11 exists explicitly Figure finite difference fixed point function evaluations Garcia and Zangwill Gaussian elimination global graph coloring Hence high curvature homotopy problem hyperplane implementation Iterates at Function iterative technique j e X(Z Jacobian matrix Johnson and Austria k+1 k+1 Lemma LU decomposition LU factors Math Newton step Newton's method nonsingular numerical obtain path permutation matrix predictor step predictor-corrector algorithm predictor-corrector cycles predictor-corrector method Proof quasi-Newton methods restart Rheinboldt Saigal Sard's Theorem satisfies secant updates SIAM simplex simplicial techniques solution solve Span{ZJ sparse Broyden method sparse matrix sparsity pattern steplength control steplength strategy subspace systems of equations tangent directions tracing triangulation Update Dimension Cycles updating techniques Wacker Watson zero