  Computing the Newton-step of a generic function with $N$ decision variables
takes $O(N^3)$ flops. In this paper, we show that given the computational graph
of the function, this bound can be reduced to $O(m\tau^3)$, where $\tau, m$ are
the width and size of a tree-decomposition of the graph. The proposed algorithm
generalizes nonlinear optimal-control methods based on LQR to general
optimization problems and provides non-trivial gains in iteration-complexity
even in cases where the Hessian is dense.
