On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs
On optimality preserving eliminations for the minimum edge count and optimal Jacobian accumulation problems in linearized DAGs
复制标题
线性化 DAG 中最小边数和最优雅可比累积问题的最优保留消除
DOI：
10.1080/10556788.2011.580745
复制
发表时间：
2012
影响因子：
2.2
通讯作者：
Mosenkis V
中科院分区：
文献类型：
--
作者：
Mosenkis V
线性化有向无环图的最小边数和最优雅可比积问题是由微分学链法则的结合性所导出的组合数学问题的结果。本文讨论了一个合适的图形形式主义，然后证明了一些结果，产生了相当大的搜索空间减少这两个问题。建立了数值分析和理论计算机科学之间的算法联系。虽然这两个问题被认为是NP-困难的一般，线性时间算法解决theMEC问题的一个指定的子类的l-DAGs。
The minimum edge count (MEC) and optimal Jacobian accumulation problems in linearized directed acyclic graphs (DAGs) result from the combinatorics induced by the associativity of the chain rule of differential calculus. This paper discusses a suitable graph formalism followed by proving a number of results that yield a considerable search space reduction for both problems. An algorithmic link between numerical analysis and theoretical computer science is established. Although both problems are believed to be NP-hard in general, a linear-time algorithm is presented solving theMECproblem for a specified subclass of l-DAGs.
登录
查看更多内容
关于有向图顶点消除的NP完备性的一个注解
DOI：
--
发表时间：
1980
期刊：
SIAM J. Algebraic Discret. Methods
影响因子：
--
作者：
J. Gilbert
通讯作者：
J. Gilbert
影响因子：
2.7
作者：
U. Naumann
通讯作者：
U. Naumann
DOI：
10.1007/978-3-540-68942-3
发表时间：
2008-07
期刊：
--
影响因子：
--
作者：
C. Bischof;H. M. Bücker;P. Hovland;U. Naumann;J. Utke
通讯作者：
C. Bischof;H. M. Bücker;P. Hovland;U. Naumann;J. Utke
雅可比稀缺性的分析与利用
DOI：
--
发表时间：
2003
期刊：
International Conference on High Performance Scientific Computing
影响因子：
--
作者：
A. Griewank;Olaf Vogel
通讯作者：
Olaf Vogel
自动微分：应用、理论和实现（计算科学与工程讲义）
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
Martin Bücker;G. Corliss;P. Hovland;U. Naumann;Boyana Norris
通讯作者：
Boyana Norris