On some properties of the Laplacian matrix revealed by the RCM algorithm
| Autor: | Pedroche Sánchez, Francisco, Rebollo Pedruelo, Miguel, Carrascosa Casamayor, Carlos, Palomares Chust, Alberto |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Degree matrix
General Mathematics MathematicsofComputing_NUMERICALANALYSIS 0211 other engineering and technologies 010103 numerical & computational mathematics 02 engineering and technology Topology Reverse Cuthill-McKee algorithm 01 natural sciences Cuthill–McKee algorithm Adjacency matrix 0101 mathematics Eigenvalues and eigenvectors Mathematics Connected component Ordering algorithm Graph partitioning Graph partition 021107 urban & regional planning Spectral clustering Laplacian matrix MATEMATICA APLICADA Algorithm LENGUAJES Y SISTEMAS INFORMATICOS |
| Zdroj: | RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia instname |
| Popis: | In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function “symrcm” of MATLAB. Some examples illustrate the theoretical results. The research has been supported by Spanish DGI grant MTM2010-18674, Consolider Ingenio CSD2007-00022, PROMETEO 2008/051, OVAMAH TIN2009-13839-C03-01, and PAID-06-11-2084. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|