The Complexity of Derivative Computation
The Complexity of Derivative Computation
复制标题
导数计算的复杂性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
U. Naumann
中科院分区：
文献类型：
--
作者：
U. Naumann
我们表明，通过减少整体计算，通过使用最少数量的浮点操作来累积雅各布材料的问题是NP的问题。代数依赖性可以在局部部分衍生物之间存在。非线性矢量函数y = f（x，a），f：ir⊇d→ir，（1）作为计算机程序。1在公式（6）切线中定义的f的jacobian矩阵f' =ḟ（x，ẋ，a）◦f（x，a）∗ẋ，ẋ∈Ir，（2）和伴随，ȳ∈IR，（3）具有潜在复杂的内部控制控制的数值模拟程序可以通过AD工具自动生成[9，11，15，25]。计算科学和工程需要基于衍生信息的数值方法[3，5-7]考虑在给定点上的任意函数来确定我们的兴趣。关于活动的输入（或自变量）x =（xi）i = 1，n。 φJ（vi）j = 1。 xi = i = 1 1 F用于指定的实现。 v = {v1 -n。对线性的代码列表的单一评估，i =∂φj∂vi（vk）k≺j∀i≺i≺j vj =φj（vi）i≺j= 1。对于x和a的给定值，通过将CJ固定在相应的边缘（I，J）。 [2]
We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from Ensemble Computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, and higher derivatives is NP-complete, too. 1 Context We consider the automatic differentiation (AD) [10] of an implementation of a non-linear vector function y = F (x,a), F : IR ⊇ D → IR , (1) as a computer program.1 With the Jacobian matrix F ′ of F defined in Equation (6) tangent-linear ẏ = Ḟ (x, ẋ,a) ≡ F (x,a) ∗ ẋ, ẋ ∈ IR , (2) and adjoint x = F (x, ȳ,a) ≡ ( F (x,a) )T ∗ ȳ, ȳ ∈ IR , (3) versions of numerical simulation programs with potentially complicated intraand interprocedural flow of control can be generated automatically by AD tools [9, 11, 15, 25]. This technique has been proved extremely useful in the context of numerous applications of computational science and engineering requiring numerical methods that are based on derivative information [3, 5–7]. For the purpose of this paper we may assume trivial flow of control in the form of a straight-line program. Similarly, one may consider the evaluation of an arbitrary function at a given point to fix the flow of control. Our interest lies in the computation of the Jacobian of the active outputs (or dependent variables) y = (yj)j=1,...,m with respect to the active inputs (or independent variables) x = (xi)i=1,...,n. The n−vector a contains all passive inputs. Conceptually, AD decomposes the program into a sequence of scalar assignments vj = φj(vi)i≺j (4) for j = 1, . . . , p+m. where we follow the notation in [10]. We refer to Equation (4) as the code list of F, and we set xi = vi−n for i = 1, . . . , n and yj = vp+j for j = 1, . . . ,m. The vj , j = 1, . . . , p, are referred to as intermediate variables. The 1 F is used to refer to the given implementation. notation i ≺ j marks a direct dependence of vj on vi meaning that vi is an argument of the elemental function2 φj . The code list induces a directed acyclic graph G = (V,E) such that V = {v1−n, . . . , vp+m} and (i, j) ∈ E ⇔ i ≺ j. Assuming that all elemental functions are continuously differentiable at their respective arguments all local partial derivatives can be computed by a single evaluation of the linearized code list cj,i = ∂φj ∂vi (vk)k≺j ∀i ≺ j vj = φj(vi)i≺j for j = 1, . . . , p+m (5) for given values of x and a. The corresponding linearized computational graph is obtained by attaching the cj,i to the corresponding edges (i, j). An example is shown in Figure 1. It has been well-known for some time [2] that the entries of the Jacobian F (x,a) ≡ (fj,i) = ( ∂yj ∂xi )