Optimal Jacobian accumulation is NP-complete
成果类型：
Article
署名作者：
Naumann, Uwe
署名单位：
RWTH Aachen University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-006-0042-z
发表日期：
2008
页码：
427-441
关键词：
摘要：
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.
来源URL：