Quasiabelian landscapes of the traveling salesman problem are elementary

Regarding a permutation as a (multi-traveler) tour of the traveling salesman problem, we show that—regardless of the distance matrix—the landscape based on a quasiabelian Cayley graph belongs to the class of elementary landscapes, where the cost vector is an eigenvector of the Cayley Laplacian, and where local minima are below average.The quasiabelian case has the additional property that, because the cost vector is an eigenvector of the Cayley Laplacian, the landscape can be reduced into independent components under a Fourier transformation. We indicate the way this may result in parallel (and therefore computationally distributed) traversal of the landscape.     

Heuristic Spectral Techniques for the Reduction of Bandwidth and Work-Bound of Sparse Matrices

In this paper, we present heuristic techniques for the reduction of the bandwidth of a sparse matrix as well as for the reduction of the cost of the associated Cholesky factorization. Our algorithms are inspired by the spectral method of Barnard, Pothen and Simon (1995), which derives a permutation for reducing the envelope-size of a sparse matrix by computing the second eigenvector of the associated Laplacian matrix. Two main modifications of that method are proposed and tested. The first is based on the experimental observation that it is often preferable to perform only few iterations of an iterative method converging to the second eigenvector; the second is the introduction of a weighted Laplacian. These simple ideas allow us to obtain a family of spectral methods that have been carefully tested on a set of matrices whose size ranges from few hundred to one million.     

Sparse spectral clustering method based on the incomplete Cholesky decomposition

A novel sparse spectral clustering method using linear algebra techniques is proposed. Spectral clustering methods solve an eigenvalue problem containing a graph Laplacian. The proposed method exploits the structure of the Laplacian to construct an approximation, not in terms of a low rank approximation but in terms of capturing the structure of the matrix. With this approximation, the size of the eigenvalue problem can be reduced. To obtain the indicator vectors from the eigenvectors the method proposed by Zha et al. (2002) [26], which computes a pivoted LQ$LQ$ factorization of the eigenvector matrix, is adapted. This formulation also gives the possibility to extend the method to out-of-sample points.     

A linear time implementation of the reverse Cuthill-McKee algorithm

The Reverse Cuthill-McKee (RCM) algorithm is a method for reordering a sparse matrix so that it has a small envelope. Given a starting node, we provide an implementation of the algorithm whose run-time complexity is proved to be linear in the number of nonzeros in the matrix. Numerical experiments are provided which compare the performance of the new implementation to a good conventional implementation.     

一个求大规模非负不可约稀疏矩阵的谱半径及特征向量的新算法

本文设计了一个计算非负不可约矩阵的谱半径及其特征向量的新算法,并证明了其收敛性.该算法计算晕不大,占用内存少,有相同的0元模式,从而在大规模稀疏矩阵的计算中优势明显.最后用实例验证了此算法的可行性.     

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.      

On PageRank versatility for multiplex networks: properties and some useful bounds

In this paper, some results concerning the PageRank versatility measure for multiplex networks are given. This measure extends to the multiplex setting the well-known classic PageRank. Particularly, we focus on some spectral properties of the Laplacian matrix of the multiplex and on obtaining boundaries for the ranking value of a given node when some personalization vector is added, as in the classic setting.     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

AHP判断矩阵权向量的改进最小二乘求解

提出了基于最小二乘法计算判断矩阵权向量的新方法.固定AHP判断矩阵权向量中的一个值为常量,利用判断矩阵的上三角部分元素,设计了一种计算判断矩阵权向量的新算法,算法简单,计算容易,与特征向量排序方法导出标度相同,并且能够证明存在唯一解.实验表明该算法具有有效性和可行性.     

Eigenvectors of interval matrices over max–plus algebra

The behaviour of a discrete-event dynamic system is often conveniently described using a matrix algebra with operations max and plus. Such a system moves forward in regular steps of length equal to the eigenvalue of the system matrix, if it is set to operate at time instants corresponding to one of its eigenvectors. However, due to imprecise measurements, it is often unappropriate to use exact matrices. One possibility to model imprecision is to use interval matrices. We show that the problem to decide whether a given vector is an eigenvector of one of the matrices in the given matrix interval is polynomial, while the complexity of the existence problem of a universal eigenvector remains open. As an aside, we propose a combinatorial method for solving two-sided systems of linear equations over the max–plus algebra.     

A sharp upper bound on the maximal entry in the principal eigenvector of symmetric nonnegative matrix

An upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries is investigated in [S. Zhao, Y. Hong, On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix, Linear Algebra Appl. 340 (2002) 245-252]. We obtain a sharp upper bound on the maximal entry y^max_p in the principal eigenvector of symmetric nonnegative matrix in terms of order, the spectral radius, the largest and the smallest diagonal entries of that matrix. Our bound is applicable for any symmetric nonnegative matrix and the upper bound of Zhao and Hong (2002) for the maximal entry y^max_p follows as a special case. Moreover, we find an upper bound on maximal entry in the principal eigenvector for the signless Laplacian matrix of a graph.     

An inverse spectral problem for the Laplacian

We propose an algorithm for the recovery of a potential from the knowledge of the eigenvalues of the Laplacian operator and the traces of its eigenfunctions. This inverse spectral problem is solved by recasting the operator as an infinite matrix and using transition matrices together with spectral projections on the boundary.     

Signless Laplacians of finite graphs

We survey properties of spectra of signless Laplacians of graphs and discuss possibilities for developing a spectral theory of graphs based on this matrix. For regular graphs the whole existing theory of spectra of the adjacency matrix and of the Laplacian matrix transfers directly to the signless Laplacian, and so we consider arbitrary graphs with special emphasis on the non-regular case. The results which we survey (old and new) are of two types: (a) results obtained by applying to the signless Laplacian the same reasoning as for corresponding results concerning the adjacency matrix, (b) results obtained indirectly via line graphs. Among other things, we present eigenvalue bounds for several graph invariants, an interpretation of the coefficients of the characteristic polynomial, a theorem on powers of the signless Laplacian and some remarks on star complements.     

On Spectral Integral Variations of Graphs

Let G be a general graph. The spectrum S ( G ) of G is defined to be the spectrum of its Laplacian matrix. Let G + e be the graph obtained from G by adding an edge or a loop e . We study in this paper when the spectral variation between G and G + e is integral and obtain some equivalent conditions, through which a new Laplacian integral graph can be constructed from a known Laplacian integral graph by adding an edge.     

On Spectral Integral Variations of Graphs

Let G be a general graph. The spectrum S ( G ) of G is defined to be the spectrum of its Laplacian matrix. Let G + e be the graph obtained from G by adding an edge or a loop e . We study in this paper when the spectral variation between G and G + e is integral and obtain some equivalent conditions, through which a new Laplacian integral graph can be constructed from a known Laplacian integral graph by adding an edge.     

The Laplacian spectra of graphs with a tree structure

Trees are very common in the theory and applications of combinatorics. In this article, we consider graphs whose underlying structure is a tree, except that its vertices are graphs in their own right and where adjacent graphs (vertices) are linked by taking their join. We study the spectral properties of the Laplacian matrices of such graphs. It turns out that in order to capture known spectral properties of the Laplacian matrices of trees, it is necessary to consider the Laplacians of vertex-weighted graphs. We focus on the second smallest eigenvalue of such Laplacians and on the properties of their corresponding eigenvector. We characterize the second smallest eigenvalue in terms of the Perron branches of a tree. Finally, we show that our results are applicable to advancing the solution to the problem of whether there exists a graph on n vertices whose Laplacian has the integer eigenvalues 0, 1, …, n ? 1.     

The smallest signless Laplacian spectral radius of graphs with a given clique number

The signless Laplacian spectral radius of a graph G is the largest eigenvalue of its signless Laplacian matrix. In this paper, the first four smallest values of the signless Laplacian spectral radius among all connected graphs with maximum clique of size greater than or equal to 2 are obtained.     

Composite orthogonal projection methods for large matrix eigenproblems

For classical orthogonal projection methods for large matrix eigenproblems, it may be much more difficult for a Ritz vector to converge than for its corresponding Ritz value when the matrix in question is non-Hermitian. To this end, a class of new refined orthogonal projection methods has been proposed. It is proved that in some sense each refined method is a composite of two classical orthogonal projections, in which each refined approximate eigenvector is obtained by realizing a new one of some Hermitian semipositive definite matrix onto the same subspace. Apriori error bounds on the refined approximate eigenvector are established in terms of the sine of acute angle of the normalized eigenvector and the subspace involved. It is shown that the sufficient conditions for convergence of the refined vector and that of the Ritz value are the same, so that the refined methods may be much more efficient than the classical ones. Project supported by the China State Major Key Projects for Basic Researches, the National Natural Science Foundation of China (Grant No. 19571014), the Doctoral Program (97014113), the Foundation of Excellent Young Scholors of Ministry of Education, the Foundation of Returned Scholars of China and the Liaoning Province Natural Science Foundation.     

Block rearranging elements within matrix columns to minimize the variability of the row sums

Several problems in operations research, such as the assembly line crew scheduling problem and the k-partitioning problem can be cast as the problem of finding the intra-column rearrangement (permutation) of a matrix such that the row sums show minimum variability. A necessary condition for optimality of the rearranged matrix is that for every block containing one or more columns it must hold that its row sums are oppositely ordered to the row sums of the remaining columns. We propose the block rearrangement algorithm with variance equalization (BRAVE) as a suitable method to achieve this situation. It uses a carefully motivated heuristic—based on an idea of variance equalization—to find optimal blocks of columns and rearranges them. When applied to the number partitioning problem, we show that BRAVE outperforms the well-known greedy algorithm and the Karmarkar–Karp differencing algorithm.