2024/10/22 by Hamid Rahkooy, Rahkooy, Hamid
Computer Science · #Cellular Automata and Applications #Commutative Algebra (math.AC) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.2410.17208
openalex publication_date 2024/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we present a new algorithm for computing the linear recurrence relations of multi-dimensional sequences. Existing algorithms for computing these relations arise in computational algebra and include constructing structured matrices and computing their kernels. The challenging problem is to reduce the size of the corresponding matrices. In this paper, we show how to convert the problem of computing recurrence relations of multi-dimensional sequences into computing the orthogonal of certain ideals as subvector spaces of the dual module of polynomials. We propose an algorithm using efficient dual module computation algorithms. We present a complexity bound for this algorithm, carry on experiments using Maple implementation, and discuss the cases when using this algorithm is much faster than the existing approaches.