A note on the computational complexity of chain rule differentiation

被引：0

作者：

Naumann, U. ^{[1
,2
]}

机构：

[1] Rhein Westfal TH Aachen, Software & Tools Computat Engn, Aachen, Germany

[2] Rhein Westfal TH Aachen, Software & Tools Computat Engn, D-52062 Aachen, Germany

来源：

OPTIMIZATION METHODS & SOFTWARE | 2023年

关键词：

Chain rule of differentiation; computational complexity; algorithmic differentiation;

D O I：

10.1080/10556788.2023.2263809

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We generalize the proof of NP-completeness of Jacobian accumulation using a given number of floating-point operations to arbitrary order.

引用

页数：8

共 50 条

[1] NOTE ON COMPLEXITY OF ALGEBRAIC DIFFERENTIATION
CAVINESS, BF
EPSTEIN, HI
INFORMATION PROCESSING LETTERS, 1978, 7 (02) : 122 - 124
[2] THE CHAIN RULE OF DIFFERENTIATION IN SUPERSPACE
KOBAYASHI, Y
NAGAMACHI, S
LETTERS IN MATHEMATICAL PHYSICS, 1986, 11 (04) : 293 - 297
[3] A note on the computational complexity of graph vertex partition
Huang, Yuanqiu
Chub, Yuming
DISCRETE APPLIED MATHEMATICS, 2007, 155 (03) : 405 - 409
[4] On computational complexity of rule-based fault diagnosis
College of Energy and Power Technology, Harbin University of Technology, Harbin 150001, China
Dongli Gongcheng, 2007, 3 (372-375):
[5] COMPUTATIONAL COMPLEXITY OF INTEGRATION AND DIFFERENTIATION OF CONVEX FUNCTIONS
堵丁柱
Ker-I Ko
Systems Science and Mathematical Sciences, 1989, (01) : 70 - 79
[6] The generalized chain rule of differentiation with historical notes
Gould, HW
UTILITAS MATHEMATICA, 2002, 61 : 97 - 106
[7] A NOTE ON THE COMPUTATIONAL-COMPLEXITY OF BRACKETING AND RELATED PROBLEMS
KRIVANEK, M
LECTURE NOTES IN COMPUTER SCIENCE, 1989, 381 : 136 - 145
[8] A NOTE ON THE COMPUTATIONAL-COMPLEXITY OF HIGH CORRELATION ESTIMATORS
GIUNTA, G
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1991, 39 (02) : 485 - 486
[9] A note on universal measures for weak implicit computational complexity
Beckmann, A
LOGIC FOR PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND REASONING, 2002, 2514 : 53 - 67
[10] Computational Complexity of Allow Rule Ordering and Its Greedy Algorithm
Fuchino, Takashi
Harada, Takashi
Tanaka, Ken
Mikawa, Kenji
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2023, E106A (09) : 1111 - 1118

← 1 2 3 4 5 →