Abstract
We are mainly concerned with sequences of graphs having a grid geometry, with a uniform local structure in a bounded domain \({\Omega} {\subset} \mathbb{R}^{d}, d \geq 1\). When \(\Omega = [0, 1]\), such graphs include the standard Toeplitz graphs and, for \(\Omega = [0, 1]^{d}\), the considered class includes d-level Toeplitz graphs. In the general case, the underlying sequence of adjacency matrices has a canonical eigenvalue distribution, in the Weyl sense, and we show that we can associate to it a symbol \(\mathfrak{f}\). The knowledge of the symbol and of its basic analytical features provides many information on the eigenvalue structure, of localization, spectral gap, clustering, and distribution type.
Few generalizations are also considered in connection with the notion of generalized locally Toeplitz sequences and applications are discussed, stemming e.g. from the approximation of differential operators via numerical schemes. Nevertheless, more applications can be taken into account, since the results presented here can be applied as well to study the spectral properties of adjacency matrices and Laplacian operators of general large graphs and networks.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Change history
03 February 2024
Reference 1 was published incorrectly and corrected in this version.
References
A. Adriani, D. Bianchi, P. Ferrari, S. Serra-Capizzano, M. Usman, Asymptotic spectra of large (Grid) graphs with a uniform local structure, part II: numerical applications. J. Comput. Appl. Math. 437, 115461 (2024). https://doi.org/10.1016/j.cam.2023.115461
D. Bianchi, Analysis of the spectral symbol associated to discretization schemes of linear self-adjoint differential operators, submitted (2020): arXiv:2004.10058
D. Bianchi, S. Serra-Capizzano, Spectral analysis of finite-dimensional approximations of 1d waves in non-uniform grids, Calcolo 55 (2018), paper no. 47, 28pp
Bhatia, R.: Matrix Analysis. Springer-Verlag, New York (1997)
Böttcher, A., Silbermann, B.: Introduction to Large Truncated Toeplitz Matrices. Springer-Verlag, New York (1999)
Brouwe, A.E., Haemers, W.H.: Spectra of graphs. Springer Science & Business Media, New York (2011)
Bu, J., Chen, C., Wang, C., Wang, X., Wu, Y., Yu, Z.: Friend recommendation with content spread enhancement in social networks. Inf. Sci. 309, 102–118 (2015)
Burago, D., Ivanov, S., Kurylev, Y.: A graph discretization of the Laplace-Beltrami operator. J. Spectr. Theor. 4(4), 675–715 (2014)
Chung, K.L.: A course in probability theory. Academic Press, Cambridge (2001)
Ciarlet, P.: The Finite Element Method for Elliptic Problems. North Holland, Amsterdam (1978)
Cottrell, J.A., Hughes, T.J.R., Bazilevs, Y.: Isogeometric analysis: toward integration of CAD and FEA. John Wiley & Sons, Hoboken (2009)
Cvetkovic, D., Doob, M., Sachs, H.: Spectra of Graphs. Academic Press, New York (1979)
E.B. Davies, Spectral theory and differential operators, Cambridge University Press, 1996.
Di Benedetto, F., Fiorentino, G., Serra-Capizzano, S.: CG preconditioning for Toeplitz matrices. Comput. Math. with Appl. 25(6), 35–45 (1993)
Eichinger, B.E.: An approach to distribution functions for Gaussian molecules. Macromolecules 10(3), 671–675 (1977)
Estrada, E.: Path Laplacian matrices: Introduction and application to the analysis of consensus in networks. Linear Algebra Appl. 436(9), 3373–3391 (2012)
Estrada, E., Hameed, E., Hatano, N., Langer, M.: Path Laplacian operators and superdiffusive processes on graphs, I. One-dimensional case, Linear Algebra Appl. 523, 307–334 (2017)
Estrada, E., Hameed, E., Langer, M., Puchalska, A.: Path Laplacian operators and superdiffusive processes on graphs, II. Two-dimensional lattice, Linear Algebra Appl. 555(2018), 373–397 (2018)
Fax, J.A., Murray, R.M., Olfati-Saber, R.: Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95(1), 215–233 (2007)
Fiedler, M.: Algebraic connectivity of graphs. Czechoslov. Math. J. 23(2), 298–305 (1973)
Galina, H., Syslo, M.: Some applications of graph theory to the study of polymer configuration. Discret. Appl. Math. 19, 167–176 (1988)
C. Garoni, M. Mazza, S. Serra-Capizzano, Block generalized locally Toeplitz sequences: from the theory to the applications, Axioms 7 no. 3 (2018), paper no. 49
Garoni, C., Serra-Capizzano, S.: The theory of Generalized Locally Toeplitz sequences: theory and applications, vol. I. Springer Monographs in Mathematics, Springer, New York (2017)
Garoni, C., Serra-Capizzano, S.: The theory of multilevel Generalized Locally Toeplitz sequences: theory and applications, vol. II. Springer Monographs in Mathematics, Springer, New York (2018)
Garoni, C., Serra-Capizzano, S., Sesana, D.: Spectral analysis and spectral symbol of d-variate \(\mathbb{Q}_{p}\) Lagrangian FEM stiffness matrices. SIAM J. Matrix Anal. Appl. 36(3), 1100–1128 (2015)
C. Garoni, S. Serra-Capizzano, D. Sesana, The Theory of Block Generalized Locally Toeplitz Sequences, Technical Report, no. 1, January 2018, Department of Information Technology, Uppsala University, http://www.it.uu.se/research/publications/reports/2018-001/
C. Garoni, H. Speleers, S.-E. Ekstrøm, A. Reali, S. Serra-Capizzano, T.J.- R. Hughes, Symbol-based analysis of finite element and isogeometric B-spline discretizations of eigenvalue problems: Exposition and review, Arch. Comput. Methods Eng. 26 (2019), 1639–1690
S. Hossein Ghorban, Toeplitz graph decomposition, Trans. Combinat. 1 no. 4 (2012), 35–41
Grenander, U., Szegő, G.: Toeplitz Forms and Their Applications, 2nd edn. Chelsea, New York (1984)
Kac, M., Murdoch, W.L., Szegő, G.: On the eigenvalues of certain Hermitian forms. J. Rational Mech. Anal. 2, 767–800 (1953)
Kato, T.: Perturbation theory for linear operators, 2nd edn. Springer, Heidelberg (1980)
Kawohl, B.: Rearrangements and convexity of level sets in PDE. Springer, Heidelberg (1985)
Keller, M., Lenz, D.: Dirichlet forms and stochastic completeness of graphs and subgraphs. J. Reine Angew. Math. 666, 189–223 (2012)
Maas, C.: Transportation in graphs and the admittance spectrum. Discret. Appl. Math. 16(1), 31–49 (1987)
Mohar, B., Alavi, Y., Chartrand, G., Oellermann, O.R.: The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications 2(12), 871–898 (1991)
Serra-Capizzano, S.: Asymptotic results on the spectra of block Toeplitz preconditioned matrices. SIAM J. Matrix Anal. Appl. 20(1), 31–44 (1998)
Serra-Capizzano, S.: Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations. Linear Algebra Appl. 366, 371–402 (2003)
Serra-Capizzano, S.: The GLT class as a generalized Fourier analysis and applications. Linear Algebra Appl. 419(1), 180–233 (2006)
Strikwerda, J.C.: Finite Difference Schemes and Partial Differential Equations, Chapman and Hall. International Thompson Publ, New York (1989)
G. Talenti, Rearrangements of functions and partial differential equations, in: Nonlinear Diffusion Problems, Springer, Berlin, Heidelberg, 1986, pp. 153–178
Tilli, P.: Locally Toeplitz matrices: spectral theory and applications. Linear Algebra Appl. 278, 91–120 (1998)
Tilli, P.: A note on the spectral distribution of Toeplitz matrices. Linear Multilinear Algebra 45, 147–159 (1998)
N. G. Trillos, M. Gerlach, M. Hein, D. Slepčev, Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–Beltrami operator, Found. Computh. Math. (2019), DOI: https://doi.org/10.1007/s10208-019-09436-w
Trillos, N.G., Sanz-Alonso, D.: Continuum limits of posteriors in graph Bayesian inverse problems. SIAM J. Math. Anal. 50(4), 4020–4040 (2018)
N. G. Trillos, D. Sanz-Alonso, R. Yang, Local Regularization of Noisy Point Clouds: Improved Global Geometric Estimates and Data Analysis, J. Mach. Learn. Res. 20 (2019), paper no. 136, 37pp
Tyrtyshnikov, E., Zamarashkin, N.: Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships. Linear Algebra Appl. 270, 15–27 (1998)
Acknowledgements
We thank the Editors and the anonymous referees for their careful reading and for their pertinent suggestions that helped us to improve the quality of the paper. We also thank INdAM - GNCS for the support in conducting our researches.
Funding
Open access funding provided by Università degli Studi dell’Insubria within the CRUI-CARE Agreement.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The authors are supported by INdAM-GNCS Gruppo Nazionale per il Calcolo Scientifico.
Reference 1 was published incorrectly and corrected in this version.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Adriani, A., Bianchi, D. & Serra-Capizzano, S. Asymptotic Spectra of Large (Grid) Graphs with a Uniform Local Structure (Part I): Theory. Milan J. Math. 88, 409–454 (2020). https://doi.org/10.1007/s00032-020-00319-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00032-020-00319-2