4 ms·

There's a straight forward algorithm for automatic differentiation. You can think of it like long division: tedious to do, but you can easily program a compute

There's a straight forward algorithm for automatic differentiation. You can think of it like long division: tedious to do, but you can easily program a computer to do it. Integration is a whole different ball game. It's essentially a puzzle: what function, when differentiated, produces this result? There are various heuristics you can apply, e.g. integration by parts. And there are some databases of common integrals. But in the end, there's no algorithm, integration requires ingenuity to solve.

adamnemecek 6y ago
No, with automatic integration you presumably would not get the integrated function, the same way you don't with dual number autodiff.
IngoBlechschmid 6y ago
Exactly. Automatic differentiation works because we have the chain rule (f . g)'(x) = f'(g(x)) g'(x), telling us how to differentiate functions which are composed from simpler building blocks. But there is no analogous rule for integration.
- a1369209993 6y ago
  Technically there is: D f = f' <=> S f' = f # inverse # chain rule D (f . g) x = D f (g x) * D g x # divide by D g x D (f . g) x / D g x = (D f) (g x) # S vs D inverse D (S f' . g) x / D g x = (f' . g) x # commute = and integrate both sides S (f' . g) x = S \x( D (S f' . g) x / D g x ) x # rename and drop argument S (f . g) = S \x( D (S f . g) x / D g x ) The problem is that the RHS is, in the general case, not any less complex (and often much more) than the LHS. Edit: Note that (S f . g) is integrating only f, then composing with g, which is what you want; it's the S \x(...) that causes problems.
  - IngoBlechschmid 6y ago
    Nice observation, thank you for sharing!
Someone 6y ago
It’s slightly better. https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm: “The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations (+ − × ÷)” That algorithm isn’t easily programmed, though, and will fail in the many cases where the integral cannot be expressed in elementary functions. Worse, according to that page, it needs the ability to check whether expressions are zero (https://en.wikipedia.org/wiki/Constant_problem https://en.wikipedia.org/wiki/Constant_problem), and that, in general, is undecidable if I understand that page correctly. https://mathworld.wolfram.com/RischAlgorithm.html https://mathworld.wolfram.com/RischAlgorithm.html seems a tiny bit more optimistic about the limitations of this approach, but https://link.springer.com/chapter/10.1007/978-3-319-00894-3_10 https://link.springer.com/chapter/10.1007/978-3-319-00894-3_... seems, to me, in line with what Wikipedia says.
- pkaye 6y ago
  There is also an open source rule based integrator that I came across. https://rulebasedintegration.org/ https://rulebasedintegration.org/

adamnemecek 6y ago

No, with automatic integration you presumably would not get the integrated function, the same way you don't with dual number autodiff.

IngoBlechschmid 6y ago

Exactly. Automatic differentiation works because we have the chain rule (f . g)'(x) = f'(g(x)) g'(x), telling us how to differentiate functions which are composed from simpler building blocks. But there is no analogous rule for integration.

a1369209993 6y ago
Technically there is: D f = f' <=> S f' = f # inverse # chain rule D (f . g) x = D f (g x) * D g x # divide by D g x D (f . g) x / D g x = (D f) (g x) # S vs D inverse D (S f' . g) x / D g x = (f' . g) x # commute = and integrate both sides S (f' . g) x = S \x( D (S f' . g) x / D g x ) x # rename and drop argument S (f . g) = S \x( D (S f . g) x / D g x ) The problem is that the RHS is, in the general case, not any less complex (and often much more) than the LHS. Edit: Note that (S f . g) is integrating only f, then composing with g, which is what you want; it's the S \x(...) that causes problems.
- IngoBlechschmid 6y ago
  Nice observation, thank you for sharing!

Someone 6y ago

It’s slightly better. https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm: “The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations (+ − × ÷)” That algorithm isn’t easily programmed, though, and will fail in the many cases where the integral cannot be expressed in elementary functions. Worse, according to that page, it needs the ability to check whether expressions are zero (https://en.wikipedia.org/wiki/Constant_problem https://en.wikipedia.org/wiki/Constant_problem), and that, in general, is undecidable if I understand that page correctly. https://mathworld.wolfram.com/RischAlgorithm.html https://mathworld.wolfram.com/RischAlgorithm.html seems a tiny bit more optimistic about the limitations of this approach, but https://link.springer.com/chapter/10.1007/978-3-319-00894-3_10 https://link.springer.com/chapter/10.1007/978-3-319-00894-3_... seems, to me, in line with what Wikipedia says.

pkaye 6y ago
There is also an open source rule based integrator that I came across. https://rulebasedintegration.org/ https://rulebasedintegration.org/