Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products. (English) Zbl 1195.74073
Summary: 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.
MSC:
| 74H45 | Vibrations in dynamical problems in solid mechanics |
| 74S30 | Other numerical methods in solid mechanics (MSC2010) |
| 05C90 | Applications of graph theory |
Keywords:
adjacency; Laplacian; Cartesian product; strong Cartesian product; direct product; lexi-cographic product; factorization; irregular graphsReferences:
| [1] | Kaveh, Structural Mechanics: Graph and Matrix Methods (2004) |
| [2] | Kaveh, Optimal Structural Analysis (2006) · doi:10.1002/9780470033326 |
| [3] | Biggs, Algebraic Graph Theory (1993) · Zbl 0284.05101 |
| [4] | Cvetković, Spectra of Graphs, Theory and Applications (1980) |
| [5] | Godsil, Algebraic Graph Theory (2001) · doi:10.1007/978-1-4613-0163-9 |
| [6] | Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal 23 pp 298– (1973) · Zbl 0265.05119 |
| [7] | Mohar, Graph Theory, Combinatorics and Applications 2 pp 871– (1991) |
| [8] | Pothen, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications 11 pp 430– (1990) · Zbl 0711.65034 |
| [9] | Topping BHV, Sziveri J. Parallel subdomain generation method. Proceedings of Civil-Comp, Edinburgh, U.K., 1995. |
| [10] | Kaveh, Compound matrix block diagonalization for efficient solution of eigenproblems in structural mechanics, Acta Mechanica 188 (3–4) pp 155– (2007) · Zbl 1107.74024 |
| [11] | Kaveh, A new spectral method for nodal ordering of regular space structures, Finite Elements in Analysis and Design 40 (13–14) pp 1931– (2004) |
| [12] | Kaveh, An efficient method for decomposition of regular structures using graph products, International Journal for Numerical Methods in Engineering 61 pp 1797– (2004) · Zbl 1075.74539 |
| [13] | Grimes, A new algorithm for finding a pseudo-peripheral node in a graph, SIAM Journal of Analysis and Applications 11 pp 323– (1990) |
| [14] | Kaveh, Algebraic and topological graph theory for ordering, Zeitschrift für Angewandte Mathematik und Mechanik 71 pp T739– (1991) |
| [15] | Paulino, Node sand element resequencing using Laplacian of a finite element graph, Part-I–general concepts and algorithms, International Journal for Numerical Methods in Engineering 37 pp 1511– (1994) |
| [16] | Simon, Partitioning of unstructured problems for parallel processing, Computing in System Engineering 2 pp 135– (1991) |
| [17] | Seale C, Topping BHV. Parallel implementation of recursive spectral bisection. Proceedings of Civil Comp 95, Edinburgh, U.K., 1995; 459–473. |
| [18] | Kaveh, Spectral bisection of adaptive finite element meshes for parallel processing, Computers and Structures 70 pp 315– (1999) · Zbl 0969.74594 |
| [19] | Kaveh, Spectral trisection of finite element models, International Journal of Numerical Methods for Heat and Fluid Flow 11 pp 358– (2001) · Zbl 0977.74060 |
| [20] | Kaveh, A multi-level finite element nodal ordering using algebraic graph theory, Finite Elements in Analysis and Design 38 pp 245– (2002) |
| [21] | Sabidussi, Graph multiplication, Mathematische Zeitschrift 72 pp 446– (1960) · Zbl 0093.37603 |
| [22] | Weichsel, The Kronecker product of graphs, Proceedings of the American Mathematical Society 13 pp 47– (1962) · Zbl 0102.38801 |
| [23] | Harary, Boolean operations on graphs, Mathematica Scandinavica 20 pp 41– (1967) · Zbl 0152.22801 · doi:10.7146/math.scand.a-10817 |
| [24] | Reif, An Efficient Algorithm for the Real Root and Symmetric Tridiagonal Eigenvalue Problems (1999) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
