Rubi: Symbolic integrator based on an extensive system of integration rules(rulebasedintegration.org)
rulebasedintegration.org
Rubi: Symbolic integrator based on an extensive system of integration rules
https://rulebasedintegration.org/
27 comments
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.
Technically division is asymptotically as cheap as multiplication, but in practice you can't really utilize this.
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.
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).
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).
> 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://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...)
Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm, 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...)
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.
The problem is that what you’re comparing are not functions, but representations of functions.
Just determining the equality of two real numbers is difficult.
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.
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.
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.
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.
It's not that simple
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).
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).
> 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.”
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.”
What is so difficult about unfrying an egg :D.
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"!
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"!
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.
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]
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
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_equation...
https://12000.org/my_notes/kamek/kamke_differential_equation...
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.
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.
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.
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.
I encourage those interested in Computer Algebra Systems to read this comparison report: 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).
AFAIK, this is the only recent benchmark-type study that compares modern CAS software (Mathematica vs Maxima vs FriCAS vs etc).
Hopefully this can be integrated (no pun intended) into SymPy.
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.
Sadly, it appears that repo hasn’t been touched in a couple years.
That was my hope at first too, but it seems very unlikely. It's implemented in Mathematica and seems quite specific to Mathematica.