On sharp bounds for spectral radius of nonnegative matrices

We give sharp upper and lower bounds for the spectral radius of a nonnegative matrix with positive row sums using average 3-row sums, compare these bounds with the existing bounds using the average 2-row sums by examples, and apply them to the adjacency matrix and the signless Laplacian matrix of a digraph or a graph.     

Some new bounds on the spectral radius of matrices

A new lower bound on the smallest eigenvalue τ(AB) for the Fan product of two nonsingular M-matrices A and B is given. Meanwhile, we also obtain a new upper bound on the spectral radius ρ(A°B) for nonnegative matrices A and B. These bounds improve some results of Huang (2008) [R. Huang, Some inequalities for the Hadamard product and the Fan product of matrices, Linear Algebra Appl. 428 (2008) 1551-1559].     

Tight bounds on the spectral radius of asymmetric nonnegative matrices

For an arbitrary asymmetric nonnegative n × n matrix A we identify a pair of symmetric matrices whose largest eigenvalues bound the spectral radius of A. Furthermore, we show that these bounding matrices are best possible by characterizing matrices A which attain equality with either the upper or the lower bounding matrix. The lower bound may be extended to some matrices with negative entries provided they have no negative cycles.     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Deterministic global derivative-free optimization of black-box problems with bounded Hessian

Obtaining guaranteed lower bounds for problems with unknown algebraic form has been a major challenge in derivative-free optimization. In this work, we pre     

Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.      

Upper bounds for the eigenvalues of Hessian equations

In this paper, we prove some upper bounds for the Dirichlet eigenvalues of a class of fully nonlinear elliptic equations, namely the Hessian equations.     

Connecting optimization with spectral analysis of tri-diagonal matrices

Mathematical Programming - We show that the global minimum (resp. maximum) of a continuous function on a compact set can be approximated from above (resp. from below) by computing the smallest...     

Optimal norms and the computation of joint spectral radius of matrices

The notion of spectral radius of a set of matrices is a natural extension of spectral radius of a single matrix. The finiteness conjecture (FC) claims that among the infinite products made from the elements of a given finite set of matrices, there is a certain periodic product, made from the repetition of the optimal product, whose rate of growth is maximal. FC has been disproved. In this paper it is conjectured that FC is almost always true, and an algorithm is presented to verify the optimality of a given product. The algorithm uses optimal norms, as a special subset of extremal norms. Several conjectures related to optimal norms and non-decomposable sets of matrices are presented. The algorithm has successfully calculated the spectral radius of several parametric families of pairs of matrices associated with compactly supported multi-resolution analyses and wavelets. The results of related numerical experiments are presented.     

A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions

We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a numerical example, we apply the proposed branch and bound algorithm to radial basis function approximations.     

Efficient computation of the exponential operator for large,sparse, symmetric matrices

In this paper we compare Krylov subspace methods with Chebyshev series expansion for approximating the matrix exponential operator on large, sparse, symmetric matrices. Experimental results upon negative‐definite matrices with very large size, arising from (2D and 3D) FE and FD spatial discretization of linear parabolic PDEs, demonstrate that the Chebyshev method can be an effective alternative to Krylov techniques, especially when memory bounds do not allow the storage of all Ritz vectors. We also discuss the sensitivity of Chebyshev convergence to extreme eigenvalue approximation, as well as the reliability of various a priori and a posteriori error estimates for both methods. Copyright © 2000 John Wiley & Sons, Ltd.     

Parallel computation of spectral portrait of large matrices by Davidson type methods

The eigenanalysis of matrices or operators based only on the knowledge of the spectrum may be misleading in the non-normal case. Instead of the spectrum, one may fully characterize the spectral behavior of a non-normal matrix by analyzing its spectral portrait, i.e., the set of its resolvent norm. In this paper, we propose a parallel version of the generalized Davidson method for analyzing and plotting the spectral portrait of large non-normal matrices. We report the performance results obtained on the machine Paragon. This revised version was published online in August 2006 with corrections to the Cover Date.     

On spectral bounds for cutsets

Let Γ be a simple and connected graph. A k-vertex separator [k-edge separator] is a subset of vertices [edges] whose deletion separates the vertex [edge] set of Γ into two parts of equal cardinality, that are at distance greater than k in Γ. Here we investigate the relation between the cardinality of these cutsets and the laplacian spectrum of Γ. As a consequence of the study, we obtain the well-known lower bounds for the bandwidth and the bipartition width of a graph.     

New permanental bounds for Ferrers matrices

We survey the most recent results on permanental bounds of a nonnegative matrix. Some older bounds are revisited as well. Applying refinements of the arithmetic mean-geometric mean inequality leads to sharp bounds for the permanent of a fully indecomposable Ferrers matrix. In the end, several relevant examples comparing the bounds are discussed.     

Spectral variation bounds for diagonalisable matrices

Summary This note is related to an earlier paper by Bhatia, Davis, and Kittaneh [4]. For matrices similar to Hermitian, we prove an inequality complementary to the one proved in [4, Theorem 3]. We also disprove a conjecture made in [4] about the norm of a commutator. This work was done when the first author visited the SFB 343 at University of Bielefeld in May and June 1994.     

Eigenvalue bounds for block preconditioned matrices

In the symmetric positive definite case, two-sided eigenvalue bounds for block Jacobi scaled matrices and upper eigenvalue bounds for matrices preconditioned with an incomplete block factorization are derived. A quantitative characterization of block matrix partitionings is also suggested, which can be used when analyzing various block preconditioning methods. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 5–41.