“Abramov's algorithm”的意思、由来-开放百科全书

In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989.^[1]^[2]

Universal denominator

The main concept in Abramov's algorithm is a universal denominator. Let

be a field of characteristic zero. The dispersion

of two polynomials

is defined as

where

denotes the set of non-negative integers. Therefore the dispersion is the maximum

such that the polynomial

and the

-times shifted polynomial

have a common factor. It is

if such a

does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant

.^[3]^[4] Let

be a recurrence equation of order

with polynomial coefficients

, polynomial right-hand side

and rational sequence solution

. It is possible to write

for two relatively prime polynomials

. Let

and

where

denotes the falling factorial of a function. Then

divides

. So the polynomial

can be used as a denominator for all rational solutions

and hence it is called a universal denominator.^[5]

Algorithm

Let again

be a recurrence equation with polynomial coefficients and

a universal denominator. After substituting

for an unknown polynomial

and setting

the recurrence equation is equivalent to

As the

cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution

. There are algorithms to find polynomial solutions. The solutions for

can then be used again to compute the rational solutions

. ^[2]

Example

The homogeneous recurrence equation of order

over

has a rational solution. It can be computed by considering the dispersion

This yields the following universal denominator:

and

Multiplying the original recurrence equation with

and substituting

leads to

This equation has the polynomial solution

for an arbitrary constant

. Using

the general rational solution is

for arbitrary

References

1. ^{{Cite journal|last=Abramov|first=Sergei A.|date=1989|title=Rational solutions of linear differential and difference equations with polynomial coefficients|journal=USSR Computational Mathematics and Mathematical Physics|volume=29|issue=6|pages=7–12|doi=10.1016/s0041-5553(89)80002-3|issn=0041-5553|via=}}
2. ^¹{{Cite book|last=Abramov|first=Sergei A.|date=1995|title=Rational solutions of linear difference and q-difference equations with polynomial coefficients|url=http://dl.acm.org/citation.cfm?id=220346.220383|journal=ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation|volume=|pages=285–289|doi=10.1145/220346.220383|isbn=978-0897916998|via=}}
3. ^{{Cite book|last=Man|first=Yiu-Kwong|last2=Wright|first2=Francis J.|date=1994|title=Fast polynomial dispersion computation and its application to indefinite summation|url=http://dl.acm.org/citation.cfm?id=190347.190413|journal=ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation|volume=|pages=175–180|doi=10.1145/190347.190413|isbn=978-0897916387|via=}}
4. ^{{Cite book|last=Gerhard|first=Jürgen|date=2005|title=Modular Algorithms in Symbolic Summation and Symbolic Integration|journal=Lecture Notes in Computer Science|volume=3218|language=en-gb|doi=10.1007/b104035|issn=0302-9743|isbn=978-3-540-24061-7}}
5. ^{{cite arxiv|last=Chen|first=William Y. C.|last2=Paule|first2=Peter|last3=Saad|first3=Husam L.|date=2007|title=Converging to Gosper's Algorithm|eprint=0711.3386|class=math.CA}}