4 ms·
Does there exist a complete implementation of the Risch algorithm?
- jjtheblunt 3y agoI'd check Mathematica or Macaulay2...but how would you verify an implementation is complete?
- jychang 3y agoIt's written in the mathoverflow question, did you read it? > I have access to Maple 2018, and it doesn't seem to have a complete implementation either. A useful test case is the following integral, taken from the (apparently unpublished) paper Trager's algorithm for the integration of algebraic functions revisited by Daniel Schultz: ∫29x2+18x−3x6+4x5+6x4−12x3+33x2−16x−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√dx Schultz explicitly provides an elementary antiderivative in his paper, but Maple 2018 returns the integral unevaluated.
- deleted 3y ago[deleted]
- cvoss 3y agoThe question at hand is "how do you verify that an implementation is complete?", not "what is one test case whose failure would demonstrate that an implementation is incomplete?"
- jjtheblunt 3y agoYes, I read it. What you responded does not address what i asked. For example, you could have an implementation that handles the example you cited, but fails at others you did not mention. So would your comment claim "complete" for handling what you mentioned, when it is not?
- irrep 3y agoMathematica does not have a complete implementation of the Risch algorithm. It actually cannot do the integral in the mathoverflow question. Macaulay2 has a focus on commutative algebra and algebraic geometry and doesn't have an implementation of the Risch algorithm either.
- tehsauce 3y agoDoes this count? https://github.com/sympy/sympy/blob/master/sympy/integrals/risch.py https://github.com/sympy/sympy/blob/master/sympy/integrals/r...
- irrep 3y agoUnfortunately this is not complete, because it does not work with integrals that require algebraic extensions (they are more complicated than transcendental extensions).
- owalt 3y agoThis does not – according to what I can see from the code and comments – implement the case of algebraic extensions. As someone only really familiar with the implementation of the transcendental case[1], my understanding is that the algebraic case is where the major difficulty lies. [1]: Manuel Bronstein, Symbolic Integration I. Online: https://archive.org/details/springer_10.1007-978-3-662-03386-9/mode/2up https://archive.org/details/springer_10.1007-978-3-662-03386...
- downvotetruth 3y agohttps://news.ycombinator.com/item?id=589004 https://news.ycombinator.com/item?id=589004 https://news.ycombinator.com/item?id=19291578 https://news.ycombinator.com/item?id=19291578 Not sure of a connection between the failure of the high school axiom set / nonfiniteness of axioms and Rubi/rule based integration feasiblility or validity of Schanuel's conjecture.
- 1letterunixname 3y agoI wonder how Giac measures up as it's reportedly more general than HP48's Erable. https://en.wikipedia.org/wiki/Xcas#Giac https://en.wikipedia.org/wiki/Xcas#Giac PS: The HP 48 could also be used a very long distance remote to turn on and off all of the TVs in a lecture hall simultaneously. :)
- murkle 3y agoWhy not try the WebAssembly version? https://www-fourier.ujf-grenoble.fr/~parisse/xcasen.html https://www-fourier.ujf-grenoble.fr/~parisse/xcasen.html
- irrep 3y agoManuel Bronstein wrote a book [1] about symbolic integration, but unfortunately it only covers the transcendental part. There is also a shorter "tutorial" from some workshop [2]. [1] Manuel Bronstein: Symbolic Integration I, https://doi.org/10.1007/b138171 https://doi.org/10.1007/b138171 [2] https://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/issac98.pdf https://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/...
- slavapestov 3y agoSadly he passed away before completing Part 2. https://lists.gnu.org/archive/html/axiom-developer/2005-06/msg00109.html https://lists.gnu.org/archive/html/axiom-developer/2005-06/m...
- arthur2e5 3y agoI wonder if someone will make a publication out of his incomplete manuscripts. How many years do this kind of work take in the field of mathematics? Marx's Capital Volume IV took 20 years from his death to Kautsky's publication.
- globular-toast 3y agoI wrote a program to do symbolic integration as my undergrad project around 2010. I had (still have) Bronstein's book which I had pored over for the best part of a year. I had also visited his website[0] and found tons of useful info there. You know when you read so much of and about a person you almost feel like you know them? It wasn't until right at the end of the project I happened across an obituary[1]. He'd been dead the whole time. It was a very strange feeling. Like I had been in communication with a ghost. It's such a shame as I feel like he probably would have finished the Risch algorithm eventually. [0] https://www-sop.inria.fr/cafe/Manuel.Bronstein/ https://www-sop.inria.fr/cafe/Manuel.Bronstein/ [1] http://www.ccas.ru/sabramov/ps/PCS56.pdf http://www.ccas.ru/sabramov/ps/PCS56.pdf
- Havoc 3y agoNo idea, but I am impressed by the clarity and preciseness of the question
- 38 3y agowhy dont any of the users has scores by their name?
- vient 3y agoOn reloading scores are shown for a split second, interesting. Turning off ad blocker does not help, seems to be some JS inside the page. Edit: looks like MO added an option to hide rep which is turned on by default. You can find it in achievements menu at the upper right angle.
- dataflow 3y agoAnybody know why there doesn't exist a complete implementation? What makes the hardest portions so difficult to implement compared to the rest?
- userbinator 3y agohttps://en.wikipedia.org/wiki/Risch_algorithm#Decidability https://en.wikipedia.org/wiki/Risch_algorithm#Decidability seems to be the most difficult part; and it is unusual in that the Wikipedia article itself doesn't seem to clearly link to the original description of the algorithm.
- dataflow 3y agoThe comments underneath the post explain that zero-testing isn't the issue: https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm#comment948140_374089 https://mathoverflow.net/questions/374089/does-there-exist-a...
- xg15 3y agoStill a bit puzzled by it. It's no surprise that the algorithm is incomplete, if some of its subtasks are still open problems in math. (And therefore it has to resort to imperfect heuristics or try and detect classes of inputs for which no results can be generated) However, the OP and links sound as if even just implementing the existing algorithm spec is so insanely hard that no one has managed to do so yet for the entirety of it. It'd be interested to know what exactly makes it so hard. Wikipedia doesn't link to the actual spec unfortunately, though they do mention that the spec is something like 100 pages in size. Maybe that's a hint of the amount of complexity that is involved...