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.
90C59 Approximation methods and heuristics in mathematical programming
68W20 Randomized algorithms
05C81 Random walks on graphs
68N20 Theory of compilers and interpreters
Full Text: DOI
[1] DOI: 10.1017/S0962492902000132 · Zbl 1047.65012 · doi:10.1017/S0962492902000132
[2] DOI: 10.1007/3-540-27170-8_12 · doi:10.1007/3-540-27170-8_12
[3] Griewank A., Other Titles in Applied Mathematics 105, 2. ed. (2008)
[4] Jerrum, M. and Sinclair, A. 1997.The Markov Chain Monte Carlo method: An Approach to Approximate Counting and Integration, 482–520. Boston, MA: PWS Publishing Co.
[5] DOI: 10.1126/science.220.4598.671 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[6] DOI: 10.1002/net.3230090302 · Zbl 0414.68018 · doi:10.1002/net.3230090302
[7] DOI: 10.1007/978-3-540-68942-3_10 · doi:10.1007/978-3-540-68942-3_10
[8] DOI: 10.1063/1.1699114 · doi:10.1063/1.1699114
[9] DOI: 10.1007/s10107-003-0456-9 · doi:10.1007/s10107-003-0456-9
[10] Naumann U., Stochastic Algorithms: Foundations and Applications 2264 pp 355– (2001)
[11] DOI: 10.1007/978-3-540-39816-5_8 · doi:10.1007/978-3-540-39816-5_8
[12] DOI: 10.1145/1377603.1377605 · Zbl 05458496 · doi:10.1145/1377603.1377605
[13] Schneider J. J., Stochastic Optimization (Scientific Computation) (2006)
[14] Strassen, V. 1990.Algebraic Complexity Theory, 633–672. Cambridge, MA, USA: MIT Press. · Zbl 0900.68247
[15] Tadjouddine M., Automatic Differentiation: Applications, Theory, and Implementations pp 111– (2005)
[16] DOI: 10.1145/1377596.1377598 · Zbl 1291.65140 · doi:10.1145/1377596.1377598
[17] DOI: 10.1007/978-1-4613-1677-0 · doi:10.1007/978-1-4613-1677-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.