部分逆M矩阵2-弦图的完备问题

本文采用图论的方法对任意阶部分逆M矩阵,当其对应的图为2-弦图时,研究了其逆M矩阵的完备问题。给出了完备定理以及具体完备的算法。     

随机矩阵特征值新盖尔型包含集

随机矩阵及其特征值问题具有广泛的应用背景,计算机辅助几何设计、数理经济学和马尔科夫链等领域都与其有着密切的联系．对随机矩阵特征值问题的研究主要集中在两个方面：在复平面上给出包含随机矩阵所有非1特征值的区域;给出随机矩阵特征值1和非1特征值之间距离的近似值估计．本文对这两方面问题进行了研究,获得了如下结果：通过选择新的参数,获得随机矩阵非1特征值新盖尔型包含区域,改进了近期一些相关成果．并由此得到估计正随机矩阵特征值1与非1特征值距离的新上界算法．最后,数值例子表明算法的优越性．     

友循环矩阵求逆和广义逆的Euclid算法

利用多项式的Euclid算法给出了任意域上非奇异的友循环矩阵求逆矩阵的一个新算法,该算法同时推广到用于求任意域上奇异友循环矩阵的群逆和Moore-Penrose逆,最后给出了应用该算法的数值例子。     

求置换因子循环矩阵的极小多项式和逆的算法

本文引入了任意域上置换因子循环矩阵,利用多项式环的理想的Gr(?)bner基的算法给出了任意域上置换因子循环矩阵的极小多项式和公共极小多项式的算法,同时给出了这类矩阵逆矩阵的两种算法最后,利用Schur补给出了任意域上具有置换因子循环矩阵块的分块矩阵逆的一个算法,在有理数域或模素数剩余类域上,这一算法可由代数系统软件CoCoA4．0实现。     

基于顶点关联索引的最短路径查询算法研究

研究了图查询中的最短路径查询问题,针对现有的查询算法存在构建索引时间长和索引规模庞大所导致的低效性和扩展性问题,在索引构建方面提出了顶点关联索引策略。对度数为1的顶点构建顶点关联索引,对其他顶点构建2-hop标签索引,通过减少冗余数据存储和图的遍历次数,降低索引规模以减少构建索引时间。基于所提出的查询策略,给出了基于顶点关联关系和2-hop标签的最短路径查询算法。     

实方阵的Moore-Penrose广义逆的MCG算法探究

证明了矩阵Moore-Penrose逆的唯一性以及建立了求矩阵Moore-Penrose逆的算法。首先将求矩阵的Moore-Penrose逆转为求解含有三个矩阵变量的矩阵方程组，其次建立求该矩阵方程组的修正共轭梯度算法(MCG算法)，给出了MCG算法的性质和收敛性证明，对于任意给定的初始矩阵该算法能在有限步迭代计算后得到矩阵的Moore-Penrose逆。最后给出数值算例，证明MCG算法在求解矩阵Moore-Penrose逆中具有很高的计算效率。     

双复特征值约束下的逆二次特征值问题

在设计电路和带阻尼弹簧质点系统等实际问题中,求解逆特征值问题是重要的方法.本文研究了如下的电路设计问题,已知电感矩阵M、电阻矩阵C、电容矩阵K的部分信息,寻找未知量的值,使电路系统具有预先给定的频率.我们将该问题转化成了双复特征值约束下的两类逆二次特征值问题,通过求解二次特征行列式方程组,给出了问题有解的存在性条件和解的表达式.文中给出了算法和数值算例,实验结果说明了所得结论的正确性.     

Hankel矩阵及其逆矩阵快速三角分解的新算法

为了降低Hankel矩阵及其逆矩阵三角分解算法的计算量和减小这类算法的误差。本文根据Hankel矩阵的对称结构,通过构造高阶矩阵的方法分别给出了求解这类矩阵及其逆矩阵三角分解的快速算法,与Chun-Kailath算法相比,新算法减少了计算量,并改进了计算精度。     

反自反矩阵的二次特征值反问题及其最佳逼近

二次特征值反问题是二次特征值问题的一个逆过程,在结构动力模型修正领域中应用非常广泛．本文由给定的部分特征值和特征向量,利用矩阵分块法、奇异值分解和Moore-Penrose广义逆,分析了二次特征值反问题反自反解的存在性,得出了解的一般表达式．然后讨论了任意给定矩阵在解集中最佳逼近解的存在性和唯一性．最后给出解的表达式和数值算法,由算例验证了结果的正确性．     

一种Loop细分小波的边界处理方法

细分小波近年来发展迅速,在计算机图形显示、渐进网格传输和网格多分辨率编辑等领域获得了广泛的应用。Bertram提出的Loop细分小波是基于提升格式的双正交细分小波的典型范例,它所针对的对象均为网格的内部顶点。目前尚未发现相关文献提及细分小波对于边界的处理。该文在Loop细分小波算法的基础上,给出了一种Loop细分小波边界处理的方法,经验证效果令人满意。     

Eigensolution of augmented graph products using shifted inverse iteration method

Two important matrices associated with graphs are adjacency and Laplacian matrices. In this paper efficient methods are presented for eigensolution of graph products augmented by other graphs. For augmentations that do not destroy the symmetry of the graph products, a method is proposed for decomposition of matrices resulting in considerable simplification of their eigensolution. For graphs composed of two non‐overlapping graph products joined through a small number of link members, a method based on shifted inverse iteration is proposed which utilizes all eigenvalues and eigenvectors of each individual graph products. Owing to the availability of fast methods for eigensolution of graph products, this method simplifies the eigensolution of a variety of graph models and proves to be very efficient in determining the few smallest eigenpairs of these models with high levels of accuracy. Copyright © 2010 John Wiley & Sons, Ltd.     

Inverse spectral problems for differential pencils on a graph with a rooted cycle

An inverse spectral problem is studied for differential pencils on graphs with a rooted cycle and with standard matching conditions in internal vertices. A uniqueness theorem is proved, and a constructive procedure for the solution is provided.     

Graph coloration and group theory for factorization of symmetric dynamic systems

Summary In this article the concept of graph coloration for factorization of the characteristic polynomial of a weighted directed graph is introduced and using the fundamental lemma of Petersdorf and Sachs, it is shown that this concept can be extended to other spectra of graph among which is the spectrum of the Laplacian matrix of graphs. The goal is to use this concept for factorizing the graphs having different types of symmetry properties. In order to present an efficient algorithm, some concepts from group theory are needed. The combination of group theory and graph coloration provides a powerful method for factorizing various structural matrices, an example of which is the stiffness matrices of mass-spring dynamic systems.     

Green's function formalism extended to systems of applied mechanical differential equations posed on graphs

The Green's function formalism is extended here to multi-point posed boundary-value problems of a special type occurring in some situations in applied mechanics. Problems which reduce to special systems of linear ordinary differential equations are considered. These are formulated on finite weighted graphs in such a way that every equation in the system governs a single unknown function and is defined on a single edge of the graph. The individual equations are put into a system format by means of contact and boundary conditions at the vertices and endpoints of the graph, respectively. Based on such a statement, the notion of the matrix of Green's type is introduced. Two methods are proposed for the analytic construction of such matrices. Illustrative examples from different areas of applied mechanics are presented.     

Block diagonalization of adjacency and Laplacian matrices for graph product; applications in structural mechanics

Eigenvalues and eigenvectors of graphs have many applications in structural mechanics and combinatorial optimization. For a regular space structure, the visualization of its graph model as the product of two simple graphs results in a substantial simplification in the solution of the corresponding eigenproblems. In this paper, the adjacency and Laplacian matrices of four graph products, namely, Cartesian, strong Cartesian, direct and lexicographic products are diagonalized and efficient methods are obtained for calculating their eigenvalues and eigenvectors. An exceptionally efficient method is developed for the eigensolution of the Laplacian matrices of strong Cartesian and direct products. Special attention is paid to the lexicographic product, which is not studied in the past as extensively as the other three graph products. Examples are provided to illustrate some applications of the methods in structural mechanics. Copyright © 2006 John Wiley & Sons, Ltd.     

Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products

Many structural models can be generated as the graph products of two or three subgraphs known as their generators. The main types of graph products consist of Cartesian, strong Cartesian, direct, and lexicographic products. In this paper, a general method is presented for the factorization of these graph products, such that the eigenvalues of the entire graph are obtained as the union of the eigenvalues of the weighted subgraphs defined here. The adjacency and Laplacian matrices for each graph product are studied separately. For graphs with missing elements (cut‐outs), the eigenvalues are calculated with the additional use of the Rayleigh quotient approach. The main idea stems from the rules recently developed by the authors for block diagonalization of matrices. These products have many applications in computational mechanics, such as ordering, graph partitioning, dynamic analysis, and stability analysis of structures. Some of these applications are addressed in this paper. Copyright © 2007 John Wiley & Sons, Ltd.     

A new directed graph approach for automated setup planning in CAPP

The task of setup planning is to determine the number and sequence of setups and the machining features or operations in each setup. Now there are three main methods for setup planning, i.e., the knowledge-based approach, the graph-based approach and the intelligence algorithm-based approach. In the knowledge-based and graph-based approaches reported in the literature, the main problem is that there is no guarantee that all precedence cycles between setups can be avoided during setup formation. The methods to break precedence cycles between setups are to split one setup into smaller setups. However, the implementation of this method is difficult and complex. In the intelligence algorithm-based approach, the method to handle the precedence constraints is a penalty strategy, which does not reflect the influence of precedence constraints on setup plans explicitly. To deal with the above deficiencies, a new directed graph approach is proposed to describe precedence constraints explicitly, which consists of three parts: (1) a setup precedence graph (SPG) to describe precedence constraints between setups. During the generation of the SPG, the minimal number of tolerance violations is guaranteed preferentially by the vertex clusters algorithm for serial vertices and the minimal number of setups is achieved by using variants of the breadth-first search. Precedence cycles between setups are avoided by checking whether two serial vertex clusters can generate a cycle; (2) operation sequencing to minimise tool changes in a setup; and (3) setup sequencing to generate optimal setup plans, which could be implemented by a topological sort. The new directed graph approach will generate many optimal or near-optimal setup plans and provide more flexibility required by different job shops. An example is illustrated to demonstrate the effect of the proposed approach.     

Improved group theoretic method using graph products for the analysis of symmetric-regular structures

In this paper, a new combined graph-group method is proposed for eigensolution of special graphs. Symmetric regular graphs are the subject of this study. Many structural models can be viewed as the product of two or three simple graphs. Such models are called regular, and usually have symmetric configurations. The proposed method of this paper performs the symmetry analysis of the entire structure via symmetric properties of its simple generators. Here, a graph is considered as the general model of an arbitrary structure. The Laplacian matrix, as one of the most important matrices associated with a graph, is studied in this paper. The characteristic problem of this matrix is investigated using symmetry analysis via group theory enriched by graph theory. The method is developed and decomposition of the Laplacian matrix of such graphs is studied in a step-by-step manner, based on the proposed method. This method focuses on simple paths which generate large networks, and finds the eigenvalues of the network via analysis of the simple generators. Group theory is the main tool, which is improved using the concept of graph products. As a mechanical application of the method, a benchmark problem of group theory in structural mechanics is studied in this paper. Vibration of cable nets is analyzed and the frequencies of the networks are calculated using the combined graph-group method.     

Sequences of regressions and their independences

Ordered sequences of univariate or multivariate regressions provide statistical models for analysing data from randomized, possibly sequential interventions, from cohort or multi-wave panel studies, but also from cross-sectional or retrospective studies. Conditional independences are captured by what we name regression graphs, provided the generated distribution shares some properties with a joint Gaussian distribution. Regression graphs extend purely directed, acyclic graphs by two types of undirected graph, one type for components of joint responses and the other for components of the context vector variable. We review the special features and the history of regression graphs, prove criteria for Markov equivalence and discuss the notion of a?simpler statistical covering model. Knowledge of Markov equivalence provides alternative interpretations of a given sequence of regressions, is essential for machine learning strategies and permits to use the simple graphical criteria of regression graphs on graphs for which the corresponding criteria are in general more complex. Under the known conditions that a Markov equivalent directed acyclic graph exists for any given regression graph, we give a polynomial time algorithm to find one such graph.