Risch algorithm for Symbolic Integration -GSOC Idea

[Anurag Sharma]

Hello everyone.

This post is regarding the gsoc idea of implementing (or continuing ) the work of Aaron Meurer and Chetna Gupta on implementation of Risch Algorithm for symbolic integrations. I have gone through the PR mentioned on the ideas page. It seems there has been good progress last summer.
I have fairly decent background in abstract algebra and universal algebra. Though I haven't formally done anything related to Differential Algebra.

I wished to know the following things:

1. There are 3 remaining tasks mentioned in the PR. Would it be okay to start on one of them ? (Most probably the one which asks to not hard code the value of 'a' )

2. Has there been any progress other than that mentioned in that PR?

3. I have skimmed through the first chapter of Bronstein's book. Algebraic Preliminaries. Nothing new there. But the second chapter introduces algorithms which I have never implemented and some of them I had not even heard of. I would be really glad if you could tell me what sort of mathematical background is required to contribute efficiently to this part of the project.

I would be really glad if you could link me to some literature on net which explains the Risch algorithm and implementation issues. In the meanwhile I'll try to procure the mentioned text from my college library.

Apart from Aaron Meurer and Chetna Gupta who else has worked on this part ? It would be really nice if I knew more people familiar to this part of sympy so that I wont have to bug Aaron with every little issue :).. I have tried contacting Chetna but I guess she is not much active now.

Cheers
Anurag
 

[Aaron Meurer]

On Wed, Jan 22, 2014 at 8:30 AM, Anurag Sharma <anur...@gmail.com> wrote:
> Hello everyone.
>
> This post is regarding the gsoc idea of implementing (or continuing ) the
> work of Aaron Meurer and Chetna Gupta on implementation of Risch Algorithm
> for symbolic integrations. I have gone through the PR mentioned on the ideas
> page. It seems there has been good progress last summer.
> I have fairly decent background in abstract algebra and universal algebra.
> Though I haven't formally done anything related to Differential Algebra.
>
> I wished to know the following things:
>
> 1. There are 3 remaining tasks mentioned in the PR. Would it be okay to
> start on one of them ? (Most probably the one which asks to not hard code
> the value of 'a' )

Yes, finishing this PR is probably the best place to start. I would
create a new branch based off the PR branch and submit a new PR (we
can close the old one when you do this).

>
> 2. Has there been any progress other than that mentioned in that PR?

No.

>
> 3. I have skimmed through the first chapter of Bronstein's book. Algebraic
> Preliminaries. Nothing new there. But the second chapter introduces
> algorithms which I have never implemented and some of them I had not even
> heard of. I would be really glad if you could tell me what sort of
> mathematical background is required to contribute efficiently to this part
> of the project.

Well really Bronstein's book is self-contained. The unfortunate thing
for you is that half of it is already implemented, so the
prerequisites are really more like "the first half of Bronstein's
book". I think you have a good opportunity to catch up, especially
since you are still early. You should read through chapter 2. This
gives a more algorithmic introduction to abstract algebra than you may
have seen before. Chapter 3 gives a good understanding of the rational
algorithm, but it is not necessary to understand all the algorithms
there, except the Lazard-Rioboo-Trager, which is the one actually
used. This is important because the full algorithm is just an
extension of this algorithm, so understanding the basics of how it
works is important. Chapter 4 is entirely theoretical. You should get
an understanding of differential algebra, but a deep understanding of
chapter 4 is not fully required. Most of it is just there to prove the
theorems, particularly the Liouville theorem. A lot of it is there
only to prove the algebraic case, which is not even described in the
book. It really depends on how you learn, though. If you feel you
learn better by really understanding all the mathematics, then you
should read chapter 4 more carefully.

Chapter 5 is the most important. This you should read and understand
(with the possible exception of the proof of Liouville's theorem,
assuming I remember correctly that it's in this chapter). This is the
"base" algorithm. Most of it is already implemented, in risch.py.

Chapters 6, 7, and 8 are nitty-gritty details of the sub-algorithms.
You really don't need to worry so much about the parts that are
already implemented. It depends on what you plan to do in your project
too, but in many cases you can worry about things when you get to them
too.

Chapter 9 is more heavy on the math than what you really need to know
to implement it.

I recommend starting with chapter 2. Try to find the implementation in
SymPy of the algorithms as you go through them, and play with them
using your own inputs. This will help you learn SymPy and the polys
module as well (the polys module can be a bit confusing so let us know
if you can't figure stuff out with it).

You should also try to follow the Risch code, say for some simple
inputs, alongside the pseudocode in Bronstein. Don't worry too much
about the code in DifferentialExtension to start with.

>
> I would be really glad if you could link me to some literature on net which
> explains the Risch algorithm and implementation issues. In the meanwhile
> I'll try to procure the mentioned text from my college library.

Read Bronstein's "symbolic integration tutorial" (you can find it for
free on his website). This gives a broad outline of the full
algorithm. Note that his book only covers about a third of the full
algorithm (namely, just the pure transcendental part), so don't worry
too much if you can't follow the algebraic part parts.

Beyond that, Bronstein's book really is the best source, so I would
stick to it for the most part. The book is extremely well written, so
you shouldn't have too many issues with it.

>
> Apart from Aaron Meurer and Chetna Gupta who else has worked on this part ?
> It would be really nice if I knew more people familiar to this part of sympy
> so that I wont have to bug Aaron with every little issue :).. I have tried
> contacting Chetna but I guess she is not much active now.

Sorry, it's just us. Raoul might be able to tell you a few things too.
I would most likely be the one to mentor the project if it were
accepted, though. You should just keep your communications on this
list, and I will respond. Or if you want to chat you can use IRC or
gitter (https://gitter.im/sympy/sympy).

Aaron Meurer

>
> Cheers
> Anurag
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> For more options, visit https://groups.google.com/groups/opt_out.

[someone]

> > 3. I have skimmed through the first chapter of Bronstein's book.
> > Algebraic Preliminaries. Nothing new there. But the second chapter
> > introduces algorithms which I have never implemented and some of
> > them I had not even heard of. I would be really glad if you could
> > tell me what sort of mathematical background is required to
> > contribute efficiently to this part of the project.
>
> Well really Bronstein's book is self-contained. The unfortunate thing
> for you is that half of it is already implemented, so the
> prerequisites are really more like "the first half of Bronstein's
> book". I think you have a good opportunity to catch up, especially
> since you are still early. You should read through chapter 2. This
> gives a more algorithmic introduction to abstract algebra than you may
> have seen before. Chapter 3 gives a good understanding of the rational
> algorithm, but it is not necessary to understand all the algorithms
> there, except the Lazard-Rioboo-Trager, which is the one actually
> used. This is important because the full algorithm is just an
> extension of this algorithm, so understanding the basics of how it
> works is important. Chapter 4 is entirely theoretical. You should get
> an understanding of differential algebra, but a deep understanding of
> chapter 4 is not fully required. Most of it is just there to prove the
> theorems, particularly the Liouville theorem. A lot of it is there
> only to prove the algebraic case, which is not even described in the
> book.

We all miss the volume II he wanted to write :-(

Yes, this a great "short version".
There is also a Thesis called "Symbolic Integration"
by BJÖRN TERELIUS. (You should be able to find this on
the net, otherwise I'll send you a copy.)

[Aaron Meurer]

There is also some paper that I found pretty useful for understanding
the extension tower concept. I can't remember who wrote it or what
it's called. It might not even be a paper, just a chapter from a
textbook on computer algebra, but I do remember that it has the
example from https://code.google.com/p/sympy/issues/detail?id=2010#c1.

There are also a ton of references in Bronstein's book.

But I would always start with Bronstein, because his writing is the
best, and then fill the gaps with other resources.

Aaron Meurer

[Anurag Sharma]

Hi Aaron
Thanks for your reply. I have got hold of Bronstein book and the tutorial. I find the tutorial much more accessible right now. I think I will go through it first and worry about the correctness of algorithms later.

I don't find all the algorithms being implemented in sympy (eg Bernoulli, Hermite Reduction etc. ). And I guess we done need them when we have better ones available.
Expect some queries and doubts related to maths involved in next couple of days while I read on.

Cheers
Anurag

[Aaron Meurer]

On Fri, Jan 24, 2014 at 11:39 AM, Anurag Sharma <anur...@gmail.com> wrote:
> Hi Aaron
> Thanks for your reply. I have got hold of Bronstein book and the tutorial. I
> find the tutorial much more accessible right now. I think I will go through
> it first and worry about the correctness of algorithms later.
>
> I don't find all the algorithms being implemented in sympy (eg Bernoulli,
> Hermite Reduction etc. ). And I guess we done need them when we have better
> ones available.

The rational algorithms are implemented in rationaltools.py. The
polynomial algorithms (that have nothing to do with integration) are
buried in the polys module. The risch algorithms are in risch.py,
rde.py, and prde.py.

Aaron Meurer

[Chetna Gupta]

Hi All

This is such a big nostalgia moment! @Anurag There are three tasks mentioned on the PR. One of them being
-> Don't hardcode the value of a in the functions in cds.py. And the input should be a, not sqrt(a), (so, e.g., the input should be -1, not sqrt(-1))
I would try to solve this and would like to illustrate the code-blocks in the above mentioned file(cds.py) so that you can understand the code flow
within files and between different files.<Updates on the PR>

In particular inside sympy/intergrals module we have "risch_integrate" function, which is suppose to be do the magic of integrating any elementary function. It indeed is an abstraction for all the function calls, coded in different files in the above mentioned module.
As suggested by Aaron, Manuel Bronstein is the best place to start with. Try going through the book and you'll realize that the code implemented is a lot more similar to the sections in the book.

[Anurag Sharma]

On Sunday, February 2, 2014 5:45:39 AM UTC+5:30, Chetna Gupta wrote:

Hi All

This is such a big nostalgia moment! @Anurag There are three tasks mentioned on the PR. One of them being
-> Don't hardcode the value of a in the functions in cds.py. And the input should be a, not sqrt(a), (so, e.g., the input should be -1, not sqrt(-1))
I would try to solve this and would like to illustrate the code-blocks in the above mentioned file(cds.py) so that you can understand the code flow
within files and between different files.<Updates on the PR>

 No please dont solve it on your own. I would be really glad if we could fix some time on the irc and then you help me solve the issue. It would make the process easier for me for the next time. Anytime suits me. Either reply here or email me(I had sent an email from my institute id.).

In particular inside sympy/intergrals module we have "risch_integrate" function, which is suppose to be do the magic of integrating any elementary function. It indeed is an abstraction for all the function calls, coded in different files in the above mentioned module.

Yeah i am reading the code (although as mentioned in my other post last week had been dull. I would really appreciate it if we could directly chat on irc it would help me solve some noob issues which I are too obvious to ask on mailing list :P.

As suggested by Aaron, Manuel Bronstein is the best place to start with. Try going through the book and you'll realize that the code implemented is a lot more similar to the sections in the book.

Yeah, I am halfway through the second chapter. But its a big book and may take time to reach the relevant portion. Is it possible to understand the code before understanding the complete math of differential fields ? I have strong background in Universal Algebra/Lattices/Rings etc. But havent formally covered Differential fields. I am reading through the book and asking for help on forums like (math.stackexchange) but the process is slow.

[Anurag Sharma]

Hi

While going through some of the risch algorithm code, I couldn't understand few of the docstrings.
One of them is quoted here:

"DE.D is a list of the derivatives of x, t1, t2, ..., tn-1 = t, DE.T is the list [x, t1, t2, ..., tn-1], DE.t is the
outer-most variable of the differential extension at the given level (the level
can be adjusted using DE.increment_level() and DE.decrement_level()),
k is the field C(x, t0, ..., tn-2), where C is the constant field.  The
numerator of a fraction is denoted by a and the denominator by
d.  If the fraction is named f, fa == numer(f) and fd == denom(f).
Fractions are returned as tuples (fa, fd).  DE.d and DE.t are used to
represent the topmost derivation and extension variable, respectively."

I do not understand what is the difference in DE.D and DE.T ?
And also the last line. Kindly be lucid.

These are hurriedly asked questions I might be able to get them after some more thought, but its better to put them on the mailing list maybe someone else stuck can also get help from these. :)

Cheers

[Aaron Meurer]

On Feb 23, 2014, at 9:58 AM, Anurag Sharma <anur...@gmail.com> wrote:

Hi

While going through some of the risch algorithm code, I couldn't understand few of the docstrings.
One of them is quoted here:

"DE.D is a list of the derivatives of x, t1, t2, ..., tn-1 = t, DE.T is the list [x, t1, t2, ..., tn-1], DE.t is the
outer-most variable of the differential extension at the given level (the level
can be adjusted using DE.increment_level() and DE.decrement_level()),
k is the field C(x, t0, ..., tn-2), where C is the constant field.  The
numerator of a fraction is denoted by a and the denominator by
d.  If the fraction is named f, fa == numer(f) and fd == denom(f).
Fractions are returned as tuples (fa, fd).  DE.d and DE.t are used to
represent the topmost derivation and extension variable, respectively."

I do not understand what is the difference in DE.D and DE.T ?
And also the last line. Kindly be lucid.

The risch algorithm is implemented recursively. You work only with the top most variable, which is DE.t. I suggest creating some differential extensions to see how they work. Try DifferentialExtension(log(exp(x**2) + 1), x, dummy=False) (dummy=False will prevent it from using dummy variables, which will make it easier to manipulate). This extension will be, mathematically, Q(, x, t0, t1), where t0 = exp(x**2) and t1 = log(t0 + 1). These are really defined by their derivatives, so Dt0 = 2*x*t0 and Dt1 = 2*x*t0/(t0 + 1). These expressions are in the D list. They are used to take the derivative of other expressions in terms of x, t0, and t1 in derivation(). DE.t would be t1 and DE.d would be 2*x*t0/(t0 + 1). 

Usually you only care about the top level, i.e., DE.d and DE.t.

Aaron Meurer

These are hurriedly asked questions I might be able to get them after some more thought, but its better to put them on the mailing list maybe someone else stuck can also get help from these. :)

Cheers

--

[Anurag Sharma]

Can some one explain me whats going on in this lemma ?? I am towards finishing the reading portion of risch algorithm and I am stuck here..
@Aaron
You might know this. The author is just explaining how to integrate the polynomial part over the field extension. I guess the recursive implementation you told me on the previous post, the recursion on the algebraic(elementary field) extension of the the original field. Right ?

[Aaron Meurer]

What reference is this from? It would be easier to say what is going on with more context. Can you find the corresponding part in Bronstein?

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/5e1ddd0b-d482-4302-bee2-f070e3b155a6%40googlegroups.com.

[Anurag Sharma]

Here's the link to the masters thesis I am refering to. I find it more easy going than bronstein. As it uses less maths (Differential algebra)
http://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2009/rapporter09/terelius_bjorn_09095.pdf

Part I asked is in Chapter 5. Polynomial 5.1.1

--
You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/bYHtVOmKEFs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6%2BG%2BgP69aE%3DGL3GOyRPZu1_YaUjXx98RauZeGo2bYC3yQ%40mail.gmail.com.

[Aaron Meurer]

Thanks. It's kind of important to know that theta is a logarithm here.

So the corresponding part in Bronstein is 5.8. I recommend reading that and seeing if you understand it better. Another good reason to read Bronstein is that the math is accompanied with pseudocode, which is the exact code that is implemented. So you can lookup that exact algorithm in risch.py (https://github.com/sympy/sympy/blob/master/sympy/integrals/risch.py#L1252).

The way that I like to understand code is to step through it with a debugger (I prefer PuDB). You can also use print if that works for you. Try stepping through that function with log(x)**2 + 2*log(x) + 1 or something.

Sorry if this is a vague answer, but I'm a little unclear on what exactly your question is. If you can give me a more specific question, I can give you a more specific answer.

Aaron Meurer

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAOYHqH-OAFNuLdqUSLNXJnSKzJoLWg4FsKWxmSRG%2BbfDkvsvrA%40mail.gmail.com.

[Anurag Sharma]

Hi Aaron
I guess I got it from Bronstein's book. I agree that the pseudo code in there really helps. But I was trying to find some other sources of introducing the algorithm without really going into the maths involved. For last two days I have been sitting with a senior of mine and reading the paper with his help. And I am really happy to say that I more or less know the gist of it now..

Now I plan to review Chetna's PRs and go through them. I will be focusing on  https://github.com/sympy/sympy/pull/2380 . Since it includes most of the work done by her and may be I can start from there. Since its a weekend now. Is it possible for you to come on irc.. ?
Recently I have found irc to be unusually silent.. ?
Have people moved on to gitter ?

Cheers

[Aaron Meurer]

IRC has been silent for a while. That's why I'm trying to get people
to move to Gitter. I would much rather you use it. And once they have
a mobile application, I will get pinged on things even when I am not
at my computer.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/c103d0c8-e1df-4e21-887a-fc8f1df90be1%40googlegroups.com.

[Anurag Sharma]

Hi Aaron and everyone
Apart from from tying loose ends from previous year's GSOC, what more need to be implemented ?
After a cursory glance over the code of cds.py and corresponding Ch-8 in Bronstein, I find all the pseudo codes implemented in cds.py.
Aaron can you point me to some larger chunk which is not implemented. All the previous month I was ploughing through Bronstein. Didnt find enough time to go through the code implemented.
I'd be very happy if you could direct me to the portions which are left so that I can think of them and plan on how to implement and discuss my ideas with you.

Cheers
 

[Aaron Meurer]

There's a lot of work, even just from Bronstein's book. All the three
major subcases, exponential, logarithmic, and trigonometric, have
algorithms that need to be implemented. Most of them are blocking on
some core algorithms, which is where a lot of the work from last
summer's project went. Another key algorithm that needs to be
implemented is the one described in the paper "Simplification of real
elementary functions" (also by Bronstein). Without this algorithm, we
cannot hook up the integrator to the algorithms written by Chetna.
There will also be work beyond that on getting the right kinds of
substitutions to integrate sine and cosine. They have to be translated
to tan to be integrated, but typically you want to translate the
answer back. There are also issues with making sure you do the right
kind of transformation that doesn't introduce new singularities.

And even if we implement all of Bronstein's book, there is a lot of
further potential work. Bronstein's book only covers the
transcendental case, but there are also the algebraic and mixed cases.
There are also extensions to make the algorithm work with certain
special functions like the error function (there are papers that
discuss this in the references of Bronstein's book, and I'm sure Raoul
could give you plenty if you are shy on references).

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/58d33625-4b84-4296-b599-57723e15e862%40googlegroups.com.

[Aaron Meurer]

By the way, another good place to start is trying to fix the
"NotImplementedError: Cannot work with non-rational coefficients in
this case." error. There is a note about this in prde.py. It's pretty
bad that risch_integrate(exp(a*x + b*x), x) works but
risch_integrate(exp(a*x)*exp(b*x), x) does not.

Aaron Meurer

[someone]

Hi,

> There's a lot of work, even just from Bronstein's book. All the three
> major subcases, exponential, logarithmic, and trigonometric, have
> algorithms that need to be implemented.

Another nice presentation of the logarithmic case is in the
bachelor thesis of Ruben Debeerst

"Integration in logarithmischen Erweiterungen"

It is in german, but has a lot of examples and
pseudo code for the central parts.

[someone]

Hi,

> And even if we implement all of Bronstein's book, there is a lot of
> further potential work. Bronstein's book only covers the
> transcendental case, but there are also the algebraic and mixed cases.

For the mixed case one maybe should look at:

"Mixed Transcendental and Algebraic Extensions for the Risch-Norman Algorithm""

by Stefan Böttner. However I could not obtain a copy of this work yet.

[Anurag Sharma]

Thanks for the links Roaul and Aaron.
I'll look at them and tell you the progresss report after thursday.
I have an exam in the interim. (Master's course which I foolishly took :P :(  )

Anurag

[Anurag Sharma]

Improved the efficiency of order_at in rde.py.
Kindly review that.
There is also an issue that I have contributed to the branch that Chetna was working on. Now till her branch is not merged my these changes wont get merged. I'm trying to fix loose ends in her PR with her help in the meanwhile. Is there any workaround this ?

Cheers
Anurag

[Anurag Sharma]

Okay as of now. Chetna's branch passes all the tests. I have tried to make some changes where I dont harcode the value of a. But it invariably fails the tests. And all the tests fail at the same point.
As shown in the iamge attached. What I have basically done is to remove the harcoded '-1' and put 'a' in place of that.
I am resisting to push these changes. So I'd be really glad if some one can discuss over this with me here or on irc.
In the meanwhile kindly review the PR.

[Aaron Meurer]

You should just push the changes. Then I can look over the code compared to the pseudocode in Bronstein and see if you did it right.

Aaron Meurer

--

You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/67e0c80d-65c6-4693-9081-a57963886c4b%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Anurag Sharma]

Yeah see the changes here
https://github.com/anurags92/sympy/commit/5933bfc1f80af5a7f3694a09bc044f0364d1dd39
I have commented on the things which need to be reviewed and what can be ignored as of now.

Anurag

[Anurag Sharma]

Hi Aaron and everyone
Now that a mandatory patch for the application is in, I can discuss in details regarding the application which I wish to propose.
This is gonna be a series of short posts where I can discuss individual elements which I can/should include or what may not be necessary.
These are the first set of changes I wish to implement:

1. I have started on Chetna's branch and have dealt with the issue of not hardcoding 'a'
Reference : https://github.com/sympy/sympy/pull/2380
What I have seen by going through the code that at some places she has diverged from keeping the variables same as in the book. I have taken the liberty to change the variable names and
keep the implementation as close to the book as possible. Is it okay to do that ? Since the code is not merged I guess it wont hurt to change names and do the modifications.
Also she was passing 'a' in all the functions but using the default value '-1' inside. When I replace that with 'a' I find that a doesn't always carry '-1' value. Rather in a recursive call its values changes to '+1' at some instances because she is using the same variable inside the loop too.

2. In rde.py and prde.py I want to merge special_denom in one file, as they are very similar.

3. To recognize whether a rational function is derivative of a rational function we right now use Laurent Series method and then hermite reduction if the first one fails.
I think we can/should also Marik's Criteria as Chetna had suggested and as this mathstackexchange answer tells us : http://math.stackexchange.com/questions/418482/primitive-of-a-rational-function
This will save us from using "costly" hermite reduction in more cases. And implementation shouldn't be tough as we already have subroutines required for the algorithm.
What does the community say about it ?

Cheers
Anurag

P.S Aaron I deleted the merge_cds branch after the changes were merged yesterday from my github repo. I still have that branch on my system because that is the only branch which has cds.py and rde.py etc in the latest version (chetna's version) In case I want you to show my hack for [1] Should i send a new PR from this branch. This PR wont get merged before the deadline but will serve as a mark on my progress on chetna's work.

On Wednesday, January 22, 2014 8:00:08 PM UTC+5:30, Anurag Sharma wrote:

Hello everyone.

This post is regarding the gsoc idea of implementing (or continuing ) the work of Aaron Meurer and Chetna Gupta on implementation of Risch Algorithm for symbolic integrations. I have gone through the PR mentioned on the ideas page. It seems there has been good progress last summer.
I have fairly decent background in abstract algebra and universal algebra. Though I haven't formally done anything related to Differential Algebra.

I wished to know the following things:

1. There are 3 remaining tasks mentioned in the PR. Would it be okay to start on one of them ? (Most probably the one which asks to not hard code the value of 'a' )

2. Has there been any progress other than that mentioned in that PR?

3. I have skimmed through the first chapter of Bronstein's book. Algebraic Preliminaries. Nothing new there. But the second chapter introduces algorithms which I have never implemented and some of them I had not even heard of. I would be really glad if you could tell me what sort of mathematical background is required to contribute efficiently to this part of the project.

I would be really glad if you could link me to some literature on net which explains the Risch algorithm and implementation issues. In the meanwhile I'll try to procure the mentioned text from my college library.

Apart from Aaron Meurer and Chetna Gupta who else has worked on this part ? It would be really nice if I knew more people familiar to this part of sympy so that I wont have to bug Aaron with every little issue :).. I have tried contacting Chetna but I guess she is not much active now.

Cheers
Anurag
 

[Anurag Sharma]

Hi
This is regarding a TODO mentioned in risch.py in recognize_log_derivative
https://github.com/sympy/sympy/blob/master/sympy/integrals/risch.py

The hack that I thought :
a = real_roots()
b = all_roots()
if a!=b return false.

but when import all_roots
it says cant be imported

Following is the error message:

    from sympy.integrals.risch import (gcdex_diophantine, frac_in, as_poly_1t,
  File "sympy/integrals/risch.py", line 29, in <module>
    from sympy.polys.polytools import all_roots
ImportError: cannot import name all_roots

[Aaron Meurer]

On Tue, Mar 11, 2014 at 4:01 PM, Anurag Sharma <anur...@gmail.com> wrote:
> Hi Aaron and everyone
> Now that a mandatory patch for the application is in, I can discuss in
> details regarding the application which I wish to propose.
> This is gonna be a series of short posts where I can discuss individual
> elements which I can/should include or what may not be necessary.
> These are the first set of changes I wish to implement:
>
> 1. I have started on Chetna's branch and have dealt with the issue of not
> hardcoding 'a'
> Reference : https://github.com/sympy/sympy/pull/2380
> What I have seen by going through the code that at some places she has
> diverged from keeping the variables same as in the book. I have taken the
> liberty to change the variable names and
> keep the implementation as close to the book as possible. Is it okay to do
> that ? Since the code is not merged I guess it wont hurt to change names and
> do the modifications.

Yes, please do that.

> Also she was passing 'a' in all the functions but using the default value
> '-1' inside. When I replace that with 'a' I find that a doesn't always carry
> '-1' value. Rather in a recursive call its values changes to '+1' at some
> instances because she is using the same variable inside the loop too.
>
> 2. In rde.py and prde.py I want to merge special_denom in one file, as they
> are very similar.

If you can keep the code readable, OK.

>
> 3. To recognize whether a rational function is derivative of a rational
> function we right now use Laurent Series method and then hermite reduction
> if the first one fails.
> I think we can/should also Marik's Criteria as Chetna had suggested and as
> this mathstackexchange answer tells us :
> http://math.stackexchange.com/questions/418482/primitive-of-a-rational-function
> This will save us from using "costly" hermite reduction in more cases. And
> implementation shouldn't be tough as we already have subroutines required
> for the algorithm.
> What does the community say about it ?

Sounds good.

>
> Cheers
> Anurag
>
> P.S Aaron I deleted the merge_cds branch after the changes were merged
> yesterday from my github repo. I still have that branch on my system because
> that is the only branch which has cds.py and rde.py etc in the latest
> version (chetna's version) In case I want you to show my hack for [1] Should
> i send a new PR from this branch. This PR wont get merged before the
> deadline but will serve as a mark on my progress on chetna's work.

Yes.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/46cf5047-fe58-40b5-931a-d8360c1ecccc%40googlegroups.com.

[Aaron Meurer]

It would be better to just use the assumptions system to check if they
are not real.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/80782c80-d3f3-4544-876f-b1f24480b7e0%40googlegroups.com.

[Anurag Sharma]

https://github.com/sympy/sympy/pull/7285
Just sent a PR.
Have a look :)
Cheers

[Anurag Sharma]

Hi everyone
I have made a rough sketch of my application in pdf format. I am uploading that here. Kindly comment on how does it look. What could be done better? All comments are welcome.

Cheers
Anurag

[Aaron Meurer]

One suggestion would be to take some specific integral that SymPy
currently cannot solve and show step-by-step how the algorithms would
solve it. This is actually a good idea for any project that aims to
implement some algorithm.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/1c87919a-c17a-4407-98d9-6d90c1385605%40googlegroups.com.

[Anurag Sharma]

Yeah.. even I was thinking of including an example of the sorts.

Other than that do I need to explain the math in greater detail ? Because for that I will have to define hell lot of things in the application and type in lot of stuff ?

You received this message because you are subscribed to a topic in the Google Groups "sympy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sympy/bYHtVOmKEFs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6%2Bo-vWSChMU%3DdQttPRKwbAmbi-z8REq6h%2Bzx%3DRmCVyUmA%40mail.gmail.com.

[Aaron Meurer]

No, I think your detail in the math is fine. If you wrote more then
none of the other mentors would understand what you were talking
about. Basically, you should just aim to prove to me that you do
understand the math (maybe I should quiz you ;-). Working through some
examples shows that you understand how the algorithm works.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/CAOYHqH9ToyG%3DP44K_%2BpSSU88rAiFofYtpHSZo9GB5yTWn2wqiQ%40mail.gmail.com.

[Anurag Sharma]

I'm glad for cheering remarks :)

I'll put in couple of examples and then finalize the whole thing tomorrow.... Its 7:00 am of the morning and I havent slept :P . I was expecting you to come online a bit earlier so was waiting all night.

Anyways thanks for your comments.

Cheers

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6%2BW%3DEsiuaHHpYkMGU6My6on9jvGavR4_LHaZFp7fgDrSQ%40mail.gmail.com.

[Anurag Sharma]

Hi everyone
Submitted my proposal at melange. :)
Have a look at it here
https://drive.google.com/file/d/0B7wy_7tuiax7ZEpVNHdlUkU3d3c/edit?usp=sharing

Thanks for all the help and motivation. Especially Raoul to get me started and Aaron for helping me in math.
Also Ondrej for encouraging words :)
I dont think there would be need for any last moment changes but if you see some, kindly tell.
We can have follow up discussion here because personally I don't find melange visually appealing.

Cheers
Anurag

[Ishan Pandhare]

Good day,

I am Ishan Pandhare, a student of Mathematics and Computing from the Indian Institute of Technology, Varanasi. I saw this project being mentioned on the project idea list, and would like to know about its current status. Being a curious student of both mathematics and Computer science, I would like to take up this project for Gsoc, if available.

Following are my areas of study

Differential equations - studied for 2 semesters

Algebra - including group theory, vector spaces and modules, studied for 3 semesters
Graph Theory - theory and implementation, for one semester

Probability, statistics, and Mathematical modeling - studied for 2 semester

Discrete mathematics - for 1 semester

Numerical techniques (involving topics such as the regula-falsi method, Newton-Rhapson method etc.) - for 1 semster

Mathematical methods (involving various transformation techniques including Laplace, Fourier, Hankel etc.) - for 2 semester

Also, I would be learning complex analysis, number theory and fluid dynamics before summer.

I am also good at python, C, C++, Java and R.

I have also studied various Algorithms for 2 semesters.

On Thursday, January 23, 2014 at 1:31:25 AM UTC+5:30 asme...@gmail.com wrote:

On Wed, Jan 22, 2014 at 8:30 AM, Anurag Sharma <anur...@gmail.com> wrote:
> Hello everyone.
>
> This post is regarding the gsoc idea of implementing (or continuing ) the
> work of Aaron Meurer and Chetna Gupta on implementation of Risch Algorithm
> for symbolic integrations. I have gone through the PR mentioned on the ideas
> page. It seems there has been good progress last summer.
> I have fairly decent background in abstract algebra and universal algebra.
> Though I haven't formally done anything related to Differential Algebra.
>
> I wished to know the following things:
>
> 1. There are 3 remaining tasks mentioned in the PR. Would it be okay to
> start on one of them ? (Most probably the one which asks to not hard code
> the value of 'a' )

Yes, finishing this PR is probably the best place to start. I would
create a new branch based off the PR branch and submit a new PR (we
can close the old one when you do this).

>
> 2. Has there been any progress other than that mentioned in that PR?

No.

>
> 3. I have skimmed through the first chapter of Bronstein's book. Algebraic
> Preliminaries. Nothing new there. But the second chapter introduces
> algorithms which I have never implemented and some of them I had not even
> heard of. I would be really glad if you could tell me what sort of
> mathematical background is required to contribute efficiently to this part
> of the project.

Well really Bronstein's book is self-contained. The unfortunate thing
for you is that half of it is already implemented, so the
prerequisites are really more like "the first half of Bronstein's
book". I think you have a good opportunity to catch up, especially
since you are still early. You should read through chapter 2. This
gives a more algorithmic introduction to abstract algebra than you may
have seen before. Chapter 3 gives a good understanding of the rational
algorithm, but it is not necessary to understand all the algorithms
there, except the Lazard-Rioboo-Trager, which is the one actually
used. This is important because the full algorithm is just an
extension of this algorithm, so understanding the basics of how it
works is important. Chapter 4 is entirely theoretical. You should get
an understanding of differential algebra, but a deep understanding of
chapter 4 is not fully required. Most of it is just there to prove the
theorems, particularly the Liouville theorem. A lot of it is there
only to prove the algebraic case, which is not even described in the
book. It really depends on how you learn, though. If you feel you
learn better by really understanding all the mathematics, then you
should read chapter 4 more carefully.

Chapter 5 is the most important. This you should read and understand
(with the possible exception of the proof of Liouville's theorem,
assuming I remember correctly that it's in this chapter). This is the
"base" algorithm. Most of it is already implemented, in risch.py.

Chapters 6, 7, and 8 are nitty-gritty details of the sub-algorithms.
You really don't need to worry so much about the parts that are
already implemented. It depends on what you plan to do in your project
too, but in many cases you can worry about things when you get to them
too.

Chapter 9 is more heavy on the math than what you really need to know
to implement it.

I recommend starting with chapter 2. Try to find the implementation in
SymPy of the algorithms as you go through them, and play with them
using your own inputs. This will help you learn SymPy and the polys
module as well (the polys module can be a bit confusing so let us know
if you can't figure stuff out with it).

You should also try to follow the Risch code, say for some simple
inputs, alongside the pseudocode in Bronstein. Don't worry too much
about the code in DifferentialExtension to start with.

>
> I would be really glad if you could link me to some literature on net which
> explains the Risch algorithm and implementation issues. In the meanwhile
> I'll try to procure the mentioned text from my college library.

Read Bronstein's "symbolic integration tutorial" (you can find it for
free on his website). This gives a broad outline of the full
algorithm. Note that his book only covers about a third of the full
algorithm (namely, just the pure transcendental part), so don't worry
too much if you can't follow the algebraic part parts.

Beyond that, Bronstein's book really is the best source, so I would
stick to it for the most part. The book is extremely well written, so
you shouldn't have too many issues with it.

>
> Apart from Aaron Meurer and Chetna Gupta who else has worked on this part ?
> It would be really nice if I knew more people familiar to this part of sympy
> so that I wont have to bug Aaron with every little issue :).. I have tried
> contacting Chetna but I guess she is not much active now.

Sorry, it's just us. Raoul might be able to tell you a few things too.
I would most likely be the one to mentor the project if it were
accepted, though. You should just keep your communications on this
list, and I will respond. Or if you want to chat you can use IRC or
gitter (https://gitter.im/sympy/sympy).

Aaron Meurer

>
> Cheers
> Anurag

>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.

> For more options, visit https://groups.google.com/groups/opt_out.