Opened 14 years ago

Closed 13 years ago

Last modified 13 years ago

#3587 closed enhancement (fixed)

calculus -- wrap maxima's symbolic summation

Reported by: was Owned by: whuss
Priority: major Milestone: sage-4.3
Component: calculus Keywords:
Cc: burcin, jason Merged in: sage-4.3.alpha1
Authors: Wilfried Huss Reviewers: Burcin Erocal, Mike Hansen, Karl-Dieter Crisman, William Stein
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by kcrisman)

Maxima has good symbolic summation and it would be easy to wrap in the calculus package. We are constantly getting stuff like this:

02:53 < nagyv> hello! how can I represent a summation in sage? like sum_{x=1}^N x, I would like to take the limit as N goes to infinity
03:02 < nagyv> what the heck is this? maxima.sum(1/x, x, 1, 2*N) gives 2*N/x! why?

Probably the only reason that this hasn't been done yet is the calculus rewrite by gfurnish. That is *not* a good enough reason, and don't worry, the work won't be lost.

Attachments (6)

summation.patch (16.6 KB) - added by whuss 13 years ago.
sum.patch (13.6 KB) - added by mhansen 13 years ago.
trac_3587-maxima_simplify_sum.patch (16.1 KB) - added by burcin 13 years ago.
trac_3587-fix_doctests.patch (689 bytes) - added by whuss 13 years ago.
fixes the doctest errors reported by William
trac_3587-binomial_workaround.patch (1.9 KB) - added by whuss 13 years ago.
removes the workaround for binomials. Depends on #6197
trac_3587-maxima_simplify_sum-with-maxima-5-19-1.patch (16.7 KB) - added by kcrisman 13 years ago.
Based on 4.2.1, apply only this patch

Download all attachments as: .zip

Change History (34)

comment:1 Changed 14 years ago by gfurnish

I would like to add a +1 to this proposal as I'm not planning on implementing symbolic summation anytime in the near (or far) future, so I would be really happy if someone would work on this.

comment:2 Changed 14 years ago by burcin

  • Cc burcin added

comment:3 Changed 14 years ago by mhansen

"sum" is probably the most appropriate name for this, but we'd have to make sure that it behaves the same way as Python's sum.

comment:4 Changed 13 years ago by whuss

  • Owner changed from gfurnish to whuss
  • Status changed from new to assigned
  • Summary changed from calculus -- implement symbolic summation to [with patch, needs review] calculus -- implement symbolic summation

The attached patch adds a summation command which wraps simplify_sum from maxima.

comment:5 follow-ups: Changed 13 years ago by burcin

  • Summary changed from [with patch, needs review] calculus -- implement symbolic summation to [with patch, needs work] calculus -- wrap maxima's symbolic summation

Many thanks for the patch, this was long overdue. A few comments after reading your patch:

Your patch replicates the way integrate/integral works perfectly. Though, as Mike wrote in comment:3, we should just call this sum. There is also a discussion about naming here:

http://groups.google.com/group/sage-devel/browse_thread/thread/bd4eb3b613c98030

I suggest putting a sum() function in sage.misc.misc_c, that calls python's sum() or your function based on the type/number of the arguments. Would you like to do this or should I?

Here are some suggested changes:

  • rename all instances of the method to sum or symbolic_sum
  • you should import your function before the doctests in calculus.py to make sure you call the right function
  • it would be good to add a comment to #6197 pointing to the comment you have in calculus.py
  • you could add your code for converting MMA output back to Sage to a _sage_() method in sage.interfaces.mathematica.MathematicaElement, see the MagmaElement class in sage.interfaces.magma for an example, similarly for Maple output
  • In the last lines of the docstring for sage.symbolic.expression.Expression.summation, choosen -> chosen

In the long term, I would like to see integral and sum constructs as subclasses of sage.symbolic.function.SFunction, instead of the current thin wrappers around maxima functionality. I will take a look at the feasibility of doing this over the weekend. I don't want to hold your patch back for this though.

comment:6 in reply to: ↑ 5 Changed 13 years ago by whuss

Replying to burcin:

Many thanks for the patch, this was long overdue. A few comments after reading your patch:

Your patch replicates the way integrate/integral works perfectly. Though, as Mike wrote in comment:3, we should just call this sum. There is also a discussion about naming here:

http://groups.google.com/group/sage-devel/browse_thread/thread/bd4eb3b613c98030

I suggest putting a sum() function in sage.misc.misc_c, that calls python's sum() or your function based on the type/number of the arguments. Would you like to do this or should I?

It would be great if you could do this.

Here are some suggested changes:

  • rename all instances of the method to sum or symbolic_sum
  • you should import your function before the doctests in calculus.py to make sure you call the right function
  • it would be good to add a comment to #6197 pointing to the comment you have in calculus.py
  • you could add your code for converting MMA output back to Sage to a _sage_() method in sage.interfaces.mathematica.MathematicaElement, see the MagmaElement class in sage.interfaces.magma for an example, similarly for Maple output
  • In the last lines of the docstring for sage.symbolic.expression.Expression.summation, choosen -> chosen

I will take care of these.

In the long term, I would like to see integral and sum constructs as subclasses of sage.symbolic.function.SFunction, instead of the current thin wrappers around maxima functionality.

This is definitely necessary. Currently there is no way to interact with an unevaluated integral or sum.

I will take a look at the feasibility of doing this over the weekend. I don't want to hold your patch back for this though.

Changed 13 years ago by whuss

comment:7 in reply to: ↑ 5 Changed 13 years ago by whuss

  • Summary changed from [with patch, needs work] calculus -- wrap maxima's symbolic summation to [with patch, needs review] calculus -- wrap maxima's symbolic summation

Replying to burcin:

Here are some suggested changes:

  • rename all instances of the method to sum or symbolic_sum
  • you should import your function before the doctests in calculus.py to make sure you call the right function
  • it would be good to add a comment to #6197 pointing to the comment you have in calculus.py
  • you could add your code for converting MMA output back to Sage to a _sage_() method in sage.interfaces.mathematica.MathematicaElement, see the MagmaElement class in sage.interfaces.magma for an example, similarly for Maple output
  • In the last lines of the docstring for sage.symbolic.expression.Expression.summation, choosen -> chosen

I posted a new patch that takes care of these issues.

The second patch (sum.patch) renames summation to sum. This currently overwrites the python sum command.

Changed 13 years ago by mhansen

comment:8 Changed 13 years ago by mhansen

  • Authors set to Wilfried Huss
  • Reviewers set to Burcin Erocal, Mike Hansen

I updated sum.patch so that it's compatible with builtin.sum.

Burcin, can you look at this?

comment:9 follow-up: Changed 13 years ago by burcin

  • Summary changed from [with patch, needs review] calculus -- wrap maxima's symbolic summation to [with patch, needs work] calculus -- wrap maxima's symbolic summation

I uploaded a new patch in attachment:trac_3587-maxima_simplify_sum.patch. This has both patches folded together, and renames sum() to symbolic_sum() in sage/calculus/calculus.py and sage/misc/functional.py eliminating the risk of people using the symbolic sum instead of sum in library code without realizing, and the need to import __builtin__.

I am OK with the patch, and ready to give it a positive review. However, there is a problem, maxima returns wrong results in certain cases:

sage: sum(binomial(n,k), k, 1, n)
2^n - 2
sage: sum(binomial(n,k), k, 2, n)
2^n - 2*n - 2
sage: r=sum(binomial(n,k), k, 2, n-2)
sage: r.simplify()
2^n - 1/6*n^3 - 11/6*n - 2

It seems that maxima doesn't handle definite sums with "non natural" bounds. I.e., in the examples above the bounds don't span the whole support of the expression, so one needs further processing to get the final result after calling Zeilberger's algorithm.

Indefinite sums seem to be fine. In this case, we could check the inputs, and raise a warning if we have a definite sum. I'll try to do this, but don't count on me since I already signed up for a lot this week.

Changed 13 years ago by burcin

comment:10 in reply to: ↑ 9 ; follow-up: Changed 13 years ago by kcrisman

I installed this, but it does not seem to work as advertised. Namely,

sage: var('n,k')
(k, n)
sage: sum(binomial(n,k),k,0,n)
simplify_sum(sum(binomial(n,k),k,0,n))

It does behave as desired if I go to Maxima and load(simplify_sum) etc., but that's not the same. Somehow it's staying symbolic for some reason. This is off of 4.1.1 on Mac OSX.5.

I am OK with the patch, and ready to give it a positive review. However, there is a problem, maxima returns wrong results in certain cases:

sage: sum(binomial(n,k), k, 1, n)
2^n - 2
sage: sum(binomial(n,k), k, 2, n)
2^n - 2*n - 2
sage: r=sum(binomial(n,k), k, 2, n-2)
sage: r.simplify()
2^n - 1/6*n^3 - 11/6*n - 2

It seems that maxima doesn't handle definite sums with "non natural" bounds. I.e., in the examples above the bounds don't span the whole support of the expression, so one needs further processing to get the final result after calling Zeilberger's algorithm.

Looks like this problem is fixed in Maxima 5.19 (at least they work properly in 5.19.1), so this is another good reason to get that in Sage soon (there was an experimental spkg posted at http://sage.math.washington.edu/home/kirkby/Solaris-fixes/maxima-5.19.0/maxima-5.19.0.spkg at one point). Incidentally, apparently it never got to as heavy a hitter as Zeilberger, but I'm not sure where the problem was.

comment:11 in reply to: ↑ 10 Changed 13 years ago by whuss

Replying to kcrisman:

I installed this, but it does not seem to work as advertised. Namely,

sage: var('n,k')
(k, n)
sage: sum(binomial(n,k),k,0,n)
simplify_sum(sum(binomial(n,k),k,0,n))

It does behave as desired if I go to Maxima and load(simplify_sum) etc., but that's not the same. Somehow it's staying symbolic for some reason. This is off of 4.1.1 on Mac OSX.5.

It works for me on sage-4.1.1 on Linux. I don't have a Mac to check.

comment:12 Changed 13 years ago by kcrisman

The fix for my problem is to change

maxima = Maxima(init_code = ['display2d:false; domain: complex; keepfloat: true; load(topoly_solver); load(simplify_sum)'],
                script_subdirectory=None)

by

maxima = Maxima(init_code = ['display2d:false', 'domain: complex', 'keepfloat: true', 'load(topoly_solver)', 'load(simplify_sum)'],
                script_subdirectory=None)

the need for which perhaps does depend on the operating system. Can someone check that this doesn't break Linux?

comment:13 Changed 13 years ago by kcrisman

The latest .spkg in #6699 (and hence in 4.1.2.alpha0) should fix the problems Burcin mentions, and seems to handle all the sums properly.

sage: sum(binomial(n,k), k, 1, n)
2^n - 2
sage: sum(binomial(n,k), k, 2, n)
2^n - 2*n - 2

are now

sage: var('k,n')
(k, n)
sage: sum(binomial(n,k),k,0,n)
2^n
sage: sum(binomial(n,k),k,1,n)
2^n - 1
sage: sum(binomial(n,k),k,2,n)
2^n - n - 1

So perhaps a new patch based on 4.1.2.alpha0 is in order, but then the review should be quite straightforward, with the fix above.

comment:14 Changed 13 years ago by kcrisman

  • Reviewers changed from Burcin Erocal, Mike Hansen to Burcin Erocal, Mike Hansen, Karl-Dieter Crisman
  • Summary changed from [with patch, needs work] calculus -- wrap maxima's symbolic summation to [with patch, needs review] calculus -- wrap maxima's symbolic summation

This should fix all the outstanding issues. It is built off of 4.1.1, with #6564 and (then) #6699 applied, then this patch. Several additional doctests/fixes to them are included beyond the previous patch, in addition to the Maxima init fix. Should definitely be tested on Linux to make sure the fix for OSX didn't break Linux!

comment:15 Changed 13 years ago by jason

I browsed through the patch---is it still easy to access the (fast) native python sum command, or will we have to import that into the namespace? In other words, was the suggestion given above about calling the python sum vs. this new sum depending on the arguments implemented? If not, I see a serious, far-reaching problem with backwards compatibility...

comment:16 Changed 13 years ago by kcrisman

Well, the following was identical with and without the patch:

sage: l = range(10^6)
sage: time sum(l)
CPU times: user 0.15 s, sys: 0.00 s, total: 0.15 s
Wall time: 0.15 s
499999500000L

And the same with summing m = 5*l, both 0.79 s, and summing n = 100*m, both about 80 s. And sum(l,3) returns the correct answer (without the L). Also, earlier mhansen seems to indicate that it's still okay - I don't know exactly where in the code that happens, though. Hope this helps.

comment:17 Changed 13 years ago by was

Fix this one broken doctest and this gets a positive review from me:

wstein@sage:~/build/sage-4.1.2.alpha1$ ./sage -t devel/sage/sage/misc/functional.py 
sage -t  "devel/sage/sage/misc/functional.py"               
**********************************************************************
File "/scratch/wstein/build/sage-4.1.2.alpha1/devel/sage/sage/misc/functional.py", line 442:
    sage: sum(k * binomial(n, k), k, 1, n)
Expected:
    1/2*2^n*n
Got:
    n*2^(n - 1)
**********************************************************************
File "/scratch/wstein/build/sage-4.1.2.alpha1/devel/sage/sage/misc/functional.py", line 480:
    sage: sum(a*q^k, k, 0, oo)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Sum is divergent.
Got:
    -a/(q - 1)
**********************************************************************
1 items had failures:
   2 of  20 in __main__.example_25
***Test Failed*** 2 failures.
For whitespace errors, see the file /scratch/wstein/build/sage-4.1.2.alpha1/tmp/.doctest_functional.py
         [8.3 s]
exit code: 1024
 
----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage/sage/misc/functional.py"
Total time for all tests: 8.3 seconds
wstein@sage:~/build/sage-4.1.2.alpha1$ 

The above is just the result of changes in Maxima going from 5.16 to 5.19 in sage-4.1.2.

-- William

comment:18 Changed 13 years ago by mpatel

This is nice!

Just a small note: Sphinx warns about the indentation of the new note:: block in expression.pyx:

/home/apps/sage/devel/sage/doc/en/reference/sage/symbolic/expression.rst:: (ERROR/3) Content block expected for the "note" directive; none found.

Changed 13 years ago by whuss

fixes the doctest errors reported by William

comment:19 Changed 13 years ago by kcrisman

  • Reviewers changed from Burcin Erocal, Mike Hansen, Karl-Dieter Crisman to Burcin Erocal, Mike Hansen, Karl-Dieter Crisman, William Stein

Okay, I fixed those tests; there were identical ones elsewhere I did fix but functional.py escaped me. I also think I fixed the note issue.

Since #6197 is merged I also used the correct algorithm=maxima behavior. I don't have Maple so I didn't feel comfortable changing the Maple behavior, but it would be easy to open a new ticket for that if the appropriate algorithm worked, which it certainly seems like it should post-#6197.

I'm going to assume that the builtin sum is indeed okay - great!

comment:20 Changed 13 years ago by kcrisman

Use only the 5-19-1 patch.

Changed 13 years ago by whuss

removes the workaround for binomials. Depends on #6197

comment:21 Changed 13 years ago by whuss

Looks like I have been a little too late.

I have checked that algorithm=maple also works without the workaround for #6197. I think it is save to remove it.

comment:22 Changed 13 years ago by kcrisman

  • Description modified (diff)

Great, I'll do that as well.

comment:23 Changed 13 years ago by was

  • Summary changed from [with patch, needs review] calculus -- wrap maxima's symbolic summation to [with patch, needs work] calculus -- wrap maxima's symbolic summation

I get *tons* of doctest failures when I apply this patch, say to sage-4.1.2.alpha1:

The following tests failed:

        sage -t  devel/sage/sage/misc/functional.py # 5 doctests failed
        sage -t  devel/sage/sage/calculus/calculus.py # 10 doctests failed
        sage -t  devel/sage/sage/symbolic/expression.pyx # 9 doctests failed

See http://sage.math.washington.edu/home/wstein/build/sage-4.1.2.alpha1/test_3587.out

comment:24 Changed 13 years ago by kcrisman

Did you do #6197?

comment:25 Changed 13 years ago by kcrisman

  • Cc jason added
  • Summary changed from [with patch, needs work] calculus -- wrap maxima's symbolic summation to [with patch, needs review] calculus -- wrap maxima's symbolic summation

This patch in fact applies cleanly to 4.1.2.alpha2, and none of the files above have doctest failures with it. Please review.

Changed 13 years ago by kcrisman

Based on 4.2.1, apply only this patch

comment:26 Changed 13 years ago by kcrisman

Please someone (beyond myself and the author) review this! It would be perfect for the big 4.3 release coming up!

comment:27 Changed 13 years ago by mhansen

  • Merged in set to sage-4.3.alpha1
  • Report Upstream set to N/A
  • Resolution set to fixed
  • Status changed from needs_review to closed

comment:28 Changed 13 years ago by mhansen

  • Summary changed from [with patch, needs review] calculus -- wrap maxima's symbolic summation to calculus -- wrap maxima's symbolic summation

Positive review from me (by the way).

Note: See TracTickets for help on using tickets.