Content deleted Content added
m Task 18 (cosmetic): eval 5 templates: del empty params (5×); |
Citation bot (talk | contribs) Add: doi-access, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 625/924 |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
'''Petkovšek's algorithm''' (also '''Hyper''') is a [[computer algebra]] algorithm that computes a basis of [[Hypergeometric identity|hypergeometric terms]] solution of its input [[P-recursive equation|linear recurrence equation with polynomial coefficients]]. Equivalently, it computes a first order right factor of linear [[difference operator]]s with polynomial coefficients. This algorithm was developed by [[Marko Petkovšek]] in his PhD-thesis 1992.<ref name=":0">{{Cite journal|last=Petkovšek|first=Marko|date=1992|title=Hypergeometric solutions of linear recurrences with polynomial coefficients|journal=Journal of Symbolic Computation|volume=14|issue=2–3|pages=243–264|doi=10.1016/0747-7171(92)90038-6|issn=0747-7171|doi-access=free}}</ref> The algorithm is implemented in all the major computer algebra systems.
== Gosper-Petkovšek representation ==
Line 12:
#<math display="inline">\gcd ( b(n), c(n+1))=1</math>.
This representation of <math display="inline">r(n)</math> is called Gosper-Petkovšek normal form. These polynomials can be computed explicitly. This construction of the representation is an essential part of [[Gosper's algorithm]].<ref>{{Cite journal |last=Gosper |first=R. William |date=1978 |title=Decision procedure for indefinite hypergeometric summation
== Algorithm ==
Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence <math display="inline">c(n)</math>. The other polynomials <math display="inline">a(n),b(n)</math> can be taken as the monic factors of the first coefficient polynomial <math display="inline">p_0 (n)</math> resp. the last coefficient polynomial shifted <math display="inline">p_r(n-r+1)</math>. Then <math display="inline">z</math> has to fulfill a certain [[algebraic equation]]. Taking all the possible finitely many triples <math display="inline">(a(n), b(n), z)</math> and computing the corresponding [[Polynomial solutions of P-recursive equations|polynomial solution]] of the transformed recurrence equation <math display="inline">c(n)</math> gives a hypergeometric solution if one exists.<ref name=":0" /><ref name=":1">{{Cite book|url=https://www.math.upenn.edu/~wilf/Downld.html|title=A=B|
In the following pseudocode the degree of a polynomial <math display="inline">p(n) \in \mathbb{K}[n]</math> is denoted by <math display="inline">\deg (p (n))</math> and the coefficient of <math display="inline">n^d</math> is denoted by <math display="inline">\text{coeff} ( p(n), n^d )</math>.
| |||