Publications

A. Lyons, I. Safro, and J. Utke, "Randomized Heuristics for Expjloiting Jacobian Scarcity," Preprint ANL/MCS-P1716-0110, January 2010. [pdf]

We describe a code transformation technique that, given code for a vector function F, produces code suitable for computing collections of Jacobian-vector products F'(x)[x dot] or Jacobian transpose-vector products F'(x)[sup T][y bar]. Exploitation of scarcity — a measure of the degrees of freedom in the Jacobian matrix — means 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 the evaluation of large collections of Jacobian-vector products or Jacobian-transpose-vector products. Our heuristics are randomized in nature and compare favorably in all cases with the best known heuristics.