Opened 3 years ago
Closed 3 years ago
#22090 closed enhancement (fixed)
Gosper algorithm and WilfZeilberger certificate
Reported by:  rws  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  symbolics  Keywords:  
Cc:  Merged in:  
Authors:  Ralf Stephan  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  70462e2 (Commits)  Commit:  70462e26e4d02bba1bbe8c6264587b564314e417 
Dependencies:  #22174, #22364  Stopgaps: 
Description (last modified by )
Pynac0.7.3 introduces Gosper's hypergeometric summation algorithm. The ticket will implement the interface and add an extensive test file. Later tickets may call the function before delegating unsolved sums to Maxima.
Also, the WZ certificate can be computed to prove hypergeometric identities.
The test file has one test marked as known bug. Its resolution depends on handling of expressions with algebraic coefficients (i.e. manipulations of polynomials over algebraic fields).
Pynac0.7.5 adds a crucial improvement and a faster implementation.
Change History (38)
comment:1 Changed 3 years ago by
 Branch set to u/rws/gosper_algorithm
comment:2 Changed 3 years ago by
 Commit set to 500332755b4187104f5ed47ec701a14d185d53d9
comment:3 Changed 3 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:4 Changed 3 years ago by
 Description modified (diff)
comment:5 Changed 3 years ago by
 Dependencies changed from #19461, pynac0.7.3 to #19461, #22136
comment:6 Changed 3 years ago by
I concede that we don't need really need #19461.
comment:7 Changed 3 years ago by
 Commit changed from 500332755b4187104f5ed47ec701a14d185d53d9 to 17c5e409466c4b258e1eb07fc490cf6828dff9ba
comment:8 Changed 3 years ago by
 Dependencies #19461, #22136 deleted
 Description modified (diff)
 Milestone changed from sage7.5 to sage7.6
Still missing is better documentation. As to performance 75% of complicated summations are spent in computation of one symbolic matrix determinant, of which 2/3 is expansions. It is astonishing that the 12x12 matrix determinant from the summation of (((n^414*n^224*n9) * 2^n / n^2 / (n+1)^2 / (n+2)^2 / (n+3)^2))
needs 4,316 first level expansions, even with the supposedly optimized "enhanced Laplaceexpansion" determinant algorithm used. Resultants should be later computed in Pynac via Singular which apparently uses a subresultant algorithm.
comment:9 Changed 3 years ago by
 Commit changed from 17c5e409466c4b258e1eb07fc490cf6828dff9ba to 7394ee1bee57b6a0a525de62bf8a913bda687aac
comment:10 Changed 3 years ago by
How does one "delegate to Maxima"? Does it do these "known bugs" cases?
comment:11 Changed 3 years ago by
Gosper summation is a subset of summation, i.e., it can handle only hypergeometric expressions (or sums of such). If one wants to use it in sum
then if gosper_sum
can't solve it, we would call Maxima's sum. The known bugs using Maxima's sum:
sage: (1 / (n^2 + sqrt(5)*n  1)).sum(n,0,m) 1/3*(m^3*(3*sqrt(5)  7)  3*m^2*(sqrt(5)  1)  2*m*(3*sqrt(5)  2)  6)/(m^3*(sqrt(5)  3)  3*m^2*(sqrt(5)  1)  m*(sqrt(5) + 3)  2) sage: ((n*(n+a+b)*a^n*b^n)/factorial(n+a)/factorial(n+b)).sum(n,1,m) (a^(m + 1)*b^(m + 1)*factorial(a + 1)*factorial(b + 1)  ((a^2 + a)*b^2 + (a^2 + a)*b)*factorial(a + m)*factorial(b + m))/(factorial(a + m)*factorial(a + 1)*factorial(b + m)*factorial(b + 1)) sage: F(n, k) = binomial(n,k) * factorial(n) / factorial(k) / factorial(ak) / f ....: actorial(a+n) sage: (F(n+1, k)  F(n, k)).sum(k,0,m) sum((binomial(n + 1, k)*factorial(a + n)*factorial(n + 1)  binomial(n, k)*factorial(a + n + 1)*factorial(n))/(factorial(a  k)*factorial(k)), k, 0, m)/(factorial(a + n + 1)*factorial(a + n))
The last is clearly not solved. The first two seem correct.
I do not claim to add new functionality with this, just the starting point for speed optimizations and for WilfZeilberger, which WOULD be new functionality.
comment:12 Changed 3 years ago by
 Commit changed from 7394ee1bee57b6a0a525de62bf8a913bda687aac to e74a4141763cec2b68ce5a27fdfe2650c88b07d4
Branch pushed to git repo; I updated commit sha1. New commits:
4f4a8b5  Merge branch 'develop' into t/22090/gosper_algorithm

648e498  22174: Interface expression conversion to gamma() and normalization

29446a0  Merge branch 'u/rws/interface_expression_conversion_to_gamma___and_normalization' of git://trac.sagemath.org/sage into t/22090/gosper_algorithm

5b729ed  Merge branch 'develop' into t/22090/gosper_algorithm

11951c8  22219: pkg version/chksum

91973f1  22219: giac usage is GO

a178a75  22219: doctest fixes

c7eb7ff  Merge branch 'develop' into t/22219/upgrade_to_pynac_0_7_4

5fdc5ff  Merge branch 't/22219/upgrade_to_pynac_0_7_4' into t/22090/gosper_algorithm

e74a414  22090: add gosper_term and WZ_certificate

comment:13 Changed 3 years ago by
 Dependencies set to pynac0.7.5
 Description modified (diff)
 Summary changed from Gosper algorithm to Gosper algorithm and WilfZeilberger certificate
comment:14 Changed 3 years ago by
 Dependencies changed from pynac0.7.5 to #22174, pynac0.7.5
 Description modified (diff)
comment:15 Changed 3 years ago by
 Commit changed from e74a4141763cec2b68ce5a27fdfe2650c88b07d4 to 2ef02d41caf973e74598feb5da656aee6a480242
Branch pushed to git repo; I updated commit sha1. New commits:
2ef02d4  22090: improvements, stress testing

comment:16 Changed 3 years ago by
 Commit changed from 2ef02d41caf973e74598feb5da656aee6a480242 to 32d1ca4399e34b129c4743b895684e0b6441795b
Branch pushed to git repo; I updated commit sha1. New commits:
32d1ca4  22090: more tests in gospersum.py

comment:17 Changed 3 years ago by
Is pynac0.7.5 a dependence? Is there a ticket for it that should be referred to? Otherwise it's not clear how this can be reviewed.
comment:18 Changed 3 years ago by
 Commit changed from 32d1ca4399e34b129c4743b895684e0b6441795b to 8b0684ee66c4396d20f027f1f1053fa29192a968
comment:19 Changed 3 years ago by
Pynac0.7.5 is a dependence to make all doctests work. What you could already review is the Python interface code and the correctness of the doctests.
comment:20 Changed 3 years ago by
Do you mean to say that 0.7.5 isn't even on trac yet?
comment:21 Changed 3 years ago by
I'm still introducing new code and fleshing out bugs in Pynac master. Trying to implement a complex algorithm has been a big benefit for Pynac already.
comment:22 Changed 3 years ago by
Anyway, current Pynac git passes all doctests in 7 seconds, so I'll prepare a release.
comment:23 Changed 3 years ago by
 Dependencies changed from #22174, pynac0.7.5 to #22174, #22364
comment:24 Changed 3 years ago by
 Commit changed from 8b0684ee66c4396d20f027f1f1053fa29192a968 to e7eddf7148b0c44f168160bd99990b753f625603
comment:25 Changed 3 years ago by
there is a wrong INPUT:: (should be INPUT: with no indentation on the next lines)
comment:26 Changed 3 years ago by
 Commit changed from e7eddf7148b0c44f168160bd99990b753f625603 to f307a8aebce7d8cd63f2a5a68f56193c85071784
comment:27 Changed 3 years ago by
doc (still) does not build
+[dochtml] OSError: [calculus ] docstring of sage.symbolic.expression.Expression.gosper_sum:7: WARNING: Bullet list ends without a blank line; unexpected unindent.
comment:28 Changed 3 years ago by
 Commit changed from f307a8aebce7d8cd63f2a5a68f56193c85071784 to 405c107a7f7ce909391b47cba8ad5dfd2388979a
comment:29 followup: ↓ 31 Changed 3 years ago by
 you should deindent the paragraphs after
INPUT:
{n \choose k}
is deprecated latex code, and is going to trigger a patchbot plugin if a patchbot runs on this ticket ; use instead\binom{n}{k}
comment:30 Changed 3 years ago by
 Commit changed from 405c107a7f7ce909391b47cba8ad5dfd2388979a to 87714b4616551f3d343e6548656399cd8d4cff1a
Branch pushed to git repo; I updated commit sha1. New commits:
87714b4  22090: cosmetics

comment:31 in reply to: ↑ 29 Changed 3 years ago by
Replying to chapoton:
{n \choose k}
is deprecated latex code, and is going to trigger a patchbot plugin if a patchbot runs on this ticket ; use instead\binom{n}{k}
Done. Does that plugin also check the output of Sage itself?
sage: latex(binomial(n,k)) {n \choose k}
comment:32 Changed 3 years ago by
 Branch changed from u/rws/gosper_algorithm to u/rws/22090
comment:33 Changed 3 years ago by
 Commit changed from 87714b4616551f3d343e6548656399cd8d4cff1a to f089c1345497165b7a31c9e7c5d0942f217dfc80
 Milestone changed from sage7.6 to sage8.0
Squashed, rebased, and fixed doctest continuation.
New commits:
f089c13  22090: Gosper algorithm and WilfZeilberger certificate

comment:34 Changed 3 years ago by
 there is a .. MATH block start that is missing a blank line just after it
otherwise, looks good to me. You can set a positive review once the minor change above is done.
comment:35 Changed 3 years ago by
 Reviewers set to Frédéric Chapoton
comment:36 Changed 3 years ago by
 Commit changed from f089c1345497165b7a31c9e7c5d0942f217dfc80 to 70462e26e4d02bba1bbe8c6264587b564314e417
Branch pushed to git repo; I updated commit sha1. New commits:
70462e2  22090: cosmetics

comment:37 Changed 3 years ago by
 Status changed from needs_review to positive_review
Thanks for the review!
comment:38 Changed 3 years ago by
 Branch changed from u/rws/22090 to 70462e26e4d02bba1bbe8c6264587b564314e417
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Merge branch 'develop' into t/22090/gosper_algorithm
22090: test file