ANGEL

Synopsis

ANGEL stands for Automatic differentiation Nested Graph Elimination Library. It implements graph elimination techniques in order to find the cheapest accumulation of Jacobian matrices. It provides:

Sparse representation of c-graphs and their dual line graphs including many helper functions to work with them
Vertex, edge, and face elimination

Structured graph generator
Heuristics for selecting next vertex, edge or face to eliminate

Lowest Markowitz degree first
Lowest relative Markowitz degree first
Minimal Fill-in
Maximal overall path length reduction
Maximal overall Markowitz degree reduction
Lowest Markowitz minimal damage
Scarcity-aware edge eliminations

Stochastic methods

It is intended to optimize elimination sequences but written as universally as possible and can be applied to any problem where neighborhood relation and objective function are provided as functor
Metropolis with fixed temperature
Logarithmic simulated annealing

ANGEL has been developed as an independent library but is primarily used by the OpenAD framework for automatic differentiation.
Note, that the Unix name for this sourceforge project is angellib.

Downloads

Much of the current development work for the core library with detailed descriptions of the changes, is kept in a Mercurial repository hosted at Argonne National Laboratory.

While we find Mercurial to be much more convenient than CVS for our development is still is somewhat unknown and therefore we use a CVS repository hosted at sourceforge for distribution.

Sourceforge provides instructions to checkout the sources. Note, that the modulename for the library is angel. The other modules in the project are not used by OpenAD. They have last been updated in 2003 and are compatible with angel_base but are not compatible with the current version of angel.

angel_base: a 2003 baseline version of angel
angel_paper_programs: example programs
cgraphs: example graphs
lsaface: draft on randomized face elimination
papers: drafts of randomized edge elimination etc.

The module programs has been partially updated in March 2008 for purposes unrelated to OpenAD. The sourceforge CVS repository is frequently synchronized to the latest changes in the Mercurial development repository. More infrequently we provide snapshots of the angel library as a dated release.

Dependencies:

GNU make
boost libraries
OpenAD : this dependency can be avoided by commenting out
CPPFLAGS += -DUSEXAIFBOOSTER
and the lines below that one in
angel/specs/lib_usage.conf

Documentation

For details on classes and functions in ANGEL see the reference manual PDF or html pages (last generated on Wednesday, 11-Mar-2009 15:41:51 UTC)

Author & Acknowledgments

the main author of the original version is Peter Gottschling
further contributions have been made by Uwe Naumann, Jean Utke and Andrew Lyons
the initial development of ANGEL was part of the XCOp project and was supported by the Engineering and Physical Sciences Research Council (EPSRC - UK) under grant number GR/R/38101/01.
further development was supported under the NSF's Information Technology Research (ITR) program under contract OCE-0205590

This page was last updated on Wednesday, 11-Mar-2009 19:07:45 UTC.