On Sparse and Symmetric Matrix Updating Subject to a Linear Equation

A procedure for symmetric matrix updating subject to a linear equation and retaining any sparsity present in the original matrix is derived.The main feature of this procedure is the reduction of the problem to the solution of an n dimensional sparse system of linear equations.The matrix of this system is shown to be symmetric and positive definite.The method depends on the Frobenius matrix norm.Comments are made on the difficulties of extending the technique so that it uses more general norms, the main points being shown by a numerical example.1. Introduction.Square matrix updating has become a very active field of research in linear algebra in the last few years, and its techniques are especially useful in algorithms for solving nonlinear systems of equations (see Broyden [1]) and in quasi-Newton methods for unconstrained optimization (see Davidon [2], Fletcher and Powell [3], Powell [7], Huang [6], for example).One common feature of these up-dating procedures is that the updated matrix satisfies a linear equation which, in the optimization field for example, has been called "quasi-Newton equation" or "DFP condition".Unfortunately, when the updated matrix is symmetric, these methods usually revise all the elements of the matrix; and therefore, the size of the problem that can be treated is often limited by the amount of computer storage that is available.Different techniques have appeared for solving linear algebra problems of large dimension when their structure is sparse.For example, very good algorithms are now available to solve large and sparse systems of linear equations (see Reid [8] ); and recently, Schubert presented in [9] a modification of Broyden's [1] method for solving nonlinear systems of equations which takes the sparsity of the problem into account.This method is of real interest but has the drawback that the resulting matrix is not symmetric, even when starting with a symmetric one.Therefore, its use is restricted to problems where the symmetry of the updated matrix is not important.Most of the standard matrix updating techniques can be obtained by calculating the smallest correction matrix in an appropriate norm that causes the new matrix to satisfy some linear constraints; and this problem approach has some advantages in both theory and practice (see [4] ).However, except for Schubert's method which