Two-sided bounds of eigenvalues of second-and fourth-order elliptic operators

This article presents an idea in the finite element methods (FEMs) for obtaining two-sided bounds of exact eigenvalues. This approach is based on the combination of nonconforming methods giving lower bounds of the eigenvalues and a postprocessing technique using conforming finite elements. Our results hold for the second and fourth-order problems defined on two-dimensional domains. First, we list analytic and experimental results concerning triangular and rectangular nonconforming elements which give at least asymptotically lower bounds of the exact eigenvalues. We present some new numerical experiments for the plate bending problem on a rectangular domain. The main result is that if we know an estimate from below by nonconforming FEM, then by using a postprocessing procedure we can obtain two-sided bounds of the first (essential) eigenvalue. For the other eigenvalues λ_l, l = 2, 3, …, we prove and give conditions when this method is applicable. Finally, the numerical results presented and discussed in the paper illustrate the efficiency of our method.     

Nonconforming finite element approximations of the Steklov eigenvalue problem and its lower bound approximations

The paper deals with error estimates and lower bound approximations of the Steklov eigenvalue problems on convex or concave domains by nonconforming finite element methods. We consider four types of nonconforming finite elements: Crouzeix-Raviart, Q ₁ ^rot , EQ ₁ ^rot and enriched Crouzeix-Raviart. We first derive error estimates for the nonconforming finite element approximations of the Steklov eigenvalue problem and then give the analysis of lower bound approximations. Some numerical results are presented to validate our theoretical results.     

Eigenvalues Estimate for the Neumann Problem of a Bounded Domain

In this note, we investigate upper bounds of the Neumann eigenvalue problem for the Laplacian of a domain Ω in a given complete (not compact a priori) Riemannian manifold (M,g). For this, we use test functions for the Rayleigh quotient subordinated to a family of open sets constructed in a general metric way, interesting for itself. As applications, we prove that if the Ricci curvature of (M,g) is bounded below Ric  ^g ≥−(n−1)a ², a≥0, then there exist constants A _n >0,B _n >0 only depending on the dimension, such that

Estimates for the eigenvalues of Hill's equation and applications for the eigenvalues of the laplacian on toroidal surfaces

In this paper we give upper and lower bounds for each eigenvalue λ _n of Hill's differential equation. We apply the results to toroidal surfaces of revolution in order to get estimates for the eigenvalues of the Laplacian in terms of curvature expressions; they are sharp for the flat torus. As an example, we investigate the standard torus in IR³; here, the bounds depend on the radii only.     

Conformal upper bounds for the eigenvalues of the Laplacian and Steklov problem

In this paper, we find upper bounds for the eigenvalues of the Laplacian in the conformal class of a compact Riemannian manifold (M,g). These upper bounds depend only on the dimension and a conformal invariant that we call “min-conformal volume”. Asymptotically, these bounds are consistent with the Weyl law and improve previous results by Korevaar and Yang and Yau. The proof relies on the construction of a suitable family of disjoint domains providing supports for a family of test functions. This method is interesting for itself and powerful. As a further application of the method we obtain an upper bound for the eigenvalues of the Steklov problem in a domain with C¹ boundary in a complete Riemannian manifold in terms of the isoperimetric ratio of the domain and the conformal invariant that we introduce.     

Markov-Bernstein inequalities for generalized Gegenbauer weight

The Markov-Bernstein inequalities for generalized Gegenbauer weight are studied. A special basis of the vector space Pn of real polynomials in one variable of degree at most equal to n is proposed. It is produced by quasi-orthogonal polynomials with respect to this generalized Gegenbauer measure. Thanks to this basis the problem to find the Markov-Bernstein constant is separated in two eigenvalue problems. The first has a classical form and we are able to give lower and upper bounds of the Markov-Bernstein constant by using the Newton method and the classical qd algorithm applied to a sequence of orthogonal polynomials. The second is a generalized eigenvalue problem with a five diagonal matrix and a tridiagonal matrix. A lower bound is obtained by using the Newton method applied to the six term recurrence relation produced by the expansion of the characteristic determinant. The asymptotic behavior of an upper bound is studied. Finally, the asymptotic behavior of the Markov-Bernstein constant is O(n²) in both cases.     

Inverse inequality estimates with symbolic computation

In the convergence analysis of numerical methods for solving partial differential equations (such as finite element methods) one arrives at certain generalized eigenvalue problems, whose maximal eigenvalues need to be estimated as accurately as possible. We apply symbolic computation methods to the situation of square elements and are able to improve the previously known upper bound, given in “p- and hp-finite element methods” (Schwab, 1998), by a factor of 8. More precisely, we try to evaluate the corresponding determinant using the holonomic ansatz, which is a powerful tool for dealing with determinants, proposed by Zeilberger in 2007. However, it turns out that this method does not succeed on the problem at hand. As a solution we present a variation of the original holonomic ansatz that is applicable to a larger class of determinants, including the one we are dealing with here. We obtain an explicit closed form for the determinant, whose special form enables us to derive new and tight upper resp. lower bounds on the maximal eigenvalue, as well as its asymptotic behaviour.     

Upper bounds for the first zeros of Bessel functions

An upper bound for the first positive zero of the Bessel functions of first kind J_μ(z) for μ > −1 is given. This upper bound is better than a number of upper bounds found recently by several authors. The upper bound given in this paper follows from a step of the Ritz's approximation method, applied to the eigenvalue problem of a compact self-adjoint operator, defined on an abstract separable Hilbert space. Some advantages of this method in comparison with other approximation methods are presented.     

Eigenvalue estimates of the p-Laplacian on finite graphs

In this paper, we study the eigenvalue of p-Laplacian on finite graphs. Under generalized curvature dimensional condition, we obtain a lower bound of the first nonzero eigenvalue of p-Laplacian. Moreover, a upper bound of the largest p-Laplacian eigenvalue is derived.     

Bounding the spectrum of large Hermitian matrices

Estimating upper bounds of the spectrum of large Hermitian matrices has long been a problem with both theoretical and practical significance. Algorithms that can compute tight upper bounds with minimum computational cost will have applications in a variety of areas. We present a practical algorithm that exploits k-step Lanczos iteration with a safeguard step. The k is generally very small, say 5-8, regardless of the large dimension of the matrices. This makes the Lanczos iteration economical. The safeguard step can be realized with marginal cost by utilizing the theoretical bounds developed in this paper. The bounds establish the theoretical validity of a previous bound estimator that has been successfully used in various applications. Moreover, we improve the bound estimator which can now provide tighter upper bounds with negligible additional cost.     

Bounds for norms of the matrix inverse and the smallest singular value

In the first part, we obtain two easily calculable lower bounds for ‖A^-1‖, where ‖·‖ is an arbitrary matrix norm, in the case when A is an M-matrix, using first row sums and then column sums. Using those results, we obtain the characterization of M-matrices whose inverses are stochastic matrices. With different approach, we give another easily calculable lower bounds for ‖A^-1‖_∞ and ‖A^-1‖₁ in the case when A is an M-matrix. In the second part, using the results from the first part, we obtain our main result, an easily calculable upper bound for ‖A^-1‖₁ in the case when A is an SDD matrix, thus improving the known bound. All mentioned norm bounds can be used for bounding the smallest singular value of a matrix.     

Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story

Let C_n,cn^2,k,t be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions. We establish upper bounds for the tightness threshold for C_n,cn^2,k,t to have an exponential resolution complexity. The upper bounds partly answers the open problems regarding the CSP resolution complexity with the tightness between the existing upper and lower bound [1].     

Edge search in graphs with restricted test sets

Suppose a graph G(V,E) contains one defective edge e. We search for the endpoints of e by asking questions of the form “Is at least one of the vertices of X an endpoint of e?”, where X is a subset of V with cardinality at most p. Then what is the minimum number c_p(G) of questions, which are needed in the worst case to find e?We solve this search problem suggested by M. Aigner in [M. Aigner, Combinatorial Search, Teubner, 1988] by deriving lower and sharp upper bounds for c_p(G). For the case that G is the complete graph K_n the problem described above is equivalent to the (2,n) group testing problem with test sets of cardinality at most p. We present sharp upper and lower bounds for the worst case number c_p of tests for this group testing problem and show that the maximum difference between the upper and the lower bounds is 3.     

Optimal designs for weighted approximation and integration of stochastic processes on [0,∞)

We study minimal errors and optimal designs for weighted L₂-approximation and weighted integration of Gaussian stochastic processes X defined on the half-line [0,∞). Under some regularity conditions, we obtain sharp bounds for the minimal errors for approximation and upper bounds for the minimal errors for integration. The upper bounds are proven constructively for approximation and non-constructively for integration. For integration of the r-fold integrated Brownian motion, the upper bound is proven constructively and we have a matching lower bound.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

Optimal lower bound estimates for the blow-up rate for the Zakharov system in a nonhomogeneous medium

In this paper we obtain lower bound estimates for the blow-up rate of finite time blow-up solutions to the Cauchy problem for the Zakharov system in a nonhomogeneous medium in two space dimensions. By introducing suitable scale transformations of space and time, and the use of compactness arguments, we derive an optimal lower bound estimate in the energy space H²(R²)×L²(R²)×H¹(R²) for the blow-up rate for t near the finite blow-up time T. Also we give an application to the virial identity for the Zakharov system under study.     

Global gradient estimate on graph and its applications

Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results.     

Code constructions and existence bounds for relative generalized Hamming weight

The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C ¹ is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C ¹) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound.     

Approximation and eigenvalue extrapolation of Stokes eigenvalue problem by nonconforming finite element methods

In this paper we analyze the stream function-vorticity-pressure method for the Stokes eigenvalue problem. Further, we obtain full order convergence rate of the eigenvalue approximations for the Stokes eigenvalue problem based on asymptotic error expansions for two nonconforming finite elements, Q ₁^rot and EQ ₁^rot. Using the technique of eigenvalue error expansion, the technique of integral identities and the extrapolation method, we can improve the accuracy of the eigenvalue approximations. This project is supported in part by the National Natural Science Foundation of China (10471103) and is subsidized by the National Basic Research Program of China under the grant 2005CB321701.