اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn finding multiplicities of characteristic polynomial factors of black-box matrices
99
0
0.0
(
0
)
نشر من قبل
Jean-Guillaume Dumas
تاريخ النشر
2009
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
تأليف
Jean-Guillaume Dumas
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present algorithms and heuristics to compute the characteristic polynomial of a matrix given its minimal polynomial. The matrix is represented as a black-box, i.e., by a function to compute its matrix-vector product. The methods apply to matrices either over the integers or over a large enough finite field. Experiments show that these methods perform efficiently in practice. Combined in an adaptive strategy, these algorithms reach significant speedups in practice for some integer matrices arising in an application from graph theory.
قيم البحث
اقرأ أيضاً
We design a fast algorithm that computes, for a given linear differential operator with coefficients in $Z[x ]$, all the characteristic polynomials of its p-curvatures, for all primes $p < N$ , in asymptotically quasi-linear bit complexity in N. We d
iscuss implementations and applications of our algorithm. We shall see in particular that the good performances of our algorithm are quickly visible.
It was recently conjectured by Fyodorov, Hiary and Keating that the maximum of the characteristic polynomial on the unit circle of a $Ntimes N$ random unitary matrix sampled from the Haar measure grows like $CN/(log N)^{3/4}$ for some random variable
$C$. In this paper, we verify the leading order of this conjecture, that is, we prove that with high probability the maximum lies in the range $[N^{1 - varepsilon},N^{1 + varepsilon}]$, for arbitrarily small $varepsilon$. The method is based on identifying an approximate branching random walk in the Fourier decomposition of the characteristic polynomial, and uses techniques developed to describe the extremes of branching random walks and of other log-correlated random fields. A key technical input is the asymptotic analysis of Toeplitz determinants with dimension-dependent symbols. The original argument for these asymptotics followed the general idea that the statistical mechanics of $1/f$-noise random energy models is governed by a freezing transition. We also prove the conjectured freezing of the free energy for random unitary matrices.
Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric ${pm 1}$-matrix is irreducible. This addresses a question raised by Eberhard in recent work. The main innovation i
n our work is establishing sharp estimates regarding the rank distribution of symmetric random ${pm 1}$-matrices over $mathbb{F}_p$ for primes $2 < p leq exp(O(n^{1/4}))$. Previously, such estimates were available only for $p = o(n^{1/8})$. At the heart of our proof is a way to combine multiple inverse Littlewood--Offord-type results to control the contribution to singularity-type events of vectors in $mathbb{F}_p^{n}$ with anticoncentration at least $1/p + Omega(1/p^2)$. Previously, inverse Littlewood--Offord-type results only allowed control over vectors with anticoncentration at least $C/p$ for some large constant $C > 1$.
We show that the averaged characteristic polynomial and the averaged inverse characteristic polynomial, associated with Hermitian matrices whose elements perform a random walk in the space of complex numbers, satisfy certain partial differential, dif
fusion-like, equations. These equations are valid for matrices of arbitrary size. Their solutions can be given an integral representation that allows for a simple study of their asymptotic behaviors for a broad range of initial conditions.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
