# zbMATH — the first resource for mathematics

Randomized heuristics for exploiting Jacobian scarcity. (English) Zbl 1242.90301
Summary: 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)\dot x$$ or Jacobian-transpose-vector products $$F'(x)^T\overline 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.
##### MSC:
 90C59 Approximation methods and heuristics in mathematical programming 68W20 Randomized algorithms 05C81 Random walks on graphs 68N20 Theory of compilers and interpreters