Browse Prior Art Database

Estimation of Sparse Hessian Matrices and Graph Coloring Problems

IP.com Disclosure Number: IPCOM000148297D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2007-Mar-29
Document File: 34 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Coleman, Thomas F.: AUTHOR [+3]

Abstract

REAO~NG ROOM E Q M p SCIENCE D E A R T E YALE UNI V E R I

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 34

REAO~NG ROOM

E Q M p ~ ~ ~ ~
SCIENCE D E ~ A R T ~ E ~ YALE UNI V E R ~ I

~y

Estimation of Sparse Hessian Matrics and
Graph ColoringProblenw

December 1982

t~le~artment
of Computer Science

Cornell University Iehaca, New Yark 14853

tt~athematics and Computer Science Division

Argonne National Laboratory
Argonne, Illinois 60439

[This page contains 1 picture or other non-text object]

Page 2 of 34

[This page contains 1 picture or other non-text object]

Page 3 of 34

ABSTRACT

Large scale optimization problems often require an approximation to the Hessian matrix. If the Hessian matrix is sparse then estimation by differences of gradients
is attractive because the number of required differences is usually small compared
to the dimension of the problem. The problem of estimating Hessian matrices by differences can be phrased as follows: Given the sparsity structure of a symmetric . matrix A, obtain vectors dl,d2 ,..., dp such that Adl,Ad2, . . . ,Adp determine A uniquely with p as small as possible. We app~roach this problem from a graph theoretic point of view and show that both direct and indirect approaches to this problem have a natural graph coloring interpretation. The complexity of the problem is analyzed and efficient practical heuristic procedures are developed. Numerical results illustrate the differences between the various approaches.

[This page contains 1 picture or other non-text object]

Page 4 of 34

[This page contains 1 picture or other non-text object]

Page 5 of 34

- Estimation of Spsrse Hessian Matrices and Graph Coloring Problem

    Thomos F. Coleman and J'orge I. Mort? Cornell University and Argoane Natioaal Labotatoy

1. Introducf ion

   Optimization algori$hms which use second order information require the computation or estimation of the symmetric matrix of second derivatives vZ

j (I)

for some problem function f : R *+R. In large scale problems the Hessian matrix

    
(2) is often sparse and then estimation of the Hessian matrix by differencing the gradient v

j (I)

is tridiagonal then Powell and Toint [1979] show that only 2 gradient ditrerences are needed to estimate v2f(z).

                    For a general sparsity structure, however, it is not easy to estimate the Hessian with a small number of gradient difllerences, and thus we address the following problem: Given a function f : R *+R and knowledge of the sparsity structure of the Hessian matrix v2/(z), how many gradient differences are needed to estimate v2f


(3) ?

   We assume that it is desirable to evaluate the gradient vf (2) as a single entity rather than separately evaluate the compone~ts alf (z),

                           ..., 3, f (2) of the gradient. This would certainly be true if the components have expensive common sub-expressions. The Hessian matrix can be estimated by noting that (with the appropriate differentiability assumptions) the product v2f (+Id can be estimated, for example, by forward d...