Timeline for Complexity of computing derivatives
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2021 at 18:58 | answer | added | Sébastien Loisel | timeline score: 2 | |
| Sep 20, 2011 at 6:56 | vote | accept | onemoreuser | ||
| Aug 24, 2011 at 19:50 | comment | added | Gerhard Paseman | As an illustration, consider (x - 7)^64. In some systems this will take over 60 operations to evaluate, while in others it will take less than 10. If you represent a function as a dataflow diagram with just-in-time evaluation, and use that to derive a similar diagram to represent computing the derivative, I see a potential for exponential blow up. The way in which you perform the T operations is important. Gerhard "Ask Me About Data Flow" Paseman, 2011.08.24 | |
| Aug 24, 2011 at 19:41 | comment | added | Gerhard Paseman | I do not know what the bound is in general. I decided that giving a poor bound for a general situation was better, and to wait for "arithmetic operations" to be made explicit before offering improvements. For polynomials there should be better than exponential bounds, PROVIDED you are given a method like Horner's to evaluate the polynomial and the representation allows it. I suggested exponential because the chain rule requires you to compute two derivatives and at least two compositions from a function having a composition. Gerhard "Ask Me About System Design" Paseman, 2011.08.24 | |
| Aug 24, 2011 at 19:29 | answer | added | Robert Israel | timeline score: 12 | |
| Aug 24, 2011 at 19:21 | comment | added | onemoreuser | @Gerhard, is exponential really the best possible? @Emil, good point. Maybe I should generalise to ask for the case when $f(x)$ is numerically approximatable to accuracy $\epsilon$? So if $f$ is essentially a polynomial, then we should be able to compute its gradient in cT operations for some constant $c$, is that true? | |
| Aug 24, 2011 at 19:16 | comment | added | Emil Jeřábek | Since $f$ is computable using finitely many arithmetic operations, it is (at least piecewise) a polynomial, right? | |
| Aug 24, 2011 at 19:04 | comment | added | Gerhard Paseman | I believe the answer is yes, and the bound is given by appropriate applications of the Chain Rule. You might look at algorithms for symbolic computation of the derivative, unless you want a numeric result. Then you can probably get a bound that is roughly exponential in the number of multiplications (or compositions perhaps) used in computing f. Gerhard "Ask Me About System Design" Paseman, 2011.08.24 | |
| Aug 24, 2011 at 18:45 | history | asked | onemoreuser | CC BY-SA 3.0 |