I&C Journal 2002 Journal Article
Finding Recursions for Multidimensional Arrays
- Oliver Pretzel
We produce a concise description of Sakata's algorithm for finding recursion relations that are valid for an n-dimensional array. The (new) analysis extends to limit points which are excluded by previous authors. We show that under a natural hypothesis the algorithm becomes stationary below each limit point and, in particular, constructs a full set of recursion relations for a recursive array at some finite point. The method used to justify the algorithm stresses the duality between the fundamental extension operation of Sakata and the S-polynomial operation of Buchberger.