The maximum Perron roots of digraphs with some given parameters

We characterize the extremal digraphs which attain the maximum Perron root of digraphs with given arc connectivity and number of vertices. We also characterize the extremal digraphs which attain the maximum Perron root of digraphs given diameter and number of vertices.     

On the Laplacian coefficients of bicyclic graphs

Let G be a graph of order n and let be the characteristic polynomial of its Laplacian matrix. Generalizing the approach in [D. Stevanovi?, A. Ili?, On the Laplacian coefficients of unicyclic graphs, Linear Algebra and its Applications 430 (2009) 2290-2300.] on graph transformations, we show that among all bicyclic graphs of order n, the kth coefficient c_k is smallest when the graph is B_n (obtained from C₄ by adding one edge connecting two non-adjacent vertices and adding n−4 pendent vertices attached to the vertex of degree 3).     

Determining the multiplicity of a root of a nonlinear algebraic equation

Newton’s method is most frequently used to find the roots of a nonlinear algebraic equation. The convergence domain of Newton’s method can be expanded by applying a generalization known as the continuous analogue of Newton’s method. For the classical and generalized Newton methods, an effective root-finding technique is proposed that simultaneously determines root multiplicity. Roots of high multiplicity (up to 10) can be calculated with a small error. The technique is illustrated using numerical examples.     

Gale duality bounds for roots of polynomials with nonnegative coefficients

We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most d. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.     

Computing the real roots of a polynomial by the exclusion algorithm

We describe a new algorithm for localizing the real roots of a polynomialP(x). This algorithm determines intervals on whichP(x) does not possess any root. The remainder set contains the real roots ofP(x) and can be arbitrarily small.     

On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients

Kostka numbers and Littlewood-Richardson coefficients appear in combinatorics and representation theory. Interest in their computation stems from the fact that they are present in quantum mechanical computations since Wigner [15]. In recent times, there have been a number of algorithms proposed to perform this task [1–3, 11, 12]. The issue of their computational complexity has received at-tention in the past, and was raised recently by E. Rassart in [11]. We prove that the problem of computing either quantity is #P-complete. Thus, unless P = NP, which is widely disbelieved, there do not exist efficient algorithms that compute these numbers.     

Reliably computing all characteristic roots of delay differential equations in a given right half plane using a spectral method

Spectral discretization methods are well established methods for the computation of characteristic roots of time-delay systems. In this paper a method is presented for computing all characteristic roots in a given right half plane. In particular, a procedure for the automatic selection of the number of discretization points is described. This procedure is grounded in the connection between a spectral discretization and a rational approximation of exponential functions. First, a region that contains all desired characteristic roots is estimated. Second, the number of discretization points is selected in such a way that in this region the rational approximation of the exponential functions is accurate. Finally, the characteristic roots approximations, obtained from solving the discretized eigenvalue problem, are corrected up to the desired precision by a local method. The effectiveness and robustness of the procedure are illustrated with several examples and compared with DDE-BIFTOOL.     

Limit distribution of the coefficients of polynomials with only unit roots

We consider sequences of random variables whose probability generating functions have only roots on the unit circle, which has only been sporadically studied in the literature. We show that the random variables are asymptotically normally distributed if and only if the fourth central and normalized (by the standard deviation) moment tends to 3, in contrast to the common scenario for polynomials with only real roots for which a central limit theorem holds if and only if the variance is unbounded. We also derive a representation theorem for all possible limit laws and apply our results to many concrete examples in the literature, ranging from combinatorial structures to numerical analysis, and from probability to analysis of algorithms. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,707–738, 2015     

具有质载和内抑制剂的非均匀恒化器模型共存解的多重性

本文研究一类具有质载和内抑制剂的非均匀恒化器竞争模型. 基于对第二类极限系统分歧的进一步分析, 我们研究了此模型共存解的多重性和稳定性, 从而在一定条件下得到了模型共存解分歧的确切形状, 验证了已有的数值结果.     

On the imaginary parts of chromatic roots

While much attention has been directed to the maximum modulus and maximum real part of chromatic roots of graphs of order $n$ (ie, with $n$ vertices), relatively little is known about the maximum imaginary part of such graphs. We prove that the maximum imaginary part can grow linearly in the order of the graph. We also show that for any fixed $\text{◂+▸}p\in \left(0,1\right)$, almost every random graph $G$ in the Erdös-Rényi model has a nonreal root.     

A note about the average number of real roots of a Bernstein polynomial system

We prove that the real roots of normal random homogeneous polynomial systems with n+1$n+1$ variables and given degrees are, in some sense, equidistributed in the projective space P(Rⁿ⁺¹)$\mathbb{P}\left({\mathbb{R}}^{n+1}\right)$. From this fact we compute the average number of real roots of normal random polynomial systems given in the Bernstein basis.     

Approximation by polynomials with nonnegative coefficients and the spectral theory of positive operators

For a compact subset of symmetric with respect to conjugation and a continuous function, we obtain sharp conditions on and that insure that can be approximated uniformly on by polynomials with nonnegative coefficients. For a real Banach space, a closed but not necessarily normal cone with , and a bounded linear operator with , we use these approximation theorems to investigate when the spectral radius of belongs to its spectrum . A special case of our results is that if is a Hilbert space, is normal and the 1-dimensional Lebesgue measure of is zero, then . However, we also give an example of a normal operator (where is unitary and ) for which and .

     

Fibre products of supersingular curves and the enumeration of irreducible polynomials with prescribed coefficients

For any positive integers $n\ge 3$, $r\ge 1$ we present formulae for the number of irreducible polynomials of degree n over the finite field ${\mathbb{F}}_{2^r}$ where the coefficients of $x^{n-1}$, $x^{n-2}$ and $x^{n-3}$ are zero. Our proofs involve counting the number of points on certain algebraic curves over finite fields, a technique which arose from Fourier-analysing the known formulae for the ${\mathbb{F}}_2$ base field cases, reverse-engineering an economical new proof and then extending it. This approach gives rise to fibre products of supersingular curves and makes explicit why the formulae have period 24 in n.     

布尔矩阵平方根问题及其与图着色问题的关系

讨论了布尔矩阵平方根问题及其与图着色问题的关系.首先得到有平方根的布尔矩阵具有的一些性质;然后给出布尔矩阵存在平方根的一个充要条件;最后证明布尔矩阵的平方根问题可以转化为简单图的着色问题.     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

Ultraconvergence of the derivative of high-order finite element method for elliptic problems with constant coefficients

In this article, for second order elliptic problems with constant coefficients, the local ultraconvergence of the derivative of finite element method using piecewise polynomials of degrees k (k ≥ 2) is studied by the interpolation postprocessing technique. Under suitable regularity and mesh conditions, we prove that at an interior vertex, which is away from the boundary with a fixed distance, the gradient of the postprecessed finite element solution using piecewise polynomials of degrees k (k ≥ 2) converges to the gradient of the exact solution with order . Numerical experiments are used to illustrate our theoretical findings.     

Approximation by rational functions with polynomials of positive coefficients as the denominators

The present paper proves that if f(x) ∈ C[0,1], changes its sign exactly l times at 0 ＜ y1 ＜ y2 ＜y1＜1 in(0,1),then there exists a pn (x)пn( ),such that |f(x)-p(x)/pn(x)|≤ Cωφ(f,n-1/2),where ρ(x) is defined by ρ(x)=l∏i=1(x - yi), if f(x) ≥ 0 for x ∈ (yl, 1),-1∏i=1(x-yi), iff(x) ＜ 0 for x ∈ (y1,1).which improves and generalizes the result of [7].