Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello! I wonder how hard is it to implement more or less general symbolic integration algorithm (number of lines in a certain language)? Maybe someone here did this or knows some good blog posts devoted to the subject.

And how hard is it to implement an algorithm to decide whether a given function could be integrated (in terms of elementary functions)?

I don't mean integrating only rational functions, something more general.

What's the easiest method to start (except integrating rational functions)?

share|improve this question
2  
Not really the kind of question this website is here for - please see the faq. Also, search for Risch algorithm. –  Gerry Myerson Jun 14 '11 at 5:30
    
Not sure the Rish algorithm (actually its generalizations) is something easy to implement. Anyway it requires some additional heuristics that makes it scary. I was thinking of parallel integration as a possible candidate but right now I haven't got any good introduction to the subject. (I'm searching now the second edition of Bronstein's book). –  Yrogirg Jun 14 '11 at 10:21
add comment

2 Answers

up vote 4 down vote accepted

Perhaps pmint, The Poor Man's Integrator,

http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/index.html

is of interest to you (<100 lines Maple).

The page contains also references to the literature and examples. Moreover, searching for Poor Man's Integrator turns up a couple of related and recent online discussions.

share|improve this answer
    
Yes, I shall study this. Maybe the discussion you mentioned: groups.google.com/group/sci.math.symbolic/browse_thread/thread/… A parallel integration in FriCAS seems to be also short. Guess it is quite close to the pmint: groups.google.com/group/fricas-devel/browse_thread/thread/… –  Yrogirg Jun 14 '11 at 15:34
    
It is my understanding (mainly based on what I picked-up reading relevant newsgroups) that FriCAS and OpenAxiom (both stemming from Axiom, or so I believe) are in a certain sense leading regarding integration. I could also imagine that looking into what was done for SymPy sympy.org might be relevant for you, as I believe they somewhat recently create something related to this. But, regarding things like this I guess the mailing-lists of the relevant projects will be the best venues to get information. Certainly and unfortunately, I cannot say much more then I did. Good luck! –  quid Jun 14 '11 at 16:00
add comment

It partly depends on how much you want to be able to integrate and how much machinery you can take for granted (factorization of polynomials, rewriting trig functions in terms of tan for example.) Is this mainly curiosity?

This is probably not news to you, but if differentiation is automatic and you can put in a suggested form for the answer, then undetermined coefficients is "easy." So if you want to evaluate $$\int x^3\cos^5xe^{3x}dx$$ and can tell the program that the answer should be of the form $$\sum_{n=0}^2 [(a_{n}\sin(x)\cos^{2n}(x)+b_{n}\cos^{2n+1}(x))e^{3x}+(c_{n}\sin(x)\cos^{2n}(x)+d_{n}\cos^{2n+1}(x))]$$ where the $a,b,c,d$ are all polynomials of degree $3$ in $x$, then the program has, after differentiation, a system of linear equations in 48 variables which either has a solution or does not. If we knew less about the solution we might have thrown in more terms. In fact we might know that the $c$ and $d$ polynomials are $0$ so this cuts it down to a more manageable $24$ unknowns and linear algebra. It might be smoother to use multiple angles like $\cos(5x)$ in place of powers.

My impression is that a large part of machine symbolic integration consists of having the machinery to efficiently give a form for the possible solution and check for one, along with the theorems to say that when this fails there is no closed form solution in terms of the menu of functions allowed.

share|improve this answer
    
Well, my primary goal was to implement symbolic integration in Haskell and to actually feel how it is done. Although there is not much machinery I have by now in Haskell (rewriting trig functions in terms of tan is not there for sure), but I hope it won't be prohibitively hard to implement it by myself. Haskell has some sort of pattern matching, I have symbolic differentiation done (really easy) with it. –  Yrogirg Jun 15 '11 at 13:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.