Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6374
Title: Estimation of Sparse Hessian Matrices and Graph Coloring Problems
Authors: Coleman, Thomas F.
More, Jorge J.
Keywords: computer science
technical report
Issue Date: Dec-1982
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR82-535
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 diferences can be phrased as follows: Given the sparsity structure of a symmetric matrix $A$, obtain vectors $d_{1},d_{2},\ldots,d_{p}$ such that $Ad_{1},Ad_{2},\ldots,Ad_{p}$ determine $A$ uniquely with $p$ as small as possible. We approach 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.
URI: http://hdl.handle.net/1813/6374
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
82-535.pdf2.83 MBAdobe PDFView/Open
82-535.ps537.74 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us