Fast algorithm for border bases of Artinian Gorenstein algebras

Bernard Mourrain 1
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , UoA - University of Athens
Abstract : Given a multi-index sequence $σ$, we present a new efficient algorithm to compute generators of the linear recurrence relations between the terms of $σ$. 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σ$ of the Hankel operator $Hσ$ associated to $σ$. 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σ$ associated to the sequence $σ$ yields the structure of the terms σα for all $α ∈ N n$. This structure is explicitly given by a border basis of $Aσ$, which is presented as a quotient of the polynomial ring $K[x 1 ,. .. , xn$] by the kernel $Iσ$ of the Hankel operator $Hσ$. The algorithm provides generators of $Iσ$ constituting a border basis, pairwise orthogonal bases of $Aσ$ 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.
Type de document :
Communication dans un congrès
ISSAC'17, Jul 2017, Kaiserslautern, Germany. ACM New York, NY, USA, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation pp.333-340, hal-01515366. 〈10.1145/3087604.3087632〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01515366
Contributeur : Bernard Mourrain <>
Soumis le : mercredi 3 mai 2017 - 11:37:59
Dernière modification le : mardi 29 août 2017 - 19:16:09
Document(s) archivé(s) le : vendredi 4 août 2017 - 12:13:52

Fichiers

paper-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bernard Mourrain. Fast algorithm for border bases of Artinian Gorenstein algebras. ISSAC'17, Jul 2017, Kaiserslautern, Germany. ACM New York, NY, USA, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation pp.333-340, hal-01515366. 〈10.1145/3087604.3087632〉. 〈hal-01515366〉

Partager

Métriques

Consultations de la notice

181

Téléchargements de fichiers

45