Publication: On the Practical Exploitation of Scarsity
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

On the Practical Exploitation of Scarsity

- incollection -
 

Author(s)
Andrew Lyons , Jean Utke

Published in
Advances in Automatic Differentiation

Editor(s)
Christian H. Bischof, H. Martin Bücker, Paul D. Hovland, Uwe Naumann, J. Utke

Year
2008

Publisher
Springer

Abstract
Scarsity is the notion that the Jacobian J for a given function f: R^n → R^m may have fewer than n * m degrees of freedom. A scarse J may be represented by a graph with a minimal edge count. So far, scarsity has been recognized only from a high-level application point of view, and no automatic exploitation has been attempted. We introduce an approach to recognize and use scarsity in computational graphs in a source transformation context. The goal is to approximate the minimal graph representation through a sequence of transformations including eliminations, reroutings, and normalizations, with a secondary goal of minimizing the transformation cost. The method requires no application-level insight and is implemented as a fully automatic transformation in OpenAD. This paper introduces the problem and a set of heuristics to approximate the minimal graph representation. We also present results on a set of test problems.

Cross-References
Bischof2008AiA

AD Tools
OpenAD

AD Theory and Techniques
Scarsity

BibTeX
@INCOLLECTION{
         Lyons2008OtP,
       title = "On the Practical Exploitation of Scarsity",
       doi = "10.1007/978-3-540-68942-3_10",
       author = "Andrew Lyons and Jean Utke",
       abstract = "Scarsity is the notion that the Jacobian J for a given function $f: \R^n
         \rightarrow \R^m$ may have fewer than $n * m$ degrees of freedom. A scarse $J$ may be
         represented by a graph with a minimal edge count. So far, scarsity has been recognized only from a
         high-level application point of view, and no automatic exploitation has been attempted. We introduce
         an approach to recognize and use scarsity in computational graphs in a source transformation
         context. The goal is to approximate the minimal graph representation through a sequence of
         transformations including eliminations, reroutings, and normalizations, with a secondary goal of
         minimizing the transformation cost. The method requires no application-level insight and is
         implemented as a fully automatic transformation in OpenAD. This paper introduces the problem and a
         set of heuristics to approximate the minimal graph representation. We also present results on a set
         of test problems.",
       crossref = "Bischof2008AiA",
       pages = "103--114",
       booktitle = "Advances in Automatic Differentiation",
       publisher = "Springer",
       editor = "Christian H. Bischof and H. Martin B{\"u}cker and Paul D. Hovland and Uwe
         Naumann and J. Utke",
       isbn = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2008",
       ad_tools = "OpenAD",
       ad_theotech = "Scarsity"
}


back
  

Contact:
Username:
Password:
(lost password)