TY - JOUR
T1 - ZZPolyCalc
T2 - An open-source code with fragment caching for determination of Zhang-Zhang polynomials of carbon nanostructures
AU - Podeszwa, Rafał
AU - Witek, Henryk A.
AU - Chou, Chien Pin
N1 - Publisher Copyright:
© 2024 Elsevier B.V.
PY - 2024/8
Y1 - 2024/8
N2 - 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.
AB - 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.
KW - Caching
KW - Carbon nanostructures
KW - Clar covers
KW - Generalized resonance structures
KW - Topological invariants
KW - Zhang-Zhang (ZZ) polynomials
UR - http://www.scopus.com/inward/record.url?scp=85190945900&partnerID=8YFLogxK
U2 - 10.1016/j.cpc.2024.109210
DO - 10.1016/j.cpc.2024.109210
M3 - Article
AN - SCOPUS:85190945900
SN - 0010-4655
VL - 301
JO - Computer Physics Communications
JF - Computer Physics Communications
M1 - 109210
ER -