We analyze the decomposition problem of multivariate polynomial-exponential functions from truncated series and present new algorithms to compute their decomposition. Using the duality between polynomials and formal power series, we first show how the elements in the dual of an Artinian algebra correspond to polynomial-exponential functions. They are also the solutions of systems of partial differential equations with constant coefficients. We relate their representation to the inverse system of the roots of the characteristic variety. Using the properties of Hankel operators, we establish a correspondence between polynomial exponential series and Artinian Gorenstein algebras. We generalize Kronecker theorem to the multivariate case, by showing that the symbol of a Hankel operator of finite rank is a polynomial-exponential series and by connecting the rank of the Hankel operator with the decomposition of the symbol. A generalization of Prony's approach to multivariate decomposition problems is presented , exploiting eigenvector methods for solving polynomial equations. We show how to compute the frequencies and weights of a minimal polynomial-exponential decomposition , using the first coefficients of the series. A key ingredient of the approach is the flat extension criteria, which leads to a multivariate generalization of a rank condition for a Carath 'e odory-Fej 'e r decomposition of multivariate Hankel matrices. A new algorithm is given to compute a basis of the Artinian Gorenstein algebra, based on a Gram-Schmidt orthogonalization process and to decompose polynomial-exponential series. A general framework for the applications of this approach is described and illustrated in different problems. We provide Kronecker-type theorems for convolution operators, showing that a convolution operator (or a cross-correlation operator) is of finite rank, if and only if, its symbol is a polynomial-exponential function, and we relate its rank to the decomposition of its symbol. We also present Kronecker-type theorems for the reconstruction of measures as weighted sums of Dirac measures from moments and for the decomposition of polynomial-exponential functions from values. Finally, we describe an application of this method for the sparse interpolation of polylog functions from values.
Hankel matrices and their kernels also play an important role in error correcting codes. Reed-Solomon codes, obtained by evaluation of a polynomial at a set of points and convolution by a given polynomial, can be decoded from their syndrome sequence by computing the error locator polynomial @cite_37 [chap. 9]. This is a linear recurrence relation between the syndrome coefficients, which corresponds to a non-zero element in the kernel of a Hankel matrix. Berlekamp @cite_44 and Massey @cite_54 proposed an efficient algorithm to compute such polynomials. Sakata extended the approach to compute Gr "o bner bases of polynomials in the kernel of a multivariate Hankel matrix @cite_56 . The computation of multivariate linear recurrence relations have been further investigated, e.g. in @cite_40 and more recently in @cite_18 .
@cite_37 @cite_18 @cite_54 @cite_56 @cite_44 @cite_40
2555323499 2170042437 1988452081 2018818965
The so-called Berlekamp -- Massey -- Sakata algorithm computes a Grobner basis of a @math -dimensional ideal of relations satisfied by an input table. It extends the Berlekamp -- Massey algorithm to @math -dimensional tables, for @math . We investigate this problem and design several algorithms for computing such a Grobner basis of an ideal of relations using linear algebra techniques. The first one performs a lot of table queries and is analogous to a change of variables on the ideal of relations. As each query to the table can be expensive, we design a second algorithm requiring fewer queries, in general. This -like algorithm allows us to compute the relations of the table by extracting a full rank submatrix of a matrix (a multivariate generalization of Hankel matrices). Under some additional assumptions, we make a third, adaptive, algorithm and reduce further the number of table queries. Then, we relate the number of queries of this third algorithm to the of the final staircase and we show that it is essentially linear in the size of the output when the staircase is convex. As a direct application to this, we decode @math -cyclic codes, a generalization in dimension @math of Reed Solomon codes. We show that the multi-Hankel matrices are heavily structured when using the ordering and that we can speed up the computations using fast algorithms for quasi-Hankel matrices. Finally, we design algorithms for computing the generating series of a linear recursive table. Let H0, …, H n be m x m matrices with entries in Q and Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel matrix H(x) = H0+x1H_1+…+xnHn and the problem of computing sample points in each connected component of the real algebraic set defined by the rank constraint rank (H(x))≤ r, for a given integer r ≤ m-1. Computing sample points in real algebraic sets defined by rank defects in linear matrices is a general problem that finds applications in many areas such as control theory, computational geometry, optimization, etc. Moreover, Hankel matrices appear in many areas of engineering sciences. Also, since Hankel matrices are symmetric, any algorithmic development for this problem can be seen as a first step towards a dedicated exact algorithm for solving semi-definite programming problems, i.e. linear matrix inequalities. Under some genericity assumptions on the input (such as smoothness of an incidence variety), we design a probabilistic algorithm for tackling this problem. It is an adaptation of the so-called critical point method that takes advantage of the special structure of the problem. Its complexity reflects this: it is essentially quadratic in specific degree bounds on an incidence variety. We report on practical experiments and analyze how the algorithm takes advantage of this special structure. A first implementation outperforms existing implementations for computing sample points in general real algebraic sets: it tackles examples that are out of reach of the state-of-the-art. The generalized eigenvalue problem @math with H a Hankel matrix and @math the corresponding shifted Hankel matrix occurs in number of applications such as the reconstruction of the shape of a polygon from its moments, the determination of abscissa of quadrature formulas, of poles of Pade approximants, or of the unknown powers of a sparse black box polynomial in computer algebra. In many of these applications, the entries of the Hankel matrix are only known up to a certain precision. We study the sensitivity of the nonlinear application mapping the vector of Hankel entries to its generalized eigenvalues. A basic tool in this study is a result on the condition number of Vandermonde matrices with not necessarily real abscissas which are possibly row-scaled. Recently, a uniform approach was given by B. Beckermann and G. Labahn [Numer. Algorithms, 3 (1992), pp. 45-54] for different concepts of matrix-type Pade approximants, such as descriptions of vector and matrix Pade approximants along with generalizations of simultaneous and Hermite Pade approximants. The considerations in this paper are based on this generalized form of the classical scalar Hermite Pade approximation problem, power Hermite Pade approximation. In particular, this paper studies the problem of computing these new approximants. A recurrence relation is presented for the computation of a basis for the corresponding linear solution space of these approximants. This recurrence also provides bases for particular subproblems. This generalizes previous work by Van Barel and Bultheel and, in a more general form, by Beckermann. The computation of the bases has complexity @math , where @math is the order of the desired approximant and requires no conditions on the input data. A second algorithm using the same recurrence relation along with divide-and-conquer methods is also presented. When the coefficient field allows for fast polynomial multiplication, this second algorithm computes a basis in the superfast complexity @math . In both cases the algorithms are reliable in exact arithmetic. That is, they never break down, and the complexity depends neither on any normality assumptions nor on the singular structure of the corresponding solution table. As a further application, these methods result in fast (and superfast) reliable algorithms for the inversion of striped Hankel, layered Hankel, and (rectangular) block-Hankel matrices.