On some properties of the Laplacian matrix revealed by the RCM algorithm

Francisco Pedroche; Miguel Rebollo; Carlos Carrascosa; Alberto Palomares

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 603-620
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Pedroche, Francisco, et al. "On some properties of the Laplacian matrix revealed by the RCM algorithm." Czechoslovak Mathematical Journal 66.3 (2016): 603-620. <http://eudml.org/doc/286796>.

@article{Pedroche2016,
abstract = {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.},
author = {Pedroche, Francisco, Rebollo, Miguel, Carrascosa, Carlos, Palomares, Alberto},
journal = {Czechoslovak Mathematical Journal},
keywords = {ordering algorithm; reverse Cuthill-McKee algorithm; graph partitioning; Laplacian matrix},
language = {eng},
number = {3},
pages = {603-620},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On some properties of the Laplacian matrix revealed by the RCM algorithm},
url = {http://eudml.org/doc/286796},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Pedroche, Francisco
AU - Rebollo, Miguel
AU - Carrascosa, Carlos
AU - Palomares, Alberto
TI - On some properties of the Laplacian matrix revealed by the RCM algorithm
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 603
EP - 620
AB - 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.
LA - eng
KW - ordering algorithm; reverse Cuthill-McKee algorithm; graph partitioning; Laplacian matrix
UR - http://eudml.org/doc/286796
ER -

References

top
  1. Benzi, M., Szyld, D. B., Duin, A. C. N. van, 10.1137/S1064827597326845, SIAM J. Sci. Comput. 20 (1999), 1652-1670. (1999) MR1694677DOI10.1137/S1064827597326845
  2. Boley, D., Ranjan, G., Zhang, Z.-L., Commute times for a directed graph using an asymmetric Laplacian, Linear Algebra Appl. 435 (2011), 224-242. (2011) Zbl1226.05125MR2782776
  3. Bolten, M., Friedhoff, S., Frommer, A., Heming, M., Kahl, K., Algebraic multigrid methods for Laplacians of graphs, Linear Algebra Appl. 434 (2011), 2225-2243. (2011) Zbl1217.65063MR2776793
  4. Cuthill, E., McKee, J., 10.1145/800195.805928, Proc. 24th Nat. Conf. of the ACM, ACM Publ P-69, Association for Computing Machinery, New York, 1969 157-172 doi:10.1145/800195.805928. DOI10.1145/800195.805928
  5. Abreu, N. M. M. de, 10.1016/j.laa.2006.08.017, Linear Algebra Appl. 423, (2007), 53-73. (2007) Zbl1115.05056MR2312323DOI10.1016/j.laa.2006.08.017
  6. Corso, G. M. Del, Romani, F., 10.1023/A:1014082430392, Numer. Algorithms 28 (2001), 117-136. (2001) MR1887751DOI10.1023/A:1014082430392
  7. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  8. Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321
  9. Fortunato, S., 10.1016/j.physrep.2009.11.002, Phys. Rep. 486 (2010), 75-174. (2010) MR2580414DOI10.1016/j.physrep.2009.11.002
  10. George, J. A., Computer Implementation of the Finite Element Method, Doctoral Dissertation, Stanford University, Stanford (1971). (1971) 
  11. George, A., Liu, J. W.-H., Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall Series in Computational Mathematics Prentice-Hall, Englewood Cliffs (1981). (1981) Zbl0516.65010MR0646786
  12. Gilbert, J. R., Moler, C., Schreiber, R., 10.1137/0613024, SIAM J. Matrix Anal. Appl. 13 (1992), 333-356. (1992) Zbl0752.65037MR1146669DOI10.1137/0613024
  13. Gross, J. L., Yellen, J., eds., Handbook of Graph Theory, Discrete Mathematics and Its Applications CRC Press, Boca Raton (2004). (2004) MR2035186
  14. Horn, R. A., Johnson, C. R., Matrix Analysis, Cambridge University Press, Cambridge (1985). (1985) Zbl0576.15001MR0832183
  15. Jungnickel, D., 10.1007/978-3-540-72780-4_11, Algorithms and Computation in Mathematics 5 Springer, Berlin (2008). (2008) Zbl1126.68058MR2363884DOI10.1007/978-3-540-72780-4_11
  16. Juvan, M., Mohar, B., 10.1002/jgt.3190170313, J. Graph Theory, 17 (1993), 393-407. (1993) Zbl0785.05077MR1220999DOI10.1002/jgt.3190170313
  17. Kumfert, G., Pothen, A., 10.1007/BF02510240, BIT 37 (1997), 559-590. (1997) Zbl0891.65043MR1483674DOI10.1007/BF02510240
  18. Liu, W-H., Sherman, A. H., 10.1137/0713020, SIAM J. Numer. Anal. 13 (1976), 198-213. (1976) MR0501813DOI10.1137/0713020
  19. Mohar, B., The Laplacian spectrum of graphs, Graph theory, Combinatorics, and Applications Vol. 2. Proc. Sixth Quadrennial International Conf. on the Theory and Applications of Graphs, Kalamazoo, Michigan, 1988 Y. Alavi et all John Wiley & Sons, New York (1991), 871-898. (1991) Zbl0840.05059MR1170831
  20. Molitierno, J. J., The spectral radius of submatrices of Laplacian matrices for graphs with cut vertices, Linear Algebra Appl. 428 (2008), 1987-1999. (2008) Zbl1137.05045MR2401634
  21. Mueller, C., Martin, B., Lumsdaine, A., 10.1109/APVIS.2007.329289, Visualization Asia-Pacific Symposium on Visualization 2007, Sydney, Australia (2007), 141-148 doi: 10.1109/APVIS.2007.329289. (2007) DOI10.1109/APVIS.2007.329289
  22. Nascimento, M. C. V., Carvalho, A. De, 10.1016/j.ejor.2010.08.012, Eur. J. Oper. Res. 211 (2011), 221-231. (2011) MR2774401DOI10.1016/j.ejor.2010.08.012
  23. Newman, M. E. J., 10.1093/acprof:oso/9780199206650.003.0001, Oxford University Press, Oxford (2010). (2010) Zbl1195.94003MR2676073DOI10.1093/acprof:oso/9780199206650.003.0001
  24. Pothen, A., Simon, H. D., Liou, K. P., 10.1137/0611030, SIAM J. Matrix Anal. Appl. 11 (1990), 430-452. (1990) MR1054210DOI10.1137/0611030
  25. Rebollo, M., Carrascosa, C., Palomares, A., Pedroche, F., Some examples of detection of connected components in undirected graphs by using the Laplacian matrix and the RCM algorithm, Int. J. Complex Systems in Science 2 (2012), 11-15. (2012) 
  26. Reid, J. K., Scott, J.A., 10.1137/050629938, Siam J. Matrix Anal. Appl. 28 (2006), 805-821. (2006) Zbl1123.65027MR2262982DOI10.1137/050629938
  27. Saad, Y., Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics Philadelphia (2003). (2003) Zbl1031.65046MR1990645
  28. Schaeffer, S. E., 10.1016/j.cosrev.2007.05.001, Comput. Sci. Rev. 1 (2007), 27-64. (2007) Zbl1302.68237DOI10.1016/j.cosrev.2007.05.001
  29. Tarjan, R., 10.1137/0201010, SIAM J. Comput. 1 (1972), 146-160. (1972) Zbl0251.05107MR0304178DOI10.1137/0201010
  30. Varga, R. S., 10.1007/978-3-642-05156-2, Springer Series in Computational Mathematics 27 Springer, Berlin (2000). (2000) Zbl0998.65505MR1753713DOI10.1007/978-3-642-05156-2

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.