Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubresultants of $(x-alpha)^m$ and $(x-beta)^n$, Jacobi polynomials and complexity
83
0
0.0
(
0
)
Added by
Alin Bostan
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In an earlier article together with Carlos DAndrea [BDKSV2017], we described explicit expressions for the coefficients of the order-$d$ polynomial subresultant of $(x-alpha)^m$ and $(x-beta)^n $ with respect to Bernsteins set of polynomials ${(x-alpha)^j(x-beta)^{d-j}, , 0le jle d}$, for $0le d<min{m, n}$. The current paper further develops the study of these structured polynomials and shows that the coefficients of the subresultants of $(x-alpha)^m$ and $(x-beta)^n$ with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. The result is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are scalar multiples of Jacobi polynomials up to an affine change of variables.
rate research
Read More
The texttt{StronglyStableIdeals} package for textit{Macaulay2} provides a method to compute all saturated strongly stable ideals in a given polynomial ring with a fixed Hilbert polynomial. A description of the main method and auxiliary tools is given.
It is well-known that a connected regular graph is strongly-regular if and only if its adjacency matrix has exactly three eigenvalues. Let $B$ denote an integral square matrix and $langle B rangle$ denote the subring of the full matrix ring generated by $B$. Then $langle B rangle$ is a free $mathbb{Z}$-module of finite rank, which guarantees that there are only finitely many ideals of $langle B rangle$ with given finite index. Thus, the formal Dirichlet series $zeta_{langle B rangle}(s)=sum_{ngeq 1}a_n n^{-s}$ is well-defined where $a_n$ is the number of ideals of $langle B rangle$ with index $n$. In this article we aim to find an explicit form of $zeta_{langle B rangle}(s)$ when $B$ has exactly three eigenvalues all of which are integral, e.g., the adjacency matrix of a strongly-regular graph which is not a conference graph with a non-squared number of vertices. By isomorphism theorem for rings, $langle B rangle$ is isomorphic to $mathbb{Z}[x]/m(x)mathbb{Z}[x]$ where $m(x)$ is the minimal polynomial of $B$ over $mathbb{Q}$, and $mathbb{Z}[x]/m(x)mathbb{Z}[x]$ is isomorphic to $mathbb{Z}[x]/m(x+gamma)mathbb{Z}[x]$ for each $gammain mathbb{Z}$. Thus, the problem is reduced to counting the number of ideals of $mathbb{Z}[x]/x(x-alpha)(x-beta)mathbb{Z}[x]$ with given finite index where $0,alpha$ and $beta$ are distinct integers.
The polynomial $f_{2n}(x)=1+x+cdots+x^{2n}$ and its minimizer on the real line $x_{2n}=operatorname{arg,inf} f_{2n}(x)$ for $ninBbb N$ are studied. Results show that $x_{2n}$ exists, is unique, corresponds to $partial_x f_{2n}(x)=0$, and resides on the interval $[-1,-1/2]$ for all $n$. It is further shown that $inf f_{2n}(x)=(1+2n)/(1+2n(1-x_{2n}))$ and $inf f_{2n}(x)in[1/2,3/4]$ for all $n$ with an exact solution for $x_{2n}$ given in the form of a finite sum of hypergeometric functions of unity argument. Perturbation theory is applied to generate rapidly converging and asymptotically exact approximations to $x_{2n}$. Numerical studies are carried out to show how many terms of the perturbation expansion for $x_{2n}$ are needed to obtain suitably accurate approximations to the exact value.
Let $p(x)$ be an integer polynomial with $mge 2$ distinct roots $rho_1,ldots,rho_m$ whose multiplicities are $boldsymbol{mu}=(mu_1,ldots,mu_m)$. We define the D-plus discriminant of $p(x)$ to be $D^+(p):= prod_{1le i<jle m}(rho_i-rho_j)^{mu_i+mu_j}$. We first prove a conjecture that $D^+(p)$ is a $boldsymbol{mu}$-symmetric function of its roots $rho_1,ldots,rho_m$. Our main result gives an explicit formula for $D^+(p)$, as a rational function of its coefficients. Our proof is ideal-theoretic, based on re-casting the classic Poisson resultant as the symbolic Poisson formula. The D-plus discriminant first arose in the complexity analysis of a root clustering algorithm from Becker et al. (ISSAC 2016). The bit-complexity of this algorithm is proportional to a quantity $log(|D^+(p)|^{-1})$. As an application of our main result, we give an explicit upper bound on this quantity in terms of the degree of $p$ and its leading coefficient.
Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored. Such objects are ubiquitous in exact computing, and so naturally we would like to have efficient algorithms to handle them. However, with this compact storage comes new algorithmic challenges, as fast algorithms for dense polynomials may no longer be efficient. In this tutorial we examine the state of the art for sparse polynomial algorithms in three areas: arithmetic, interpolation, and factorization. The aim is to highlight recent progress both in theory and in practice, as well as opportunities for future work.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
