×

a-tint: a polymake extension for algorithmic tropical intersection theory. (English) Zbl 1285.14071

Summary: We study algorithmic aspects of tropical intersection theory. We analyze how divisors and intersection products on tropical cycles can actually be computed using polyhedral geometry. The main focus of this paper is the study of moduli spaces, where the underlying combinatorics of the varieties involved allow a much more efficient way of computing certain tropical cycles. The algorithms discussed here have been implemented in an extension for polymake, a software for polyhedral computations.

MSC:

14T05 Tropical geometry (MSC2010)
14Q99 Computational aspects in algebraic geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, M.; Ziegler, G. M., Proofs from THE BOOK (1998), Springer · Zbl 0905.00001
[2] Allermann, L.; Rau, J., First steps in tropical intersection theory, Math. Z., 264, 3, 633-670 (2010), Available at: arxiv:0709.3705v3 · Zbl 1193.14074
[3] Ardila, F.; Klivans, C. J., The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B, 96, 38-49 (2006), Available at: arxiv:math/0311370v2 · Zbl 1082.05021
[4] Avis, D.; Bremner, D.; Seidel, R., How good are convex hull algorithms, Comput. Geom. Theory Appl., 7, 265-302 (1997) · Zbl 0877.68119
[5] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., 8, 295-313 (1992) · Zbl 0752.68082
[6] Barthélemy, J.-P.; Guénoche, A., Trees and Proximity Representations (1991), Wiley-Interscience: Wiley-Interscience Chichester
[8] Buneman, P., A note on the metric properties of trees, J. Combin. Theory, 17, 48-50 (1974) · Zbl 0286.05102
[9] Cohen, H., A Course in Computational Algebraic Number Theory (2000), Springer Verlag: Springer Verlag Berlin
[10] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer-Verlag · Zbl 0634.52001
[11] Feichtner, E.; Sturmfels, B., Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), 62, 437-468 (2005), Available at: arxiv:math/0411260 · Zbl 1092.52006
[14] Fulton, W.; Sturmfels, B., Intersection theory on toric varieties, Topology, 36, 2 (1997), Available at: arxiv:9403002 · Zbl 0885.14025
[15] Gathmann, A.; Kerber, M.; Markwig, H., Tropical fans and the moduli spaces of tropical curves, Compos. Math., 145, 1, 173-195 (2009), Available at: arxiv:0708.2268 · Zbl 1169.51021
[16] Gawrilow, E.; Joswig, M., polymake: a framework for analyzing convex polytopes, (Polytopes—Combinatorics and Computation (2000)), 43-74, polymake is available at: http://www.polymake.org · Zbl 0960.68182
[17] Grünbaum, B., Convex Polytopes (2003), Springer-Verlag
[18] Havas, G.; Majewski, B. S.; Matthews, K. R., Extended GCD and Hermite normal form algorithms via lattice basis reduction, Experiment. Math., 7, 125-136 (1998) · Zbl 0922.11112
[20] Kerber, M.; Markwig, H., Intersecting Psi-classes on tropical \(M_{0, n}\), Int. Math. Res. Not., 2009, 2, 221-240 (2009), Available at: arxiv:0709.3953v2 · Zbl 1205.14070
[21] Khachiyan, L.; Boros, E.; Elbassioni, K.; Gurvich, V.; Makino, K., On the complexity of some enumeration problems for matroids, SIAM J. Discrete Math., 19, 4, 966-984 (2006) · Zbl 1104.05017
[24] Mikhalkin, G., Moduli spaces of rational tropical curves, (Proceedings of the 13th Gökova Geometry-Topology Conference (2007), International Press: International Press Cambridge, MA), 39-51, Available at: arxiv:0704.0839 · Zbl 1203.14027
[25] Motzkin, T. S.; Raiffa, H.; Thompson, G. L.; Thrall, R. M., The double description method, (Contributions to Theory of Games, Vol. 2 (1953)) · Zbl 0050.14201
[27] Rincón, F., Computing tropical linear spaces, J. Symbolic. Comput., 51, 86-98 (2013) · Zbl 1319.14060
[29] Seymour, P. D., A note on hyperplane generation, J. Combin. Theory Ser. B, 1, 1, 88-91 (1994) · Zbl 0803.05015
[31] Speyer, D., Tropical linear spaces, SIAM J. Discrete Math., 22, 1527-1558 (2008), Available at: arxiv:math/0410455 · Zbl 1191.14076
[32] Speyer, D.; Sturmfels, B., The tropical grassmannian, Adv. Geom., 4, 3, 389-411 (2004), Available at: arxiv:math/0304218 · Zbl 1065.14071
[33] Sturmfels, B., (Solving Systems of Polynomial Equations. Solving Systems of Polynomial Equations, CBMS Regional Conferences Series in Mathematics, vol. 97 (2002), Published for the Conference Board of the Mathematical Sciences: Published for the Conference Board of the Mathematical Sciences Washington, DC) · Zbl 1101.13040
[34] Tiwary, H. R., On the hardness of computing intersection, union and minkowski sum of polytopes, Discrete Comput. Geom., 40, 3, 469-479 (2008) · Zbl 1155.52008
[35] Volodin, I. A.; Kuznecov, V. E.; Fomenko, A. T., The problem of the algorithmic discrimination of the standard three-dimensional sphere, Uspekhi Mat. Nauk, 29, 71-168 (1974), Appendix by S. P. Novikov
[36] Witten, E., Two-dimensional gravity and intersection theory on moduli space, Surv. Differ. Geom., 1, 243-310 (1991) · Zbl 0757.53049
[37] Ziegler, G., (Lectures on Polytopes. Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (1994), Springer-Verlag) · Zbl 0823.52002
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.