Note: All software packages are supported on Linux systems only. Testing has been done on CentOS 6/7 and Gentoo.

Causal Set Generator

The Causal Set Generator is a package written in C/C++ and CUDA used to study the statistical physics of graphs. Methods are grouped into three categories: sampling, dynamics, and measurement. Algorithms are accelerated using OpenMP, AVX/AVX2, CUDA, and OpenMPI. Data is output using the HDF5 file format. Implementation details are described here.

Graphs are sampled using a Poisson Point Process given the target dimension, manifold, bounding region, spatial curvature, and temporal symmetry. A complete list of supported combinations of these parameters are described in the file "VERSION". Alternatively, an edge list may be supplied for graphs generated using some other procedure.

Graph dynamics are performed by specifying an ensemble and an action. Both single-move and cluster updates are available, and methods may be accelerated using either parallel tempering (PT) or population annealing (PA). While PT may be distributed across dozens of CPU cores, PA has been tested with hundreds of thousands of GPU cores.

The following graph observables may be measured:
  • Local clustering coefficients
  • Number and size of connected components
  • Success ratio and/or stretch using greedy routing
  • Smeared and local Benincasa-Dowker action
  • Chain lengths and causal set height
  • Hub density
  • Fraction of geodesically disconnected node pairs
  • Number of elements near timelike boundaries (New in v5!)
  • Foliations into chains and antichains (New in v5!)
  • Antichain sizes and causal set width (New in v5!)
  • Myrheim-Meyer dimension (New in v5!)
  • Ordering fraction and link density (New in v5!)
  • Specific heat, free energy, and entropy (New in v5!)
This package includes one or more implementations of the following algorithms:
  • Newton-Raphson and bisection root-finding methods
  • Quicksort, mergesort, parallel bitonic sort, cycle sort, topological sort
  • Breadth and depth first search
  • Transitive closure and transitive reduction
  • Rejection sampling
  • Metropolis Monte Carlo
  • Parallel tempering Monte Carlo with adaptive temperature spacing
  • Population annealing Monte Carlo with adaptive temperature and sweep schedule
  • Asynchronous MPI scheduler (custom)
  • Parallel graph construction (custom)
  • Parallel causal set action (custom)
Citations:
  1. W.J. Cunningham and S. Surya. Dimensionally Restricted Causal Set Quantum Gravity: Examples in Two and Three Dimensions, Classical and Quantum Gravity 37, 054002 (2020).
  2. F. Versteegen. Quantum Gravity: From Continuous to Discrete, Ph.D. Thesis, Universitat Heidelberg (2019).
  3. R. Loll. Quantum Gravity from Causal Dynamical Triangulations: A Review, Classical and Quantum Gravity 37, 013002 (2019).
  4. A. Eichhorn. Steps towards Lorentzian Quantum Gravity with Causal Sets, Journal of Physics: Conference Series 1275, 012010 (2019).
  5. M. Aghili, L. Bombelli, and B.B. Pilgrim. Discrete Spacetime: A Web of Chains, Classical and Quantum Gravity 36, 185015 (2019).
  6. L. Glaser. The Ising Model Coupled to 2D Orders, Classical and Quantum Gravity 35, 084001 (2018).
  7. W.J. Cunningham. Inference of Boundaries in Causal Sets, Classical and Quantum Gravity 35, 094002 (2018).
  8. A. Belenchia, D.M.T. Benincasa, M. Letizia, and S. Liberati. On the Entanglement Entropy of Quantum Fields in Causal Sets, Classical and Quantum Gravity 35, 074002 (2018).
  9. C.A. Kelly. Approaches to Numerical Simulations of Causal Sets, Masters Thesis, Norwegian University of Science and Technology (2018)
  10. W.J. Cunningham. High Performance Algorithms for Quantum Gravity and Cosmology, Ph.D. Thesis, Northeastern University (2018).
  11. W.J. Cunningham and D. Krioukov. Causal Set Generator and Action Computer, Computer Physics Communications 233, 123 (2018).
  12. W. Cunningham and D. Krioukov. Navigability of Random Geometric Graphs in the Universe and Other Spacetimes, Scientific Reports 7, 8699 (2017).

FastMath Toolkit

The FastMath Toolkit is a package written in C and x64 assembly intended to provide efficient implementations of certain mathematical functions and data structures. These include approximations to the following:
  • Power and root functions
  • Exponential and logarithmic functions
  • Absolute value and sign functions
  • Trigonometric and hyperbolic functions
  • Gamma function and Pochhammer symbols
  • Gauss hypergeomtric function with transformations
The package also includes compact data structures for the following:
  • Bitset and bit-packed matrix
  • Geometric and unlabeled graphs
  • Single-precision coordinates
  • Array-structured data
Citations:
  1. P. van der Hoorn, W.J. Cunningham, G. Lippner, C. Trugenberger, and D. Krioukov. Ollivier-Ricci Curvature Convergence in Random Geometric Graphs, arXiv Preprint (2020).
  2. W.J. Cunningham and S. Surya. Dimensionally Restricted Causal Set Quantum Gravity: Examples in Two and Three Dimensions, Classical and Quantum Gravity 37, 054002 (2020).
  3. W.J. Cunningham. High Performance Algorithms for Quantum Gravity and Cosmology, Ph.D. Thesis, Northeastern University (2018).
  4. W.J. Cunningham. Inference of Boundaries in Causal Sets, Classical and Quantum Gravity 35, 094002 (2018).
  5. W.J. Cunningham and D. Krioukov. Causal Set Generator and Action Computer, Computer Physics Communications 233, 123 (2018).
  6. W. Cunningham and D. Krioukov. Navigability of Random Geometric Graphs in the Universe and Other Spacetimes, Scientific Reports 7, 8699 (2017).

Graph Curvature Toolkit

The Graph Curvature Toolkit is a package written in C/C++ and CUDA used to calculate the Ollivier-Ricci curvature of random graphs representing discrete constant-curvature manifolds. Motivations and implementation details are described here. The following types of graphs may be generated using this toolkit:
  • One-dimensional random geometric graph (RGG) on the real line with periodic boundaries
  • One-dimensional periodic lattice
  • Two-dimensional periodic lattice
  • Two-dimensional RGG on a torus
  • Two-dimensional RGG on a sphere
  • Two-dimensional RGG on a Bolza surface
  • Binary tree
  • Complete graph
This package also implements several search algorithms which have been optimized for large graphs. These include the following:
  • Breadth First Search
  • Depth First Search
  • Dijkstra's Algorithm (single-source-multiple-destination)
  • A* Algorithm (single-source-single-destination)
  • Hybrid A* Algorithm (single-source-multiple-destination)
  • Hybrid GA* Algorithm (GPU implementation of Hybrid A*)
Finally, there is also a subroutine to calculate exactly the Wasserstein distance between two graph neighborhoods, using either unweighted or weighted edges. This is achieved using the MOSEK package for convex optimization.

Citations:
  1. P. van der Hoorn, G. Lippner, C. Trugenberger, and D. Krioukov. Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds, arXiv Preprint (2020).
  2. P. van der Hoorn, W.J. Cunningham, G. Lippner, C. Trugenberger, and D. Krioukov. Ollivier-Ricci Curvature Convergence in Random Geometric Graphs, arXiv Preprint (2020).

More to come shortly!