Résumé
Computing recurrence relations for sequences is a central problem in 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 minimal lexicographic Gröbner bases of the ideal of C-relations associated to bi-indexed sequences. Our approach extends the half-gcd algorithm in \(\mathbb {K}^{\mathbb {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 C-relations and 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.