Sparse Matrix Structures and Higher Derivatives
In this talk we consider solving nonlinear systems of equations and the unconstrained minimization problem using iterative methods from
the Halley class. The methods in this class have in general local and
third order rate of convergence. In the unconstrained optimization case
these methods will require the second and third derivative. We say that
the sparsity pattern of the third derivative (or tensor) is induced by
the sparsity pattern of the Hessian matrix. The sparsity pattern of
the tensor can fairly easy be derived from the indices of the nonzero
elements of the Hessian. However, few datastructures for sparse
symmetric matrices will store both the row and column index of a
nonzero element. We will discuss some datastructures for matrices where
the indices of nonzero elements of the tensor can be computed. These
will be compressed storage format using array of arrays (jagged) data
structures for storing the second and third derivative of a multivariate
function. Methods in the Halley class require solution of one or two
linear systems of linear equations and we briefly discuss suitable
termination criteria for the (inner) iterative method to achieve a cubic
rate of convergence as well as direct methods. We also discuss
techniques to compute the derivatives using coloring schemes to computesparse Jacobian and Hessian matrices.
Trond Steihaug, University of Bergen, Norway
