Complexity of the creative telescoping for bivariate rational functions
| When |
Feb 11, 2009
from 02:00 PM to 03:00 PM |
|---|---|
| Where | RISC Seminar room, Hagenberg |
| Add event to calendar |
vCal
iCal
|
Shaoshi CHEN
Complexity of the creative telescoping for bivariate rational functions
The method of creative telescoping was originally designed by Zeilberger in the recurrence case and later extended to the differential case by Almkvist and Zeilberger. The heart of this method is to search for a pair (L, g) with L in K(x)<D_x> and g in the same function field as f such that L(f)=D_y(g) for an explicit given function f. To the best of our knowledge, the complexity of this method has not been analyzed. In this talk, we restrict to the case where f is a bivariate rational function. Our main aim is twofold: on the one hand, we analyze the possible arithmetic size of a solution (L, g); on the other hand, we analyze the existing algorithms for this task from the complexity viewpoint, and propose a new algorithm which is base on Hermite reduction. We will show that our Hermite reduction approach has less complexity than Almkvist and Zeilberger's algorithm in bivariate rational case.