The main purpose of SparsLinC is to support the computation of linear
combinations of sparse vectors, i.e.
for single and double precision real and complex types.
This operation is the key kernel in first-order derivative propagation, with
vectors corresponding to derivative objects, and, ultimately, to rows of the
Jacobian to be computed.
We note that, in general, no intermediate derivative object can have more
nonzeros than any row of the final Jacobian.
However, even for gradients,
which are dense, sparsity can potentially be exploited in the gradient
computation.
If
has a sparse Hessian, it is a partially separable function
and can be represented as
where each
only depends on a few of the
, and hence
each of
is sparse.
Hence, whether
is expressed in this partially separable form or not, there is "sparsity 'under the rug".
So by using dynamic data structures, we can
SparsLinC supports sparse vector accumulation employing a polyalgorithm that transparently switches between three different representations of sparse vectors, provides a buffered memory-management scheme, and special support for the type of vector accumulations arising in the computation of gradients of partially separable functions. SparsLinC is written in portable ANSI C and supports single, double, complex, and double complex arithmetic.
Employing ADIFOR/SParsLinC on some large-scale problems arising in large-scale optimization, we obtained up to three orders of magnitude improvement in both runtime and storage compared to the performance of ADIFOR without SParsLinC (which usually is already 2-4 times faster than numerical approximations of derivatives). To view a graph of performance improvement through SparsLinC (7k) click here.
SparsLinC has been developed by Chris Bischof and Peyvand Khademi.
If you have any questions about SparsLinC, or would like to use it, please write us at sparselinc@mcs.anl.gov.
