Computation of polarized metrized graph invariants by using discrete Laplacian matrix

Cinkir, Zubeyir

doi:10.1090/mcom/2981

Computation of polarized metrized graph invariants by using discrete Laplacian matrix
HTML articles powered by AMS MathViewer

by Zubeyir Cinkir PDF

Math. Comp. 84 (2015), 2953-2967 Request permission

Abstract:

Several invariants of polarized metrized graphs and their applications in Arithmetic Geometry have been studied recently. In this paper, we give fast algorithms to compute these invariants by expressing them in terms of the discrete Laplacian matrix and its pseudo inverse. The algorithm we give can be used for both symbolic and numerical computations. We present various examples to illustrate the implementation of these algorithms.

References

Matthew Baker and Xander Faber, Metrized graphs, Laplacian operators, and electrical networks, Quantum graphs and their applications, Contemp. Math., vol. 415, Amer. Math. Soc., Providence, RI, 2006, pp. 15–33. MR 2277605, DOI 10.1090/conm/415/07857
Matt Baker and Robert Rumely, Harmonic analysis on metrized graphs, Canad. J. Math. 59 (2007), no. 2, 225–275. MR 2310616, DOI 10.4153/CJM-2007-010-2
R. B. Bapat, Resistance matrix of a weighted graph, MATCH Commun. Math. Comput. Chem. 50 (2004), 73–82. MR 2037425
R. B. Bapat, Resistance distance in graphs, Math. Student 68 (1999), no. 1-4, 87–98. MR 1836414
Enrico Bombieri and Walter Gubler, Heights in Diophantine geometry, New Mathematical Monographs, vol. 4, Cambridge University Press, Cambridge, 2006. MR 2216774, DOI 10.1017/CBO9780511542879
Z. Cinkir, The Tau Constant of Metrized Graphs, Thesis at University of Georgia, Athens, GA, 2007.
Zubeyir Cinkir, The tau constant of a metrized graph and its behavior under graph operations, Electron. J. Combin. 18 (2011), no. 1, Paper 81, 42. MR 2788698
Zubeyir Cinkir, The tau constant and the edge connectivity of a metrized graph, Electron. J. Combin. 19 (2012), no. 4, Paper 46, 32. MR 3007181
Zubeyir Cinkir, Zhang’s conjecture and the effective Bogomolov conjecture over function fields, Invent. Math. 183 (2011), no. 3, 517–562. MR 2772087, DOI 10.1007/s00222-010-0282-7
Zubeyir Cinkir, The tau constant and the discrete Laplacian matrix of a metrized graph, European J. Combin. 32 (2011), no. 4, 639–655. MR 2780862, DOI 10.1016/j.ejc.2011.01.008
P. Courrieu, Fast Computation of Moore-Penrose Inverse Matrices, Neural Information Processing - Letters and Reviews, Volume 8, No 2, (2005), 25–29.
Ted Chinburg and Robert Rumely, The capacity pairing, J. Reine Angew. Math. 434 (1993), 1–44. MR 1195689, DOI 10.1515/crll.1993.434.1
Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
X. W. C. Faber, The geometric Bogomolov conjecture for curves of small genus, Experiment. Math. 18 (2009), no. 3, 347–367. MR 2555704
X. W. C. Faber, Topics in arithmetic geometry over function fields, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)–Columbia University. MR 2711474
Marc Hindry and Joseph H. Silverman, Diophantine geometry, Graduate Texts in Mathematics, vol. 201, Springer-Verlag, New York, 2000. An introduction. MR 1745599, DOI 10.1007/978-1-4612-1210-2
Robin de Jong, Admissible constants for genus 2 curves, Bull. Lond. Math. Soc. 42 (2010), no. 3, 405–411. MR 2651934, DOI 10.1112/blms/bdp132
Robin de Jong, Second variation of Zhang’s $\lambda$-invariant on the moduli space of curves, Amer. J. Math. 135 (2013), no. 1, 275–290. MR 3022965, DOI 10.1353/ajm.2013.0008
D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81–95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566, DOI 10.1007/BF01164627
The MathWorks Inc., Matlab, Version R2011a, Natick, Massachusetts, (2011).
Atsushi Moriwaki, Bogomolov conjecture over function fields for stable curves with only irreducible fibers, Compositio Math. 105 (1997), no. 2, 125–140. MR 1440719, DOI 10.1023/A:1000139117766
Atsushi Moriwaki, Bogomolov conjecture for curves of genus $2$ over function fields, J. Math. Kyoto Univ. 36 (1996), no. 4, 687–695. MR 1443744, DOI 10.1215/kjm/1250518448
Wolfram Research, Inc., Mathematica, Version 8.0, Champaign, IL, 2010.
C. Radhakrishna Rao and Sujit Kumar Mitra, Generalized inverse of matrices and its applications, John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 0338013
G. Kirchhoff, Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72 (1847), 497–508; for a reprint (Engl. transl.), see: I.R.E. Trans. Circuit Theory, 5, (1958), 4.
D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81–95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566, DOI 10.1007/BF01164627
Kazuhiko Yamaki, Graph invariants and the positivity of the height of the Gross-Schoen cycle for some curves, Manuscripta Math. 131 (2010), no. 1-2, 149–177. MR 2574996, DOI 10.1007/s00229-009-0305-0
Kazuhiko Yamaki, Effective calculation of the geometric height and the Bogomolov conjecture for hyperelliptic curves over function fields, J. Math. Kyoto Univ. 48 (2008), no. 2, 401–443. MR 2436745, DOI 10.1215/kjm/1250271420
Kazuhiko Yamaki, Geometric Bogomolov’s conjecture for curves of genus 3 over function fields, J. Math. Kyoto Univ. 42 (2002), no. 1, 57–81. MR 1932737, DOI 10.1215/kjm/1250284711
A. J. Stothers, On the Complexity of Matrix Multiplication, Thesis at University of Edinburgh, Edinburgh, 2010.
Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
L. Szpiro, Séminaire sur les pinceaux de courbes de genre au moins deux, Astérisque 86 (1981), no. 3, 44–78.
L. Szpiro, Sur les propriétés numériques du dualisant relatif d’une surface arithmétique, The Grothendieck Festschrift, Vol. III, Progr. Math., vol. 88, Birkhäuser Boston, Boston, MA, 1990, pp. 229–246 (French). MR 1106917, DOI 10.1007/978-0-8176-4576-2_{9}
Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd [extended abstract], STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887–898. MR 2961552, DOI 10.1145/2213977.2214056
Shouwu Zhang, Admissible pairing on a curve, Invent. Math. 112 (1993), no. 1, 171–193. MR 1207481, DOI 10.1007/BF01232429
Shou-Wu Zhang, Gross-Schoen cycles and dualising sheaves, Invent. Math. 179 (2010), no. 1, 1–73. MR 2563759, DOI 10.1007/s00222-009-0209-3