×
Kaveh, A.; Fazli, H.

Approximate eigensolution of Laplacian matrices for locally modified graph products. (English) Zbl 1234.05153

J. Comput. Appl. Math. 236, No. 6, 1591-1603 (2011).
Summary: Laplacian matrices and their spectrum are of great importance in algebraic graph theory. There exist efficient formulations for eigensolutions of the Laplacian matrices associated with a special class of graphs called product graphs. In this paper, the problem of determining a few approximate smallest eigenvalues and eigenvectors of large scale product graphs modified through the addition or deletion of some nodes and/or members, is investigated. The eigenproblem associated with a modified graph model is reduced using the set of master eigenvectors and linear approximated slave eigenvectors from the original model. Implicitly restarted Lanczos method is employed to obtain the required eigenpairs of the reduced problem. Examples of large scale models are included to demonstrate the efficiency of the proposed method compared to the direct application of the IRL method.

Cited in 3 Documents

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C76 Graph operations (line graphs, products, etc.)
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)

Keywords:

Laplacian matrices; graphs; implicitly restarted Lanczos (IRL) method; eigenvalues; locally modified

Software:

ARPACK; eigs; IRAM
Cite Review PDF
Full Text: DOI

References:

[1] Kaveh, A., (Structural Mechanics: Graph and Matrix Methods, 3rd edition (2004), Research Studies Press, John Wiley: Research Studies Press, John Wiley Somerset, UK) · Zbl 0974.74002
[2] Kaveh, A., Optimal Structural Analysis (2006), John Wiley: John Wiley Chichister, UK · Zbl 0974.74001
[3] Kaveh, A.; Sayarinejad, M. A., Eigensolutions for matrices of special structures, Comm. Numer. Methods Engrg., 19, 125-136 (2003) · Zbl 1013.65030
[4] Imrich, W.; Klavžar, S., Product Graphs; Structure and Recognition (2000), John Wiley: John Wiley NY · Zbl 0963.05002
[5] Kaveh, A.; Rahami, H., Block diagonalization of adjacency and Laplacian matrices for graph products; applications in structural mechanics, Internat. J. Numer. Methods Engrg., 68, 1, 33-63 (2006) · Zbl 1127.74050
[6] Kaveh, A.; Rahami, H., Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products, Internat. J. Numer. Methods Engrg., 75, 1, 58-82 (2008) · Zbl 1195.74073
[7] Kaveh, A.; Rahami, H., Eigenvalues of the adjacency and Laplacian matrices for modified regular structural models, Internat. J. Numer. Methods Biomed. Engrg., 26, 1836-1855 (2010) · Zbl 1207.05119
[8] Kaveh, A.; Fazli, H., Eigensolution of augmented graph products using shifted inverse iteration method, Internat. J. Numer. Methods Engrg., 83, 5, 558-574 (2010) · Zbl 1197.05089
[9] Bendiksen, O. O., Mode localization phenomena in large space structures, AIAA J., 25, 1241-1248 (1987)
[10] Wang, B. P.; Pilkey, W. D., Eigenvalue reanalysis of locally modified structures using a generalized Rayleigh’s method, AIAA J., 24, 6, 983-990 (1986) · Zbl 0596.70021
[11] Golub, G. H., Some modified matrix eigenvalue problems, SIAM Rev., 15, 318-334 (1973) · Zbl 0254.65027
[12] Bunch, J. R.; Nielsen, C. P.; Sorensen, D., Rank-one modification of the symmetric eigenproblem, Numer. Math., 31, 31-48 (1978) · Zbl 0369.65007
[13] Arbenz, P.; Golub, G. H., On the spectral decomposition of Hermitian matrices modified by low rank perturbations with applications, SIAM J. Matrix Anal. Appl., 9, 40-58 (1988) · Zbl 0646.65033
[14] Arbenz, P.; Gander, W.; Golub, G. H., Restricted rank modification of the symmetric eigenvalue problem: theoretical considerations, Linear Algebra Appl., 104, 75-95 (1988) · Zbl 0652.15004
[15] Carey, M. M.; Golub, G. H.; Law, K. H., A Lanczos-based method for structural dynamic reanalysis problems, Internat. J. Numer. Methods Engrg., 7, 16, 2857-2883 (1994) · Zbl 0812.73074
[16] Lui, S. H., Domain decomposition methods for eigenvalue problems, J. Comput. Appl. Math., 117, 1, 17-34 (2000) · Zbl 0952.65085
[17] G. Kron, Diakoptics, piecewise solution of large-scale systems; a series of chapters in the Elect. J. (London), June 1957-February, 1959.; G. Kron, Diakoptics, piecewise solution of large-scale systems; a series of chapters in the Elect. J. (London), June 1957-February, 1959.
[18] Lui, S. H., Kron’s method for symmetric eigenvalue problems, J. Comput. Appl. Math., 98, 1, 35-48 (1988) · Zbl 0934.65046
[19] Hurty, W. C., Dynamic analysis of structural systems using component modes, AIAA J., 3, 678-685 (1965)
[20] Craig, R. J.; Bampton, M., Coupling of substructures for dynamic analyses, AIAA J., 6, 7, 1313-1319 (1968) · Zbl 0159.56202
[21] MacNeal, R. H., A hybrid method of component mode synthesis, Comput. Struct., 1, 4, 581-601 (1971)
[22] Bennighof, J. K., Component mode iteration for frequency calculations, AIAA J., 25, 996-1002 (1987) · Zbl 0621.73059
[23] Rixen, D. J., A dual Craig-Bampton method for dynamic substructuring, J. Comput. Appl. Math., 168, 1-2, 383-391 (2004) · Zbl 1107.70303
[24] Sehmi, N. S., The Lanczos algorithm applied to Kron’s method, Internat. J. Numer. Methods Engrg., 23, 1857-1872 (1986) · Zbl 0597.65024
[25] Weng, S.; Xia, Y.; Xu, Y. L.; Zhou, X. Q.; Zhu, H. P., Improved substructuring method for eigensolutions of large-scale structures, J. Sound Vib., 3, 23, 718-736 (2009)
[26] Calvetti, D.; Reichel, L.; Sorensen, D. C., An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Elect. Trans. Numer. Anal., 2, 1-21 (1994) · Zbl 0809.65030
[27] Sorensen, D. C., Implicit application of polynomial filters in a \(k\)-step Arnoldi method, SIAM J. Matrix Anal. App., 13, 357-385 (1992) · Zbl 0763.65025
[28] Lehoucq, R. B.; Sorensen, D. C.; Yang, C., ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (1998), SIAM · Zbl 0901.65021
[29] Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Halstead Press: Halstead Press New York · Zbl 0991.65039
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.