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.     

On some properties of the Laplacian matrix revealed by the RCM algorithm

In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function “symrcm” of MATLAB. Some examples illustrate the theoretical results.     

Maximal independent sets on a grid graph

An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics.     

A general finite element preconditioning for the conjugate gradient method

Discretizing a symmetric elliptic boundary value problem by a finite element method results in a system of linear equations with a symmetric positive definite coefficient matrix. This system can be solved iteratively by a preconditioned conjugate gradient method. In this paper a preconditioning matrix is proposed that can be constructed for all finite element methods if a mild condition for the node numbering is fulfilled. Such a numbering can be constructed using a variant of the reverse Cuthill-McKee algorithm.     

周期三对角矩阵逆的一种新算法

给出了一类周期三对角矩阵逆的新的递归算法.新方法充分利用周期三对角矩阵的结构特点,采用递归方法将高阶周期三对角矩阵求逆转化为低阶周期三对角矩阵的求逆.并同时得到简化的计算方法,方法可以有效地减少运算量和存储量,计算精度也有明显的优势.数值实验表明此算法是有效的.     

并行准高斯高阶递归滤波算法研究

三维变分同化系统中一个重要的问题是背景误差协方差矩阵B及其逆的求解.背景误差协方差矩阵的水平变换部分采用递归滤波运算,可以简化矩阵的求解,解决了背景误差协方差矩阵B及其逆难以求解的问题.本文对准高斯高阶递归滤波的算法原理和过程进行了深入研究.因为递归滤波并行的低可扩展性制约了高阶递归滤波算法在三维变分同化系统中的应用,所以本文提出了阶段二维区域剖分并行化方法,实现了并行准高斯高阶递归滤波算法库.数值试验表明,四阶递归滤波1次的效果明显优于一阶4次的滤波效果;并且高阶递归滤波并行算法64核时能达到大约50倍的加速,并行效率高达78%,具有良好的加速效果和较强的可扩展性.     

A new algorithm for computing the inverse and the determinant of a Hessenberg matrix

In this paper, a new recursive symbolic computational Hessenberg matrix algorithm is presented to compute the inverse and the determinant of a Hessenberg matrix.     

A recursive algorithm for constructing complicated Dixon matrices

Whether the determinant of the Dixon matrix equals zero or not is used for determining if a system of n + 1 polynomial equations in n variables has a common root, and is a very efficient quantifier elimination approach too. But for a complicated polynomial system, it is not easy to construct the Dixon matrix. In this paper, a recursive algorithm to construct the Dixon matrix is proposed by which some problems that cannot be tackled by other methods can be solved on the same computer platform. A dynamic programming algorithm based on the recursive formula is developed and compared for speed and efficiency to the recursive algorithm.     

Trees with very few eigenvalues

The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance-transitive and distance-regular graphs. Here we provide a recursive construction that will create graphs having the fewest possible eigenvalues. This construction is best at creating trees, but will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large amounts of symmetry. A corollary allows us to determine the values and multiplicities of all the nonsimple eigenvalues of the constructed graph.     

Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

We generalize the linear-time shortest-paths algorithm for planar graphs with nonnegative edge-weights of Henzinger et al. (1994) to work for any proper minor-closed class of graphs. We argue that their algorithm can not be adapted by standard methods to all proper minor-closed classes. By using recent deep results in graph minor theory, we show how to construct an appropriate recursive division in linear time for any graph excluding a fixed minor and how to transform the graph and its division afterwards, so that it has maximum degree three. Based on such a division, the original framework of Henzinger et al. can be applied. Afterwards, we show that using this algorithm, one can implement Mehlhorn’s (1988) 2-approximation algorithm for the Steiner tree problem in linear time on these graph classes.     

High‐performance direct algorithms for computing the sign function of triangular matrices

Algorithms and implementations for computing the sign function of a triangular matrix are fundamental building blocks for computing the sign of arbitrary square real or complex matrices. We present novel recursive and cache‐efficient algorithms that are based on Higham's stabilized specialization of Parlett's substitution algorithm for computing the sign of a triangular matrix. We show that the new recursive algorithms are asymptotically optimal in terms of the number of cache misses that they generate. One algorithm that we present performs more arithmetic than the nonrecursive version, but this allows it to benefit from calling highly optimized matrix multiplication routines; the other performs the same number of operations as the nonrecursive version, suing custom computational kernels instead. We present implementations of both, as well as a cache‐efficient implementation of a block version of Parlett's algorithm. Our experiments demonstrate that the blocked and recursive versions are much faster than the previous algorithms and that the inertia strongly influences their relative performance, as predicted by our analysis.     

A linear 5-coloring algorithm of planar graphs

A simple linear algorithm is presented for coloring planar graphs with at most five colors. The algorithm employs a recursive reduction of a graph involving the deletion of a vertex of degree 6 or less possibly together with the identification of its several neighbors.     

RECURSIVE FORMULA FOR CALCULATING THE CHROMATIC POLYNOMIAL OF A GRAPH BY VERTEX DELETION

A new recursive vertex-deleting formula for the computation of the chromatic polynomial of a graph is obtained in this paper. This algorithm is not only a good tool for further studying chromatic polynomials but also the fastest among all the algorithms for the computation of chromatic polynomials.     

关于可达矩阵的求法探讨

在《离散数学》、《图论》课程中 ,用矩阵表示图时 ,涉及到一类重要的矩阵——可达矩阵 ,它是判别图中任意两点是否有通路的重要手段 ,也是求强分图的重要方法 ,但是可达矩阵的求法比较复杂 .本文针对这一问题 ,对可达矩阵的求法进行了改进 ,提出了一种简单可行的算法 .     

基于主成份分析的递推子空间辨识

研究了多输入多输出系统的状态空间模型的递推子空间辨识问题.针对只有输出量测噪声的线性时不变系统,提出了基于随机逼近-主成份分析(SA-PCA)的估计扩张能观矩阵的递推算法.同时利用递推最小二乘在线估计系统矩阵.最后通过仿真例子说明算法的收敛速度和估计效果.     

The inertia of unicyclic graphs and the implications for closed-shells

The inertia of a graph is an integer triple specifying the number of negative, zero, and positive eigenvalues of the adjacency matrix of the graph. A unicyclic graph is a simple connected graph with an equal number of vertices and edges. This paper characterizes the inertia of a unicyclic graph in terms of maximum matchings and gives a linear-time algorithm for computing it. Chemists are interested in whether the molecular graph of an unsaturated hydrocarbon is (properly) closed-shell, having exactly half of its eigenvalues greater than zero, because this designates a stable electron configuration. The inertia determines whether a graph is closed-shell, and hence the reported result gives a linear-time algorithm for determining this for unicyclic graphs.     

Fourier expansion based recursive algorithms for periodic Riccati and Lyapunov matrix differential equations

Combining Fourier series expansion with recursive matrix formulas, new reliable algorithms to compute the periodic, non-negative, definite stabilizing solutions of the periodic Riccati and Lyapunov matrix differential equations are proposed in this paper. First, periodic coefficients are expanded in terms of Fourier series to solve the time-varying periodic Riccati differential equation, and the state transition matrix of the associated Hamiltonian system is evaluated precisely with sine and cosine series. By introducing the Riccati transformation method, recursive matrix formulas are derived to solve the periodic Riccati differential equation, which is composed of four blocks of the state transition matrix. Second, two numerical sub-methods for solving Lyapunov differential equations with time-varying periodic coefficients are proposed, both based on Fourier series expansion and the recursive matrix formulas. The former algorithm is a dimension expanding method, and the latter one uses the solutions of the homogeneous periodic Riccati differential equations. Finally, the efficiency and reliability of the proposed algorithms are demonstrated by four numerical examples.     

图的可达性矩阵的一种新求法

图的可达性矩阵在判断图的强连通性以及求强连通分图中具有重要作用.根据传统求解图的可达性矩阵的特点,在定义链长的基础上,寻求了一种新的计算方法,采用逐次求平方的方法进一步降低计算量.     

Marking algorithms

Algorithms for traversing and marking the nodes of a directed graph have applications in many fields, for instance search methods in artificial intelligence and garbage collection schemes. In this paper, a general nonrecursive algorithm for the purpose is formulated and proved, and some if its properties are investigated. A second general nonrecursive algorithm is also discussed. Then two implementations of the general algorithms with valuable properties are described. Finally a recursive version is given.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.