Abramov's algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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[edit]

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[edit]

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]

algorithm rational_solutions is
    input: Linear recurrence equation .
    output: The general rational solution  if there are any solutions, otherwise false.

    
    
    
    Solve  for general polynomial solution 
    if solution  exists then
        return general solution 
    else
        return false
    end if

Example[edit]

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[edit]

  1. ^ Abramov, Sergei A. (1989). "Rational solutions of linear differential and difference equations with polynomial coefficients". USSR Computational Mathematics and Mathematical Physics. 29 (6): 7–12. doi:10.1016/s0041-5553(89)80002-3. ISSN 0041-5553. 
  2. ^ a b Abramov, Sergei A. (1995). "Rational solutions of linear difference and q-difference equations with polynomial coefficients". ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation: 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998. 
  3. ^ Man, Yiu-Kwong; Wright, Francis J. (1994). "Fast polynomial dispersion computation and its application to indefinite summation". ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation: 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387. 
  4. ^ Gerhard, Jürgen (2005). "Modular Algorithms in Symbolic Summation and Symbolic Integration". Lecture Notes in Computer Science. 3218. doi:10.1007/b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743. 
  5. ^ Chen, William Y. C.; Paule, Peter; Saad, Husam L. (2007). "Converging to Gosper's Algorithm". arXiv:0711.3386Freely accessible [math.CA]. 
Wikidata-logo.svg WikiProject Mathematics on Wikidata Wikidata-logo.svg