×

Diffuse scattering on graphs. (English) Zbl 1331.05207

Summary: We formulate and analyze difference equations on graphs analogous to time-independent diffusion equations arising in the study of diffuse scattering in continuous media. Moreover, we show how to construct solutions in the presence of weak scatterers from the solution to the homogeneous (background problem) using Born series, providing necessary conditions for convergence and demonstrating the process through numerous examples. In addition, we outline a method for finding Green’s functions for Cayley graphs for both abelian and non-abelian groups. Finally, we conclude with a discussion of the effects of sparsity on our method and results, outlining the simplifications that can be made provided that the scatterers are weak and well-separated.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
68R10 Graph theory (including graph drawing) in computer science
35Q99 Partial differential equations of mathematical physics and other areas of application
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions (1964), National Bureau of Standards · Zbl 0171.38503
[2] Angel, O.; Holroyd, A. E.; Romik, D.; Virág, B., Random sorting networks, Adv. Math., 215, 839-868 (2007) · Zbl 1132.60008
[3] Araúz, C.; Carmona, A.; Encinas, A., Overdetermined partial boundary value problems on finite networks, J. Math. Anal. Appl., 423, 191-207 (2014) · Zbl 1310.35234
[4] Arridge, S. R.; Schotland, J. C., Optical tomography: forward and inverse problems, Inverse Probl., 25 (2009) · Zbl 1188.35197
[5] Bendito, E.; Carmona, A.; Encinas, A. M., Solving boundary value problems on networks using equilibrium measures, J. Funct. Anal., 171, 155-176 (2000) · Zbl 0958.31004
[6] Bendito, E.; Carmona, A.; Encinas, A. M., Potential theory for Schrödinger operators on finite networks, Rev. Mat. Iberoam., 21, 771-818 (2005) · Zbl 1102.31011
[7] Bendito, E.; Encinas, A. M.; Carmona, A., Eigenvalues, eigenfunctions and Green’s functions on a path via Chebyshev polynomials, Appl. Anal. Discrete Math., 3, 282-302 (2009) · Zbl 1257.39005
[8] Bensoussan, A.; Menaldi, J.-L., Difference equations on weighted graphs, J. Convex Anal., 12, 13-44 (2005) · Zbl 1068.05039
[9] Beurling, A.; Deny, J., Espaces de Dirichlet I, le cas élémentaire, Acta Math., 99, 203-224 (1958) · Zbl 0089.08106
[10] Carmona, A.; Encinas, A. M.; Mitjana, M., Discrete elliptic operators and their Green operators, Linear Algebra Appl., 442, 115-134 (2014) · Zbl 1286.35085
[11] Carmona, A.; Encinas, A. M.; Mitjana, M., Green matrices associated with generalized linear polyominoes, Linear Algebra Appl., 468, 38-47 (2015) · Zbl 1320.15037
[12] Carmona, A.; Encinas, A. M.; Mitjana, M., Perturbations of discrete elliptic operators, Linear Algebra Appl., 468, 270-285 (2015) · Zbl 1307.31019
[13] Cartier, P., Fonctions harmoniques sur un arbre, Sympos. Math., 9, 203-270 (1972) · Zbl 0283.31005
[14] Chau, C.-K.; Basu, P., Analysis of latency of stateless opportunistic forwarding in intermittently connected networks, IEEE/ACM Trans. Netw., 19, 1111-1124 (2011)
[15] Choquet, G.; Deny, J., Modèles finis en théorie du potentiel, J. Anal. Math., 5, 77-135 (1956) · Zbl 0086.30502
[16] Chung, F. R., Spectral Graph Theory (1997), American Mathematical Society · Zbl 0867.05046
[17] Chung, F. R.; Yau, S. T., Discrete Green’s functions, J. Combin. Theory Ser. A, 91, 191-214 (2000) · Zbl 0963.65120
[18] Ciarlet, P. G., Introduction to Numerical Linear Algebra and Optimisation (1989), Cambridge University Press
[19] Cserti, J.; David, G.; Piroth, A., Perturbation of infinite networks of resistors, Amer. J. Phys., 70, 153-159 (2002)
[20] Curtis, E. B.; Morrow, J. A., Inverse Problems for Electrical Networks (2000), World Scientific Publishing · Zbl 1056.94022
[21] Drineas, P.; Mahoney, M. W., Effective resistances, statistical leverage, and applications to linear equation solving (2010), CoRR
[22] Duffin, R. J., Discrete potential theory, Duke Math. J., 20, 233-251 (1953) · Zbl 0051.07203
[23] Economou, E. N., Green’s Functions in Quantum Physics (2006), Springer: Springer Berlin, Heidelberg
[24] Ellis, R. B., Discrete Green’s functions for products of regular graphs (2003)
[25] Ellis, R. B., Chip-firing games with Dirichlet eigenvalues and discrete Green’s functions (2002), University of California, San Diego: University of California, San Diego San Diego, PhD thesis
[26] Fisher, A. R.; Schissler, A. J.; Schotland, J. C., Photoacoustic effect for multiply scattered light, Phys. Rev. E, 76 (2007)
[27] Gantmacher, F. P.; Krein, M. G., Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems (2002), AMS Chelsea Publishing · Zbl 1002.74002
[28] Grötschel, M.; Jünger, M.; Reinelt, G., Facets of the linear ordering polytope, Math. Program., 33, 43-60 (1985) · Zbl 0577.05035
[29] Kayano, T.; Yamasaki, M., Dirichlet finite solution of Poisson equations on an infinite network, Hiroshima Math. J., 12, 569-579 (1982) · Zbl 0523.31005
[30] Kenyon, R. W.; Wilson, D. B., Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs, J. Amer. Math. Soc., 28, 985-1030 (2015) · Zbl 1327.60033
[31] Kirchhoff, G., On the solution of the equations obtained from the investigation of the linear distribution of galvanic currents, IRE Trans. Circuit Theory, 5, 4-7 (1958)
[32] Koutis, I.; Miller, G.; Peng, R., A nearly-\(o(m \log n)\) time solver for SDD linear systems, (2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS (2011)), 590-598 · Zbl 1292.05249
[33] Lin, Y.-R.; Sundaram, H.; Chi, Y.; Tatemura, J.; Tseng, B. L., Blog community discovery and evolution based on mutual awareness expansion, (Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence. Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, WI ’07, Washington, DC, USA (2007), IEEE Computer Society), 48-56
[34] Martin, P., Discrete scattering theory: Green’s function for a square lattice, Wave Motion, 43, 619-629 (2006) · Zbl 1231.35135
[35] Mila, F.; Stafford, C. A.; Capponi, S., Persistent currents in a Möbius ladder: a test of interchain coherence of interacting electrons, Phys. Rev. B, 57, 1457-1460 (1998)
[36] Miller, P. D., Applied Asymptotic Analysis (2006), American Mathematical Society · Zbl 1101.41031
[37] Qiu, H.; Hancock, E. R., Clustering and embedding using commute times, IEEE Trans. Pattern Anal. Mach. Intell., 29, 1873-1890 (2007)
[38] Serre, J.-P., Linear Representations of Finite Groups (1977), Springer-Verlag
[39] Simon, J., Knots and chemistry, (New Scientific Applications of Geometry and Topology. New Scientific Applications of Geometry and Topology, Proc. Sympos. Appl. Math., vol. 45 (1992), American Math. Society: American Math. Society Providence, Rhode Island), 97-130 · Zbl 0772.57013
[40] Soardi, P. M., Potential Theory on Infinite Networks, Lecture Notes in Math. (1994), Springer-Verlag · Zbl 0818.31001
[41] Spielman, D. A.; Srivastava, N., Graph sparsification by effective resistances, (Proceedings of the 40th Annual ACM Symposium on Theory of Computing. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC ’08, New York, NY, USA (2008), ACM), 563-568 · Zbl 1231.68184
[42] Tanda, S.; Tsuneta, T.; Okajima, Y.; Inagaki, K.; Yamaya, K.; Hatakenaka, N., Crystal topology: a Möbius strip of single crystals, Nature, 417, 397-398 (2002)
[43] Terras, A., Fourier Analysis on Finite Groups and Applications (1999), Cambridge University Press · Zbl 0928.43001
[44] Thomson, R.; Zhou, S. J.; Carlsson, A. E.; Tewary, V. K., Lattice imperfections studied by use of lattice Green’s functions, Phys. Rev. B, 46, 10613-10622 (1992)
[45] Urakawa, H., Heat kernel and Green kernel comparison theorems for infinite graphs, J. Funct. Anal., 146, 206-235 (1997) · Zbl 0870.05070
[46] Urakawa, H., Spectra of the discrete and continuous Laplacians on graphs and Riemannian manifolds, Inter. Inform. Sci., 3, 95-109 (1997) · Zbl 0928.58034
[47] Vishnoi, N. K., Laplacian solvers and their algorithmic applications, Found. Trends Theor. Comput. Sci., 8, 1-141 (2012) · Zbl 1280.65003
[48] Yamasaki, M., The equation \(\Delta u = q u\) on an infinite network, Mem. Fac. Sci. Shimane Univ., 21, 31-46 (1987) · Zbl 0658.35024
[49] Zhu, X.; Ghahramani, Z.; Lafferty, J., Semi-supervised learning using gaussian fields and harmonic functions, (Proceedings of the Twentieth International Conference on Machine Learning. Proceedings of the Twentieth International Conference on Machine Learning, ICML (2003))
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.