On the complexity of the gradient of a rational function
Igor' Sergeevich Sergeev · Journal of Applied and Industrial Mathematics · 2008
The Baur-Strassen method implies L (∇ f ) ⩽ 4 L ( 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 ) ⩽ 3 L ( f ) + n , where n is the number of variables in f . In addition, the depth of a circuit for the gradient is estimated.