Skip to main content


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

Please use this identifier to cite or link to this item:
Title: The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices
Authors: Coleman, Thomas F.
Cai, Jin-yi
Keywords: computer science
technical report
Issue Date: Oct-1984
Publisher: Cornell University
Abstract: Numerical optimization algorithms often require the (symmetric) matrix of second derivatives, $\nabla^{2} f (x)$, of some problem function $f: R^{n} \rightarrow R^{1}$. If the Hessian matrix is large and sparse then estimation by finite differences can be quite attractive since several schemes allow for estimation in $\ll n$ gradient evaluations. The purpose of this paper is to analyze, from a combinatorial point of view, a class of methods known as substitution methods. We present a concise characterization of such methods in graph-theoretic terms. Using this characterization, we develop a complexity analysis of the general problem and derive a roundoff error bound on the Hessian approximation. Moreover, the graph model immediately reveals procedures to effect the substitution process optimally (ie. using fewest possible substitutions given the differencing directions) in space proportional to the number of nonzeroes in the Hessian matrix.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
84-646.pdf1.99 MBAdobe PDFView/Open
84-646.ps483.75 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us