Abstract
Computing recurrence relations for sequences is a central problemin computer algebra, with applications in error-correcting codes, Gröbner basis computation, and sparse interpolation. While uni-indexed C-recursive sequences benefit from quasi-linear algorithms leveraging the half-gcd method, the extension to multi-indexed sequences remains computationally challenging. Existing methods for bi-indexed sequences achieve quadratic complexity at best, limiting their practical use.This paper presents a quasi-linear algorithm for computing lexicographic Gröbner bases of the ideal of C-relations associated to bi-indexed sequences. Our approach extends the half-gcd algorithm in $K^N$[$y$] by integrating a pseudo-Euclidean division. This approach shows how to leverage the bi-Hankel structure of the matrix, significantly improving the efficiency of computing minimalC-relations closing the complexity gap between the uni- and bi-indexed cases. Our algorithm is restricted to bi-indexed sequences whose associated bi-Hankel matrix has generic row rank profile.