Eigensolution of augmented graph products using shifted inverse iteration method
Ali Kaveh, H. Fazli · International Journal for Numerical Methods in Engineering · 2010
Abstract 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.