Opened 3 years ago
Last modified 2 years ago
#22090 closed enhancement
Gosper algorithm and WilfZeilberger certificate — at Version 14
Reported by:  rws  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  symbolics  Keywords:  
Cc:  Merged in:  
Authors:  Ralf Stephan  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/rws/gosper_algorithm (Commits)  Commit:  e74a4141763cec2b68ce5a27fdfe2650c88b07d4 
Dependencies:  #22174, pynac0.7.5  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 (14)
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)
Branch pushed to git repo; I updated commit sha1. New commits:
Merge branch 'develop' into t/22090/gosper_algorithm
22090: test file