On Mon, Mar 19, 2012 at 9:15 AM, Jorge Cardona <[email protected]> wrote: > Hi, > > Aaron, I was following your code for the risch algorithm, as you have > previously comment is basically chapters 6 in rde.py, 7 in prde.py and > 5 in risch.py, and some algorithm sparse in the book also in risch.py. > > There are a lot of "TODO" in the code, some nonimplemented exceptions, > and this comment on risch_integrate: > > Only transcendental functions are supported. Currently, only exponentials > and logarithms are supported, but support for trigonometric functions is > forthcoming. > > That means that right now you can only built the differential > extension of the integrand for logarithms and exponential functions? I > didn't found actually a formal way to built this on Bronstein's book, > I imagine it must be then a well know problem. since is just the > starting point for Risch Algorithm according to the section 5.2. Also > I can't connect in my head right now the relation of that problem with > the structure theorems in chapter 9.
Yes, that's what it means. Bronstein's book describes this, but this is one of the few algorithms he does not give pseudocode for. Rather, the algorithm is partly what is explained in the first part of section 5.2 and partly the results of the structure theorems from chapter 9. Basically, you recursively take the exponential and logarithmic parts of an expression, and that is your extension. So if you have log(exp(x) + 1)*log(x), your extension would be QQ(x, log(x), exp(x), log(exp(x) + 1)) (the log(x) could actually go anywhere in the extension, the only important thing is that exp(x) is added before log(exp(x) + 1)). The reason why you have to have the structure theorems is that each extension must be transcendental over the others. For example, if you have log(x)*log(2*x), you cannot use QQ(x, log(x), log(2*x)), because log(2*x) is not transcendental over C(log(x)) (because log(2*x) == log(2) + log(x)). Here, C = const(QQ(x, log(x)) (i.e., we don't care that log(2) is transcendental over QQ; extending the constant field is not an issue). As another example, you cannot integrate exp(log(x)/2) with the algorithm, because this function is really x**(1/2), which is algebraic. The structure theorems will discover this for you, because when you try to add exp(log(x)/2) to QQ(x, log(x)), it will find the relation exp(log(x)/2)**2 = x, proving that exp(log(x)/2) is algebraic over QQ(log(x)). > > I will like to know then if a possible project on the Risch algorithm > would be planned on solve those "TODO" comments, and polish the code > to an easy merge with master? Well, you could look at it that way. If I remember correctly, I basically have TODOs for everything that needs to be done, including stuff like "TODO: implement support for trig extensions". > > Sadly I found hard to follow some aspects in the code, but the > comments help a lot, I will try to find some possible patch of your > code. The code will be very hard to follow unless you follow along in Bronstein's book. I think with the exception of the algorithm you described above (currently implemented in DifferentialExtension.__init__), and the loop in risch_integrate(), all the algorithms come straight from pseudocode in Bronstein's book (those are exceptions simply because Bronstein didn't include explicit pseudocode for them in his book, but rather just plain English descriptions). I won't lie to you: the easy parts of this algorithm have for the most part already been implemented. The majority of what remains comes from implementing the algorithms that are only described in plain English in his book. My best advice to you is to read through Bronstein's book, in order, and when you come across pseudocode, look it up in my branch to see how it is implemented. The pseudocodes from chapter 1 are all essential to the polys, and is implemented there (your best bet to find them is to grep the repository). Chapter 2 describes the rational integration algorithm, which is entirely implemented already in sympy/integrals/rationaltools.py. Only about half the pseudocode is implemented there, because the other half are less efficient algorithms given only for instructive purposes. Chapter 3 and chapter 4 are theoretical, and contain almost no pseudocode. These will be necessary if you want to understand the proofs of the later theorems, but if you don't care about that, you can probably get away with just skimming them, and making sure you at least understand the definitions. I've already told you about chapters 5-7. Chapter 8 relates to the algorithm for integrating trig functions, which hasn't been implemented at all yet. Chapter 9 is about the structure theorems. That chapter is very technical. You could probably just get away with just looking at the statement of the theorems at this point. When you come across pseudocode, try to play around with the functions interactively to see how they work. An idea for something you could so, which is not a TODO so much as I remember, would be to write doctests for all the internal functions in the Risch algorithm. Basically, you should try to find a simple yet instructive example, and put it in the docstring as >>> from sympy.integrals.risch import whatever_function >>> whatever_function(example) result This will help you learn how things work, and will also help future people learn how they work as well. Aaron Meurer > > Are there some sympy tools to work with algebraic structures as rings, > fields, extensions, and more? There are some on the polys module but > there is somethign like a Ring class, and Extension? Yes, these are the domains. When you create a Poly, the domain is inferred automatically, but you can also provide one explicitly. For extensions, the support is limited. Only algebraic number extensions are supported (as opposed to algebraic functions), and they can get quite slow as you extend by more than a few numbers. Aaron Meurer > > Bye. > > -- > Jorge Eduardo Cardona > [email protected] > jorgeecardona.blogspot.com > github.com/jorgeecardona > ------------------------------------------------ > Linux registered user #391186 > Registered machine #291871 > ------------------------------------------------ > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
