Opened 4 years ago
Closed 4 years ago
#22090 closed enhancement (fixed)
Gosper algorithm and Wilf-Zeilberger certificate
Reported by: | rws | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.0 |
Component: | symbolics | Keywords: | |
Cc: | Merged in: | ||
Authors: | Ralf Stephan | Reviewers: | Frédéric Chapoton |
Report Upstream: | N/A | Work issues: | |
Branch: | 70462e2 (Commits, GitHub, GitLab) | Commit: | 70462e26e4d02bba1bbe8c6264587b564314e417 |
Dependencies: | #22174, #22364 | Stopgaps: |
Description (last modified by )
Pynac-0.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).
Pynac-0.7.5 adds a crucial improvement and a faster implementation.
Change History (38)
comment:1 Changed 4 years ago by
- Branch set to u/rws/gosper_algorithm
comment:2 Changed 4 years ago by
- Commit set to 500332755b4187104f5ed47ec701a14d185d53d9
comment:3 Changed 4 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 4 years ago by
- Description modified (diff)
comment:5 Changed 4 years ago by
- Dependencies changed from #19461, pynac-0.7.3 to #19461, #22136
comment:6 Changed 4 years ago by
I concede that we don't need really need #19461.
comment:7 Changed 4 years ago by
- Commit changed from 500332755b4187104f5ed47ec701a14d185d53d9 to 17c5e409466c4b258e1eb07fc490cf6828dff9ba
comment:8 Changed 4 years ago by
- Dependencies #19461, #22136 deleted
- Description modified (diff)
- Milestone changed from sage-7.5 to sage-7.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^4-14*n^2-24*n-9) * 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 Laplace-expansion" determinant algorithm used. Resultants should be later computed in Pynac via Singular which apparently uses a subresultant algorithm.
comment:9 Changed 4 years ago by
- Commit changed from 17c5e409466c4b258e1eb07fc490cf6828dff9ba to 7394ee1bee57b6a0a525de62bf8a913bda687aac
comment:10 Changed 4 years ago by
How does one "delegate to Maxima"? Does it do these "known bugs" cases?
comment:11 Changed 4 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(a-k) / 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 Wilf-Zeilberger, which WOULD be new functionality.
comment:12 Changed 4 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 4 years ago by
- Dependencies set to pynac-0.7.5
- Description modified (diff)
- Summary changed from Gosper algorithm to Gosper algorithm and Wilf-Zeilberger certificate
comment:14 Changed 4 years ago by
- Dependencies changed from pynac-0.7.5 to #22174, pynac-0.7.5
- Description modified (diff)
comment:15 Changed 4 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 4 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 gosper-sum.py
|
comment:17 Changed 4 years ago by
Is pynac-0.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 4 years ago by
- Commit changed from 32d1ca4399e34b129c4743b895684e0b6441795b to 8b0684ee66c4396d20f027f1f1053fa29192a968
comment:19 Changed 4 years ago by
Pynac-0.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 4 years ago by
Do you mean to say that 0.7.5 isn't even on trac yet?
comment:21 Changed 4 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 4 years ago by
Anyway, current Pynac git passes all doctests in 7 seconds, so I'll prepare a release.
comment:23 Changed 4 years ago by
- Dependencies changed from #22174, pynac-0.7.5 to #22174, #22364
comment:24 Changed 4 years ago by
- Commit changed from 8b0684ee66c4396d20f027f1f1053fa29192a968 to e7eddf7148b0c44f168160bd99990b753f625603
comment:25 Changed 4 years ago by
there is a wrong INPUT:: (should be INPUT: with no indentation on the next lines)
comment:26 Changed 4 years ago by
- Commit changed from e7eddf7148b0c44f168160bd99990b753f625603 to f307a8aebce7d8cd63f2a5a68f56193c85071784
comment:27 Changed 4 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 4 years ago by
- Commit changed from f307a8aebce7d8cd63f2a5a68f56193c85071784 to 405c107a7f7ce909391b47cba8ad5dfd2388979a
comment:29 follow-up: ↓ 31 Changed 4 years ago by
- you should de-indent 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 4 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 4 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 4 years ago by
- Branch changed from u/rws/gosper_algorithm to u/rws/22090
comment:33 Changed 4 years ago by
- Commit changed from 87714b4616551f3d343e6548656399cd8d4cff1a to f089c1345497165b7a31c9e7c5d0942f217dfc80
- Milestone changed from sage-7.6 to sage-8.0
Squashed, rebased, and fixed doctest continuation.
New commits:
f089c13 | 22090: Gosper algorithm and Wilf-Zeilberger certificate
|
comment:34 Changed 4 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 4 years ago by
- Reviewers set to Frédéric Chapoton
comment:36 Changed 4 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 4 years ago by
- Status changed from needs_review to positive_review
Thanks for the review!
comment:38 Changed 4 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