Fast algorithm for border bases of Artinian Gorenstein algebras

DOI10.1145/3087604.3087632MaRDI QIDQ5119958zbMATH OpenOpenAlexFDO

Authors Bernard Mourrain

Publication date 9 September 2020

Published in Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.01328

zbMATH Keywords

Artinian algebraBerlekamp-Massey-Sakata algorithmborder basisGorenstein algebraHankel matrixlinear recurrence relation

Mathematics Subject Classification ID

Commutative Artinian rings and modules, finite-dimensional algebras (13E10) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Symbolic computation and algebraic computation (68W30)

Abstract: Given a multi-index sequence ${\displaystyle }$sigma${\displaystyle }$, we present a new efficient algorithm to compute generators of the linear recurrence relations between the terms of ${\displaystyle }$sigma${\displaystyle }$. We transform this problem into an algebraic one, by identifying multi-index sequences, multivariate formal power series and linear functionals on the ring of multivariate polynomials. In this setting, the recurrence relations are the elements of the kerne l$I$sigma${\displaystyle }$ of the Hankel operator $H$sigma${\displaystyle }$ associated to ${\displaystyle }$sigma${\displaystyle }$. We describe the correspondence between multi-index sequences with a Hankel operator of finite rank and Artinian Gorenstein Algebras. We show how the algebraic structure of the Artinian Gorenstein algebra $A$sigma${\displaystyle }$ associated to the sequence ${\displaystyle }$sigma${\displaystyle }$ yields the structure of the terms $sigma$$alpha$ for all ${\displaystyle }$alpha${\displaystyle }$in$Nn$. This structure is explicitly given by a border basis of $A$sigma${\displaystyle }$, which is presented as a quotient of the polynomial ring $K[x1,\mathrm{...},xn$] by the kernel $I$sigma${\displaystyle }$ of the Hankel operator $H$sigma${\displaystyle }$. The algorithm provides generators of $I$sigma${\displaystyle }$ constituting a border basis, pairwise orthogonal bases of $A$sigma${\displaystyle }$ and the tables of multiplication by the variables in these bases. It is an extension of Berlekamp-Massey-Sakata (BMS) algorithm, with improved complexity bounds. We present applications of the method to different problems such as the decomposition of functions into weighted sums of exponential functions, sparse interpolation, fast decoding of algebraic codes, computing the vanishing ideal of points, and tensor decomposition. Some benchmarks illustrate the practical behavior of the algorithm.

Recommendations

• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• Polynomial-division-based algorithms for computing linear recurrence relations
• A polynomial-division-based algorithm for computing linear recurrence relations
• Linear algebra for computing Gröbner bases of linear recursive multidimensional sequences
• scientific article; zbMATH DE number 1567893

Cited in

(7)

• Guessing Gröbner bases of structured ideals of relations of sequences
• Symmetry in multivariate ideal interpolation
• Computing real radicals by moment optimization
• Algorithms for linearly recurrent sequences of truncated polynomials
• Generalised power series determined by linear recurrence relations
• Quasi-linear guessing of minimal lexicographic Gröbner bases of ideals of c-relations of random bi-indexed sequences
• Polynomial-division-based algorithms for computing linear recurrence relations

This page was built for publication: Fast algorithm for border bases of Artinian Gorenstein algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119958)