On the complexity of the gradient of a rational function |
| |
Authors: | I S Sergeev |
| |
Institution: | (1) Department of Mechanics and Mathematics, Moscow State University, Vorob’ovy gory, Moscow, 119991, Russia |
| |
Abstract: | The Baur-Strassen method implies L(?f) ? 4L(f), where L(f) is the complexity of computing a rational function f by arithmetic circuits, and ?f is the gradient of f. We show that L(? f) ? 3L(f) + n, where n is the number of variables in f. In addition, the depth of a circuit for the gradient is estimated. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|