Canonical Forms for Combinatorial Optimisation, Nodal Ordering and Graph Partitioning
Ordering is an important issue in the analysis of large-scale structures. In the standard approach depending on the solution scheme, the bandwidth, profile or front width of the structural matrices should be optimised. For parallel computing, the model of
- PDF / 2,630,315 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 209 Views
Canonical Forms for Combinatorial Optimisation, Nodal Ordering and Graph Partitioning
5.1
Introduction
Ordering is an important issue in the analysis of large-scale structures. In the standard approach depending on the solution scheme, the bandwidth, profile or front width of the structural matrices should be optimised. For parallel computing, the model of the structure (domain) should be partitioned (decomposed) into a number of substructures (subdomain) having certain properties. The latter can also be considered as an ordering problem. There are many applications of algebraic graph theory in nodal and element ordering and graph partitioning. However, despite of the efficiency of graph spectra for combinatorial optimisation, the calculation of eigenvalues and eigenvectors of large graphs and their corresponding structural models without considering patterns and the sparsity of their matrices requires additional memory and computational time. There are numerous applications of graph theory and algebraic graph theory in optimal structural analysis, Kaveh [1, 2]. In this chapter, a canonical form as well as its relation with four structural models often encountered in practice and their corresponding graphs are presented, Kaveh and Koohestani [3]. Furthermore, the block diagonalisation of this form, which is performed using three Kronecker products and unsymmetric matrices, is studied. This block diagonalisation leads to an efficient method for the eigensolution of adjacency and Laplacian matrices of special graphs. The eigenvalues and eigenvectors are used for efficient nodal ordering and partitioning of large structural models.
5.2
Preliminary Definitions
Consider the solution of sparse linear system of equations Ax ¼ b;
(5.1)
where the n n matrix A is a sum of elemental matrices. A. Kaveh, Optimal Analysis of Structures by Concepts of Symmetry and Regularity, DOI 10.1007/978-3-7091-1565-7_5, © Springer-Verlag Wien 2013
115
116
5 Canonical Forms for Combinatorial Optimisation, Nodal Ordering and Graph. . .
The bandwidth of the matrix A is defined as B ¼ maxfbi g;
(5.2)
bi ¼ maxfi j þ 1g with aij 6¼ 0
(5.3)
where
The profile of the matrix A is the total number of coefficients in the lower triangle when any zero ahead of the first entry in its row is excluded. That is, P¼
n X
maxfbi g:
(5.4)
i¼1
Note that since A is assumed to have a symmetric pattern of non-zeros, it follows that P¼
n X
fi:
(5.5)
i¼1
5.3
Algebraic Graph Theory for Ordering and Partitioning
Algebraic graph theory can be considered as a branch of mathematics that connects the algebra and theory of graph. In this theory, eigenvalues and eigenvectors of certain matrices are employed to deduce the principal properties of a graph. In fact eigenvalues are closely related to most of the invariants of a graph, linking one extremal property to another. These eigenvalues play a central role in our fundamental understanding of graphs. There are interesting books on algebraic graph theory such as Biggs [4], Cvetkovic´ et al. [5
Data Loading...
