اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Sparse Flat Extension Theorem for Moment Matrices
109
0
0.0
(
0
)
تأليف
Monique Laurent
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its border, assuming that this set is connected to 1. When formulated in a basis-free setting, this gives an equivalent result for truncated Hankel operators.
قيم البحث
اقرأ أيضاً
Let $f_1,...,f_s in mathbb{K}[x_1,...,x_m]$ be a system of polynomials generating a zero-dimensional ideal $I$, where $mathbb{K}$ is an arbitrary algebraically closed field. We study the computation of matrices of traces for the factor algebra $A :=
CC[x_1, ..., x_m]/ I$, i.e. matrices with entries which are trace functions of the roots of $I$. Such matrices of traces in turn allow us to compute a system of multiplication matrices ${M_{x_i}|i=1,...,m}$ of the radical $sqrt{I}$. We first propose a method using Macaulay type resultant matrices of $f_1,...,f_s$ and a polynomial $J$ to compute moment matrices, and in particular matrices of traces for $A$. Here $J$ is a polynomial generalizing the Jacobian. We prove bounds on the degrees needed for the Macaulay matrix in the case when $I$ has finitely many projective roots in $mathbb{P}^m_CC$. We also extend previous results which work only for the case where $A$ is Gorenstein to the non-Gorenstein case. The second proposed method uses Bezoutian matrices to compute matrices of traces of $A$. Here we need the assumption that $s=m$ and $f_1,...,f_m$ define an affine complete intersection. This second method also works if we have higher dimensional components at infinity. A new explicit description of the generators of $sqrt{I}$ are given in terms of Bezoutians.
Ritt-Wus algorithm of characteristic sets is the most representative for triangularizing sets of multivariate polynomials. Pseudo-division is the main operation used in this algorithm. In this paper we present a new algorithmic scheme for computing g
eneralized characteristic sets by introducing other admissible reductions than pseudo-division. A concrete subalgorithm is designed to triangularize polynomial sets using selected admissible reductions and several effective elimination strategies and to replace the algorithm of basic sets (used in Ritt-Wus algorithm). The proposed algorithm has been implemented and experimental results show that it performs better than Ritt-Wus algorithm in terms of computing time and simplicity of output for a number of non-trivial test examples.
Borel-fixed ideals play a key role in the study of Hilbert schemes. Indeed each component and each intersection of components of a Hilbert scheme contains at least one Borel-fixed point, i.e. a point corresponding to a subscheme defined by a Borel-fi
xed ideal. Moreover Borel-fixed ideals have good combinatorial properties, which make them very interesting in an algorithmic perspective. In this paper, we propose an implementation of the algorithm computing all the saturated Borel-fixed ideals with number of variables and Hilbert polynomial assigned, introduced from a theoretical point of view in the paper Segment ideals and Hilbert schemes of points, Discrete Mathematics 311 (2011).
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the correctness of each output. Wiede-manns algorithm projects the Krylov sequ
ence obtained by repeatedly multiplying a vector by a matrix to obtain a linearly recurrent sequence. The minimal polynomial of this sequence divides the minimal polynomial of the matrix. For instance, if the $ntimes n$ input matrix is sparse with n 1+o(1) non-zero entries, the computation of the sequence is quadratic in the dimension of the matrix while the computation of the minimal polynomial is n 1+o(1), once that projected Krylov sequence is obtained. In this paper we give algorithms that compute certificates for the Krylov sequence of sparse or structured $ntimes n$ matrices over an abstract field, whose Monte Carlo verification complexity can be made essentially linear. As an application this gives certificates for the determinant, the minimal and characteristic polynomials of sparse or structured matrices at the same cost.
The class of quasiseparable matrices is defined by the property that any submatrix entirely below or above the main diagonal has small rank, namely below a bound called the order of quasiseparability. These matrices arise naturally in solving PDEs fo
r particle interaction with the Fast Multi-pole Method (FMM), or computing generalized eigenvalues. From these application fields, structured representations and algorithms have been designed in numerical linear algebra to compute with these matrices in time linear in the matrix dimension and either quadratic or cubic in the quasiseparability order. Motivated by the design of the general purpose exact linear algebra library LinBox, and by algorithmic applications in algebraic computing, we adapt existing techniques introduce novel ones to use quasiseparable matrices in exact linear algebra, where sub-cubic matrix arithmetic is available. In particular, we will show, the connection between the notion of quasiseparability and the rank profile matrix invariant, that we have introduced in 2015. It results in two new structured representations, one being a simpler variation on the hierarchically semiseparable storage, and the second one exploiting the generalized Bruhat decomposition. As a consequence, most basic operations, such as computing the quasiseparability orders, applying a vector, a block vector, multiplying two quasiseparable matrices together, inverting a quasiseparable matrix, can be at least as fast and often faster than previous existing algorithms.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
