On the calculation of Jacobian matrices by the Markowitz rule

Abstract. The evaluation of derivative vectors can be performed with optimal computa-tional complexity by the forward or reverse mode of automatic dierentiation. This ap-proach may be applied to evaluate rst and higher derivatives of any vector function that is de ned as the composition of easily dierentiated elementary functions, typically in the form of a computer program. The more general task of eciently evaluating Jacobians or other derivative matrices leads to a combinatorial optimization problem, which is conjectured to be NP-hard. Here, we examine this vertex elimination problem and solve it approximately, using a greedy heuristic. Numerical experiments show the resulting Markowitz scheme for Jacobian evaluation to be more ecient than column by column or row by row evaluation using the forward or the reverse mode, respectively. 1 Basic Setting and Assumptions. Most nonlinear vector functions of practical interest are evaluated by computer programs in a high-level computer language such as Fortran or C. Conceptually, the execution of any such evaluation program can be viewed as a sequence of scalar assignments v