Opened 3 years ago
Last modified 2 years ago
#22090 closed enhancement
Gosper algorithm — at Version 8
Reported by: | rws | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.0 |
Component: | symbolics | Keywords: | |
Cc: | Merged in: | ||
Authors: | Ralf Stephan | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/rws/gosper_algorithm (Commits) | Commit: | 17c5e409466c4b258e1eb07fc490cf6828dff9ba |
Dependencies: | 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.
The test file has three tests marked as known bug. Each of them shows an area where the implementation will have to be improved:
- expressions with algebraic coefficients (i.e. manipulations of polynomials over algebraic fields)
- the final computation in Gosper's algorithm may result in
NaN
from0*inf
,0/0
or such. Here a limit computation will give the result. I didn't want to call Maxima from Pynac however. - enhancement of GiNaC's resultant implementation
Change History (8)
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, pynac-0.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 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.
Branch pushed to git repo; I updated commit sha1. New commits:
Merge branch 'develop' into t/22090/gosper_algorithm
22090: test file