ZZPolyCalc: An open-source code with fragment caching for determination of Zhang-Zhang polynomials of carbon nanostructures

Rafał Podeszwa*, Henryk A. Witek, Chien Pin Chou


研究成果: Article同行評審


Determination of topological invariants of graphene flakes, nanotubes, and fullerenes constitutes a challenging task due to its time-intensive nature and exponential scaling. The invariants can be organized in a form of a combinatorial polynomial commonly known as the Zhang-Zhang (ZZ) polynomial or the Clar covering polynomial. We report here a computer program, ZZPolyCalc, specifically designed to compute ZZ polynomials of large carbon nanostructures. The curse of the exponential scaling is avoided for a broad class of nanostructures by employing a sophisticated bookkeeping algorithm, in which each fragment appearing in the recursive decomposition is stored in the cache repository of molecular fragments indexed by a hash of the corresponding adjacency matrix. Although exponential scaling persists for the remaining nanostructures, the computational time is reduced by a few orders of magnitude owing to efficient use of hash-based fragment bookkeeping. The provided benchmark timings show that ZZPolyCalc allows for treating much larger carbon nanostructures than previously envisioned. Program summary: Program Title: ZZPolyCalc CPC Library link to program files: https://doi.org/10.17632/vmnr5xfb6t.1 Developer's repository link: https://github.com/quantumint/zzpolycalc Licensing provisions: GPLv3 Programming language: Fortran 2008, C Nature of problem: Calculations of Zhang-Zhang (ZZ) polynomials for carbon nanostructures have traditionally been performed by the application of a recursive algorithm, which scales exponentially with the size of the system. For large nanostructures, the problem often becomes intractable due to prohibitive computational cost. Consequently, ZZ polynomials were reported so far only for small or model systems, for which analytical formulas could be determined; larger systems, such as graphene flakes, fullerenes, or nanotubes, have been intractable with the existing implementations. Solution method: The process of determination of ZZ polynomials, based on recursive decomposition of a given carbon nanostructure, produces many identical fragments. In ZZPolyCalc, we avoid redundant calculations for such fragments by storing all the intermediate data in a hash table and reusing it efficiently whenever necessary. This new algorithm is particularly effective for elongated graphene flakes or carbon nanotubes, where the scaling becomes polynomial, but it also greatly reduces the computational time for other, less regular nanostructures.

期刊Computer Physics Communications
出版狀態Published - 8月 2024


深入研究「ZZPolyCalc: An open-source code with fragment caching for determination of Zhang-Zhang polynomials of carbon nanostructures」主題。共同形成了獨特的指紋。