Fast Numerical Determination of Symmetric Sparsity Patterns

We consider a function g : ! n ! ! n for which the Jacobian is symmetric and sparse. Such functions often arise, for instance, in numerical optimization, where g is the gradient of some objective function f so that the Jacobian of g is the Hessian of f . In many such applications one can generate extremely efficient algorithms by taking advantage of the sparsity structure of the problem if this pattern is known a priori. Unfortunately, determining such sparsity structures by hand is often difficult and prone to error. If one suspects a mistake has been made, or if g is a "black box" so that the true structure is completely unknown, one often has no alternative but to compute the entire matrix by finite differences --- a prohibitively expensive task for large problems. We show that it is possible to numerically determine symmetric sparsity patterns using a relatively small number of g evaluations. Numerical results are shown for n up to 100,000 in which all nonzeros in the Jacobian..