\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Homotopy continuation for the spectra of persistent Laplacians

  • * Corresponding author: Guo-Wei Wei

    * Corresponding author: Guo-Wei Wei

This work was supported in part by NIH grant GM126189, NSF grants DMS-2052983, DMS-1761320, and IIS-1900473, NASA grant 80NSSC21M0023, Michigan Economic Development Corporation, George Mason University award PD45722, Bristol-Myers Squibb 65109, and Pfizer. The authors thank Dr. Wenrui Hao and Ms. Rui Wang for discussion and/or help.

Abstract / Introduction Full Text(HTML) Figure(18) Related Papers Cited by
  • The $ p $-persistent $ q $-combinatorial Laplacian defined for a pair of simplicial complexes is a generalization of the $ q $-combinatorial Laplacian. Given a filtration, the spectra of persistent combinatorial Laplacians not only recover the persistent Betti numbers of persistent homology but also provide extra multiscale geometrical information of the data. Paired with machine learning algorithms, the persistent Laplacian has many potential applications in data science. Seeking different ways to find the spectrum of an operator is an active research topic, becoming interesting when ideas are originated from multiple fields. In this work, we explore an alternative approach for the spectrum of persistent Laplacians. As the eigenvalues of a persistent Laplacian matrix are the roots of its characteristic polynomial, one may attempt to find the roots of the characteristic polynomial by homotopy continuation, and thus resolving the spectrum of the corresponding persistent Laplacian. We consider a set of simple polytopes and small molecules to prove the principle that algebraic topology, combinatorial graph, and algebraic geometry can be integrated to understand the shape of data.

    Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  0-simplex, 1-simplex, 2-simplex and 3-simplex

    Figure 2.  Rips complexes corresponding to different $ r $ values

    Figure 3.  Pentagon, Heptagon, Octagon and Nonagon

    Figure 4.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ against the radius $ \alpha $ for the pentagon. The persistent Betti numbers are shown by the blue line. The smallest nonzero eigenvalues calculated by HERMES and Bertini are shown by a red line and red circles, respectively and one can see that they almost coincide. The half edge length is approximately $ \sin(\pi/5) \approx 0.58 $

    Figure 5.  (a) A cube with edge length 1. (b) A regular octahedron with edge length $ \sqrt{2} $. (c) A regular tetrahedron with edge length $ \sqrt{3} $. (d) A regular pyramid with square edge length $ \sqrt{2} $ and height 2. (e) A triangular prism with edge length $ \sqrt{3}$

    Figure 6.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the cube. The length of its face diagonal is $ \sqrt{2} \approx 1.4 $ and the length of its main diagonal is $ \sqrt{3} \approx 1.7$

    Figure 7.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the octahedron. Its edge length is $ \sqrt{2} $. The circumradius of any face is equal to $ \sqrt{2}/\sqrt{3} \approx 0.8 $. The circumradius of the octahedron itself is equal to $ 1 $

    Figure 8.  Some aromatic molecules

    Figure 9.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the benzene. The half length of its edge is approximately 0.7Å, and its radius is approximately 1.4Å

    Figure 10.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the heptagon

    Figure 11.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the octagon

    Figure 12.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the nonagon

    Figure 13.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the regular tetrahedron with edge length $ \sqrt{3} $. The centroid to vertex distance is $ 3/\sqrt{8} \approx 1.06 $

    Figure 14.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for a triangular prism. Its base is a regular triangle with edge length $ \sqrt{3} $. Its side faces are squares. Important distances are $ \sqrt{3}/2, 1, \sqrt{6}/2 \approx 1.22 $ and $ \sqrt{7}/2 \approx 1.32 $

    Figure 15.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for a regular pyramid. Its base is a square with edge length $ \sqrt{2} $ and its height is 2. Important distances are $ \sqrt{2}/2, 1, \sqrt{5}/2 \approx 1.12, 5\sqrt{2}/6 \approx 1.18 $ and $ 5/4 $

    Figure 16.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the naphthalene

    Figure 17.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the anthracene

    Figure 18.  The illustration of the persistent Betti numbers $ \beta_{q}^{\alpha, 0} $ and the smallest nonzero eigenvalues of persistent Laplacians $ \lambda_{q}^{\alpha, 0} $ for the pyrene

  • [1] E. L. AllgowerD. J. BatesA. J. Sommese and C. W. Wampler, Solution of polynomial systems derived from differential equations, Computing, 76 (2006), 1-10.  doi: 10.1007/s00607-005-0132-4.
    [2] D. N. Arnold, G. David, M. Filoche, D. Jerison and S. Mayboroda, Computing spectra without solving eigenvalue problems, SIAM J. Sci. Comput., 41 (2019), B69–B92. doi: 10.1137/17M1156721.
    [3] D. J. Bates, I. A. Fotiou and P. Rostalski, A numerical algebraic geometry approach to nonlinear constrained optimal control, 46th IEEE Conference on Decision and Control, New Orleans, LA, 2007. doi: 10.1109/CDC.2007.4434470.
    [4] D. J. Bates, J. D. Hauenstein, A. J. Sommese and C. W. Wampler, Bertini: Software for numerical algebraic geometry., Available from: https://bertini.nd.edu.
    [5] D. J. Bates, J. D. Hauenstein, A. J. Sommese and C. W. Wampler, Numerically Solving Polynomial Systems with Bertini, Software, Environments, and Tools, 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. doi: 10.1137/1.9781611972702.
    [6] P. Breiding and S. Timme, HomotopyContinuation.jl: A package for homotopy continuation in Julia, in International Congress on Mathematical Software, Lecture Notes in Computer Science, 10931, Springer, 2018,458–465. doi: 10.1007/978-3-319-96418-8_54.
    [7] Z. CangL. MuK. WuK. OpronK. Xia and G.-W. Wei, A topological approach for protein classification, Computational and Mathematical Biophysics, 3 (2015), 140-162.  doi: 10.1515/mlbmb-2015-0009.
    [8] G. Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.), 46 (2009), 255-308.  doi: 10.1090/S0273-0979-09-01249-X.
    [9] T. Chen, T.-L. Lee and T.-Y. Li, Hom4ps-3: A parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continuation methods, in Mathematical Software – ICMS 2014, Lecture Notes in Comput. Sci., 8592, Springer, Heidelberg, 2014,183–190. doi: 10.1007/978-3-662-44199-2_30.
    [10] H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010. doi: 10.1090/mbk/069.
    [11] J. Friedman, Computing betti numbers via combinatorial Laplacians, Algorithmica, 21 (1998), 331-346.  doi: 10.1007/PL00009218.
    [12] M. GameiroY. HiraokaS. IzumiM. KramarK. Mischaikow and V. Nanda, A topological measurement of protein compressibility, Jpn. J. Ind. Appl. Math., 32 (2015), 1-17.  doi: 10.1007/s13160-014-0153-5.
    [13] T. E. Goldberg, Combinatorial Laplacians of simplicial complexes, Senior project, Bard College, 2002. Available from: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3354&rep=rep1&type=pdf.
    [14] E. Gross, B. Davis, K. L. Ho, D. J. Bates and H. A. Harrington, Numerical algebraic geometry for model selection and its application to the life sciences, J. Roy. Soc. Interface, 13 (2016). doi: 10.1098/rsif.2016.0256.
    [15] The GUDHI Project, GUDHI User and Reference Manual, 3.4.1 edition, GUDHI Editorial Board, 2021. Available from: https://gudhi.inria.fr/doc/3.4.1/.
    [16] W. HaoJ. D. HauensteinB. HuY. LiuA. J. Sommese and Y.-T. Zhang, Multiple stable steady states of a reaction-diffusion model on zebrafish dorsal-ventral patterning, Discrete Contin. Dyn. Syst. Ser. S, 4 (2011), 1413-1428.  doi: 10.3934/dcdss.2011.4.1413.
    [17] W. Hao, B. Hu and A. J. Sommese, Numerical algebraic geometry and differential equations, in Future Vision and Trends on Shapes, Geometry and Algebra, Springer Proc. Math. Stat., 84, Springer, London, 2014, 39–53. doi: 10.1007/978-1-4471-6461-6_3.
    [18] C. R. HarrisK. J. MillmanS. J. van der WaltR. Gommers and P. Virtanen, et al., Array programming with NumPy, Nature, 585 (2020), 357-362.  doi: 10.1038/s41586-020-2649-2.
    [19] J. HauensteinJ. I. Rodriguez and B. Sturmfels, Maximum likelihood for matrices with rank constraints, J. Algebr. Stat., 5 (2014), 18-38.  doi: 10.18409/jas.v5i1.23.
    [20] A. Leykin and F. Sottile, Galois groups of Schubert problems via homotopy computation, Math. Comp., 78 (2009), 1749-1765.  doi: 10.1090/S0025-5718-09-02239-X.
    [21] L.-H. Lim, Hodge Laplacians on graphs, SIAM Rev., 62 (2020), 685-715.  doi: 10.1137/18M1223101.
    [22] X. Liu, X. Wang, J. Wu and K. Xia, Hypergraph-based persistent cohomology (HPC) for molecular representations in drug design, Briefings in Bioinformatics, (2021), bbaa411. doi: 10.1093/bib/bbaa411.
    [23] E. R. Love, B. Filippenko, V. Maroulas and G. Carlsson, Topological deep learning, preprint, arXiv: 2101.05778.
    [24] F. Mémoli, Z. Wan and Y. Wang, Persistent Laplacians: Properties, algorithms and implications, preprint, arXiv: 2012.02808.
    [25] Z. Meng, D. Vijay Anand, Y. Lu, J. Wu and K. Xia, Weighted persistent homology for biomolecular data analysis, Scientific Reports, 10 (2020), 1-15. doi: 10.1038/s41598-019-55660-3.
    [26] F. Nasrin, C. Oballe, D. Boothe and V. Maroulas, Bayesian topological learning for brain state classification, 18th IEEE International Conference On Machine Learning And Applications (ICMLA), Boca Raton, FL, 2019. doi: 10.1109/ICMLA.2019.00205.
    [27] D. D. NguyenZ. Cang and G.-W. Wei, A review of mathematical representations of biomolecular data, Phys. Chem. Chem. Phys., 22 (2020), 4343-4367.  doi: 10.1039/C9CP06554G.
    [28] Y. RenJ. W. R. Martini and J. Torres, Decoupled molecules with binding polynomials of bidegree $(n, 2)$, J. Math. Biol., 78 (2019), 879-898.  doi: 10.1007/s00285-018-1295-x.
    [29] I. SgouralisA. Nebenführ and V. Maroulas, A Bayesian topological framework for the identification and reconstruction of subcellular motion, SIAM J. Imaging Sci., 10 (2017), 871-899.  doi: 10.1137/16M1095755.
    [30] A. J. Sommese and C. W. Wampler II, The Numerical Solution of Systems of Polynomials. Arising in Engineering and Science, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. doi: 10.1142/5763.
    [31] J. TownsendC. P. MicucciJ. H. HymelV. Maroulas and K. D. Vogiatzis, Representation of molecular structures with persistent homology for machine learning applications in chemistry, Nature Communications, 11 (2020), 1-9.  doi: 10.1038/s41467-020-17035-5.
    [32] J. Verschelde, Algorithm 795: Phcpack: A general-purpose solver for polynomial systems by homotopy continuation, ACM Trans. Math. Softw., 25 (1999), 251-276.  doi: 10.1145/317275.317286.
    [33] C. W. Wampler and A. J. Sommese, Numerical algebraic geometry and algebraic kinematics, Acta Numer., 20 (2011), 469-567.  doi: 10.1017/S0962492911000067.
    [34] R. Wang, D. D. Nguyen and G.-W. Wei, Persistent spectral graph, Int. J. Numer. Methods Biomed. Eng., 36 (2020), 27pp. doi: 10.1002/cnm.3376.
    [35] R. WangR. ZhaoE. Ribando-GrosJ. ChenY. Tong and G.-W. Wei, HERMES: Persistent spectral graph software, Foundations of Data Science, 3 (2020), 67-97.  doi: 10.3934/fods.2021006.
    [36] K. Xia and G.-W. Wei, Persistent homology analysis of protein structure, flexibility, and folding, Int. J. Numer. Methods Biomed. Eng., 30 (2014), 814-844.  doi: 10.1002/cnm.2655.
    [37] X.-D. Zhang, The Laplacian eigenvalues of graphs: A survey, preprint, arXiv: 1111.2897.
  • 加载中

Figures(18)

SHARE

Article Metrics

HTML views(4682) PDF downloads(429) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return