4 ms·

Rubi: Symbolic integrator based on an extensive system of integration rules

70 points by ducktective 2y ago

injidup 2y ago
What is it fundamentally about symbolic integration that makes it so much more difficult to do? I mean, I studied calculus and learned any number of the rules but it's a curious thing that one operation, differentiation is trivial, yet the opposite, integration is massively complex.
- mkl 2y ago
  This is a common feature of mathematics; doing many things is much easier in one direction than the reverse. Encryption systems are built on this idea, e.g. RSA relies on multiplication of large integers being very easy and factoring large integers being very hard. That doesn't really answer your question - I'm not sure there is a clear reason.
- chongli 2y ago
  There is no general algorithm to symbolically compute all integrals. All we have are partial algorithms which consist of big rulebooks for the cases we’ve already solved. It also turns out we can’t even verify, in general, the result of integration: Suppose you are given two functions, f(x) and G(x), and are told that G(x) is an antiderivative of f(x). So then you let g(x) = G’(x), the derivative of G(x). Now if G(x) is truly an antiderivative of f(x) then we must have g(x) = f(x) but unfortunately the problem of determining whether two functions are equal is undecidable (a consequence of the halting problem).
  - carbotaniuman 2y ago
    Does the functional equality being impossible to determine thing work for math problems? I know it works for computable functions, but math functions are pure and total so it seems easier.
    - chongli 2y ago
      Math functions are not total, in general. Computable functions are a subclass of all functions, so lots of functions are not computable. Purity doesn't apply to functions, it applies to algorithms which compute functions. In software parlance the terms are often conflated but they are not equivalent. The algorithm which computes a function is in general not unique.
    - kccqzy 2y ago
      Just determining the equality of two real numbers is difficult.
    - xigoi 2y ago
      The problem is that what you’re comparing are not functions, but representations of functions.
  - Someone 2y ago
    > There is no general algorithm to symbolically compute all integrals Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html https://mathworld.wolfram.com/RischAlgorithm.html) ‘only’ handles “rational functions, radicals, logarithms, and exponential functions”, but may never have been fully implemented (https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm https://mathoverflow.net/questions/374089/does-there-exist-a...)
- GrantMoyer 2y ago
  If you think of the variable being derived/integrated over as time, then conceptually the derivative at a time only represents information from that one time plus or minus some tiny delta, while an antiderivative repesents information from all of time. Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing.
  - almostgotcaught 2y ago
    It's not that simple https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra) https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(diffe... So it's important to keep in mind the difference between integral and anti-derivative. And note that as soon you say "within an epsilon" you're already on the other side of "not a lot of info" vs "infinite info". So global, local doesn't matter, especially since eg an analytic function is completely determined by it's derivatives at a single point (good ol Taylor's theorem).
  - 6gvONxR4sf7o 2y ago
    > Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing. I wonder if you could relate it to the difference between local and global sections on bundles and connect “global sections don’t always exist” to “global data is harder.”
- barrenko 2y ago
  What is so difficult about unfrying an egg :D.
  - ValentinA23 2y ago
    nothing https://www.livescience.com/49610-scientists-unboil-egg.html https://www.livescience.com/49610-scientists-unboil-egg.html
    - CoreformGreg 2y ago
      A team of four PhDs + seven other academics manage to unfold a single protein in an egg white using a "vortex fluid device" to produce a Couette flow, heat treatment, dilution in phosphate-buffered saline, dissolution in ureal, use of recombinant proteins, etc., etc., Meanwhile, my four-year old niece can boil a dozen eggs in the time it took me to read their paper. I think it's still accurate to say unboiling an egg is "difficult"!
- eigenket 2y ago
  Let's say you have a library of functions you know how to integrate and differentiate. Something that happens a lot is that you end up wanting to do integrate or differentiate a product like x -> f(x)g(x) or composition like x -> f(g(x)) of two or more of the functions you know about. For diffentiation there are two ridiculously powerful theorems which says that if you know how to differentiate a bunch of functions you can also differentiate any product or composition of these functions. For a random other map there is no reason for this to be the case, integration is essentially "as expected" in that except in some specific circumstances knowing how to integrate f and g doesn't tell you how to integrate their product or composition.
  - deleted 2y ago
    [deleted]
- namibj 2y ago
  Technically division is asymptotically as cheap as multiplication, but in practice you can't really utilize this.
hobscoop 2y ago
Rubi is great. When I'm stuck on an integral in Mathematica with the builtin Integrate, I load up Rubi and sometimes it can find a solution.
Y_Y 2y ago
I used this a while back to do an awkward integral that no other CAS was able to do and was able to show up a paper that had claimed there was no closed-form solution. Unfortunately the answer was in terms of hypergeometric functions and was scarcely more useful than the unevaluated integral. In any case I found Rubi to be very impressivein terms of results. Digging into the code wasn't much fun, as it's just a colossal Mathematica rules engine, like reading Gradshteyn and Ryzhik, but with square brakets everywhere.
ducktective 2y ago
I encourage those interested in Computer Algebra Systems to read this comparison report: https://www.12000.org/my_notes/CAS_integration_tests/reports/summer_2022/indexchapter1.htm#x2-10001 https://www.12000.org/my_notes/CAS_integration_tests/reports... AFAIK, this is the only recent benchmark-type study that compares modern CAS software (Mathematica vs Maxima vs FriCAS vs etc).
amelius 2y ago
Hopefully this can be integrated (no pun intended) into SymPy.
- ducktective 2y ago
  From Rubi install guide: >The SymPy (Symbolic Python) CAS also intends to incorporate Rubi’s integration rules. The code for Rubi is in the sympy/integrals/rubi subdirectory of the SymPy source-code on GitHub. Also: https://github.com/sympy/rubi https://github.com/sympy/rubi
  - staplung 2y ago
    Sadly, it appears that repo hasn’t been touched in a couple years.
- mkl 2y ago
  That was my hope at first too, but it seems very unlikely. It's implemented in Mathematica and seems quite specific to Mathematica.
pkaye 2y ago
There is a Golang based CAS that follows the Mathematica language which makes use of Rubi for integration. https://github.com/corywalker/expreduce https://github.com/corywalker/expreduce
krackers 2y ago
This is cool! The page by Abbasi they link to also contains a comparison between MMA and Maple in solving differential equations https://12000.org/my_notes/kamek/kamke_differential_equations.htm https://12000.org/my_notes/kamek/kamke_differential_equation...
wdkrnls 2y ago
Has anyone looked at writing a script to transform those rules for yacas? Making yacas 94% as good as Mathematica at integration sounds like a worthy goal considering how easy it is to deploy it.

70 points by ducktective 2y ago

What is it fundamentally about symbolic integration that makes it so much more difficult to do? I mean, I studied calculus and learned any number of the rules but it's a curious thing that one operation, differentiation is trivial, yet the opposite, integration is massively complex.

mkl 2y ago
This is a common feature of mathematics; doing many things is much easier in one direction than the reverse. Encryption systems are built on this idea, e.g. RSA relies on multiplication of large integers being very easy and factoring large integers being very hard. That doesn't really answer your question - I'm not sure there is a clear reason.
chongli 2y ago
There is no general algorithm to symbolically compute all integrals. All we have are partial algorithms which consist of big rulebooks for the cases we’ve already solved. It also turns out we can’t even verify, in general, the result of integration: Suppose you are given two functions, f(x) and G(x), and are told that G(x) is an antiderivative of f(x). So then you let g(x) = G’(x), the derivative of G(x). Now if G(x) is truly an antiderivative of f(x) then we must have g(x) = f(x) but unfortunately the problem of determining whether two functions are equal is undecidable (a consequence of the halting problem).
- carbotaniuman 2y ago
  Does the functional equality being impossible to determine thing work for math problems? I know it works for computable functions, but math functions are pure and total so it seems easier.
  - chongli 2y ago
    Math functions are not total, in general. Computable functions are a subclass of all functions, so lots of functions are not computable. Purity doesn't apply to functions, it applies to algorithms which compute functions. In software parlance the terms are often conflated but they are not equivalent. The algorithm which computes a function is in general not unique.
  - kccqzy 2y ago
    Just determining the equality of two real numbers is difficult.
  - xigoi 2y ago
    The problem is that what you’re comparing are not functions, but representations of functions.
- Someone 2y ago
  > There is no general algorithm to symbolically compute all integrals Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html https://mathworld.wolfram.com/RischAlgorithm.html) ‘only’ handles “rational functions, radicals, logarithms, and exponential functions”, but may never have been fully implemented (https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm https://mathoverflow.net/questions/374089/does-there-exist-a...)
GrantMoyer 2y ago
If you think of the variable being derived/integrated over as time, then conceptually the derivative at a time only represents information from that one time plus or minus some tiny delta, while an antiderivative repesents information from all of time. Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing.
- almostgotcaught 2y ago
  It's not that simple https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra) https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(diffe... So it's important to keep in mind the difference between integral and anti-derivative. And note that as soon you say "within an epsilon" you're already on the other side of "not a lot of info" vs "infinite info". So global, local doesn't matter, especially since eg an analytic function is completely determined by it's derivatives at a single point (good ol Taylor's theorem).
- 6gvONxR4sf7o 2y ago
  > Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing. I wonder if you could relate it to the difference between local and global sections on bundles and connect “global sections don’t always exist” to “global data is harder.”
barrenko 2y ago
What is so difficult about unfrying an egg :D.
- ValentinA23 2y ago
  nothing https://www.livescience.com/49610-scientists-unboil-egg.html https://www.livescience.com/49610-scientists-unboil-egg.html
  - CoreformGreg 2y ago
    A team of four PhDs + seven other academics manage to unfold a single protein in an egg white using a "vortex fluid device" to produce a Couette flow, heat treatment, dilution in phosphate-buffered saline, dissolution in ureal, use of recombinant proteins, etc., etc., Meanwhile, my four-year old niece can boil a dozen eggs in the time it took me to read their paper. I think it's still accurate to say unboiling an egg is "difficult"!
eigenket 2y ago
Let's say you have a library of functions you know how to integrate and differentiate. Something that happens a lot is that you end up wanting to do integrate or differentiate a product like x -> f(x)g(x) or composition like x -> f(g(x)) of two or more of the functions you know about. For diffentiation there are two ridiculously powerful theorems which says that if you know how to differentiate a bunch of functions you can also differentiate any product or composition of these functions. For a random other map there is no reason for this to be the case, integration is essentially "as expected" in that except in some specific circumstances knowing how to integrate f and g doesn't tell you how to integrate their product or composition.
- deleted 2y ago
  [deleted]
namibj 2y ago
Technically division is asymptotically as cheap as multiplication, but in practice you can't really utilize this.

hobscoop 2y ago

Rubi is great. When I'm stuck on an integral in Mathematica with the builtin Integrate, I load up Rubi and sometimes it can find a solution.

Y_Y 2y ago

I used this a while back to do an awkward integral that no other CAS was able to do and was able to show up a paper that had claimed there was no closed-form solution. Unfortunately the answer was in terms of hypergeometric functions and was scarcely more useful than the unevaluated integral. In any case I found Rubi to be very impressivein terms of results. Digging into the code wasn't much fun, as it's just a colossal Mathematica rules engine, like reading Gradshteyn and Ryzhik, but with square brakets everywhere.

ducktective 2y ago

I encourage those interested in Computer Algebra Systems to read this comparison report: https://www.12000.org/my_notes/CAS_integration_tests/reports/summer_2022/indexchapter1.htm#x2-10001 https://www.12000.org/my_notes/CAS_integration_tests/reports... AFAIK, this is the only recent benchmark-type study that compares modern CAS software (Mathematica vs Maxima vs FriCAS vs etc).

amelius 2y ago

Hopefully this can be integrated (no pun intended) into SymPy.

ducktective 2y ago
From Rubi install guide: >The SymPy (Symbolic Python) CAS also intends to incorporate Rubi’s integration rules. The code for Rubi is in the sympy/integrals/rubi subdirectory of the SymPy source-code on GitHub. Also: https://github.com/sympy/rubi https://github.com/sympy/rubi
- staplung 2y ago
  Sadly, it appears that repo hasn’t been touched in a couple years.
mkl 2y ago
That was my hope at first too, but it seems very unlikely. It's implemented in Mathematica and seems quite specific to Mathematica.

pkaye 2y ago

There is a Golang based CAS that follows the Mathematica language which makes use of Rubi for integration. https://github.com/corywalker/expreduce https://github.com/corywalker/expreduce

krackers 2y ago

This is cool! The page by Abbasi they link to also contains a comparison between MMA and Maple in solving differential equations https://12000.org/my_notes/kamek/kamke_differential_equations.htm https://12000.org/my_notes/kamek/kamke_differential_equation...

wdkrnls 2y ago

Has anyone looked at writing a script to transform those rules for yacas? Making yacas 94% as good as Mathematica at integration sounds like a worthy goal considering how easy it is to deploy it.