Paper Info
Title
Fast Algorithm for Border Bases of Artinian Gorenstein Algebras.
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 kernel 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 α ∈ Nn. This structure is explicitly given by a border basis of Aσ, which is presented as a quotient of the polynomial ring K [x1, ..., 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.
Year
DOI
Venue
2017
10.1145/3087604.3087632
ISSAC
Keywords
Field
DocType
Artinian algebra, Gorenstein algebra, linear recurrence relation, Hankel matrix, border basis, Berlekamp-Massey-Sakata algorithm
Kernel (linear algebra),Discrete mathematics,Combinatorics,Algebraic number,Recurrence relation,Algebraic structure,Polynomial ring,Quotient,Algorithm,Formal power series,Hankel matrix,Mathematics
Conference
Citations 
PageRank 
References 
2
0.37
17
Authors
1
Name
Order
Citations
PageRank
Bernard Mourrain11074113.70