Publication: Randomized heuristics for exploiting Jacobian scarcity
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Randomized heuristics for exploiting Jacobian scarcity

- Article in a journal -
 

Author(s)
Andrew Lyons , Ilya Safro , Jean Utke

Published in
Optimization Methods and Software

Year
2012

Abstract
In this paper, we describe a code transformation technique that, given a code for a vector function F, produces a code suitable for computing collections of Jacobian-vector products F'(x)x? or Jacobian-transpose-vector products F'(x)T yŻ. Exploitation of scarcity – a measure of the degrees of freedom in the Jacobian matrix – requires solving a combinatorial optimization problem that is believed to be hard. Our heuristics transform the computational graph for F, producing, in the form of a transformed graph G', a representation of the Jacobian F'(x) that is both concise and suitable for evaluating large collections of the Jacobian-vector products or the Jacobian-transpose-vector products. Our heuristics are randomized and compare favourably in all cases with the best known heuristics.

AD Tools
OpenAD

AD Theory and Techniques
Combinatorics, Scarsity

BibTeX
@ARTICLE{
         Lyons2012Rhf,
       author = "Lyons, Andrew and Safro, Ilya and Utke, Jean",
       title = "Randomized heuristics for exploiting Jacobian scarcity",
       journal = "Optimization Methods and Software",
       volume = "27",
       number = "2",
       pages = "311--322",
       year = "2012",
       doi = "10.1080/10556788.2011.577774",
       url = " http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.577774",
       eprint = " http://www.tandfonline.com/doi/pdf/10.1080/10556788.2011.577774",
       ad_tools = "OpenAD",
       ad_theotech = "Combinatorics, Scarsity",
       abstract = "In this paper, we describe a code transformation technique that, given a code for a
         vector function F, produces a code suitable for computing collections of Jacobian-vector products
         F'(x)x? or Jacobian-transpose-vector products F'(x)T y¯. Exploitation of scarcity
         – a measure of the degrees of freedom in the Jacobian matrix – requires solving
         a combinatorial optimization problem that is believed to be hard. Our heuristics transform the
         computational graph for F, producing, in the form of a transformed graph G', a representation
         of the Jacobian F'(x) that is both concise and suitable for evaluating large collections of the
         Jacobian-vector products or the Jacobian-transpose-vector products. Our heuristics are randomized
         and compare favourably in all cases with the best known heuristics."
}


back
  

Contact:
Username:
Password:
(lost password)