Up: Contents Previous: AD in Maple

SparsLinC: A Library for Computing Sparse Linear Combinations

SYNOPSIS:

SparsLinC is a library written in ANSI C, for the sparse implementation of the operation, linear combination of vectors. SparsLinC has been developed in conjunction with ADIFOR and ADIC, which are primarily forward-mode, first order automatic differentiation (AD) tools. The computational workhorse of derivative codes generated by such tools is the linear combination of vectors. For case where the vectors are characteristically sparse, using SparsLinC is a big boon in terms of reducuing the runtime and memory requirements of the code.

SparsLinC can also be used in any computational context where sparsity is a salient factor in the computation of linear combinations.

WHOM TO CONTACT:

Christian Bischof
Mathematics and Computer Science Division
Bldg. 221, Rm. C-223
Argonne National Laboratory
9700 S. Cass Ave.
Argonne, IL 60439
Tel.: (630) 252-8875
FAX: (630) 252-5986
WWW: http://www.mcs.anl.gov/people/bischof
e-mail: bischof@mcs.anl.gov

DOCUMENTATION:

FUNCTIONALITY:

The computational workhorse of primarily forward-mode, first-order automatic differentiation approaches, such as implemented in ADIFOR or ADIC, is the vector linear combination:

where w and v(i) are vectors and the alpha(i) are scalar multipliers. The vector length p corresponds to the number of directional derivatives being computed.

The SparsLinC (Sparse Linear Combination) library provides an implementation of vector linear combinations when p is large and most of the vectors involved in vector linear combination are sparse (that is, for the most part they contain zero entries). This situation arises, for example, in the computation of large sparse Jacobians or gradients of so-called partially separable functions. In particular, any function with a sparse Hessian belongs to this class.

An important byproduct of derivative computation via SparsLinC is the sparsity pattern of the Jacobian. That is, SparsLinC allows exploitation of derivative sparsity without a priori knowledge of the derivative structure.

SOFTWARE FEATURES:

SparsLinC, which is written in ANSI C, includes the following features:
Three data structures for sparse vectors:
SparsLinC has different data structures for a vector containing only one nonzero, a few nonzeros, or several nonzeros. In the numerical linear algebra literature, the latter two data structures are usually referred to as the ``single-subscript'' and ``compressed subscript'' representation of a sparse vector.
Efficient Memory Allocation Scheme:
SparsLinC employs a ``bucket'' memory allocation scheme, which in effect provides a buffered memory allocation mechanism, supporting the dynamic nature of the sparse vectors while avoiding the need for system calls most of the time.
Polyalgorithms:
SparsLinC switches between vector representations in a transparent fashion and provides special support for the ``+='' operation w = alpha(1)*w + alpha(2)*v , which occurs frequently when computing gradients of partially separable functions.
Full-Precision Support:
single- and double-precision routines are provided for both real- and complex-valued computations.

In this fashion, SparsLinC can adapt to the dynamic nature of the derivative vectors.

AVAILABILITY:

SparsLinC is available for noncommercial use free of charge, but since it is copyrighted software, the signing of a license is required. SparsLinC is contained in the ADIFOR distribution.

Up: Contents Previous: AD in Maple