Benchmarks
The suite adapts real applications to a portable array-programming style. This catalog is generated from metadata.json in the main repository.
Model Counting using einsum
Benchmarks Model Counting Algorithm using einsum operations.
Input generators (2)
Model Counting Generator
Parses standard DIMACS CNF test strings into sparse arrays for model counting.
Model Counting Competition Track1 Generator
Loads exact model counting CNF instances from MCComp Track1.
Weighted Model Counting using einsum
Benchmarks Weighted Model Counting Algorithm using einsum operations.
Input generators (2)
Weighted Model Counting Generator
Parses DIMACS CNF test strings into sparse arrays.
Model Counting Competition Track4 Generator
Loads projected weighted model counting CNF instances from MCComp Track4.
Bellman Ford Algorithm
This code implements an Array-API compatible version of Bellman Ford Algorithm to find the shortest distance from a src node to all edges across a graph. It takes in an adjacency matrix as an input and then slowly relaxes each vector by broadcasting it and then determining the minimum distances iteratively.
Input generators (3)
Bellman-Ford Test Input Generator
Small deterministic Bellman-Ford examples.
Bellman-Ford Input Generator
Input generator for Bellman-Ford shortest-path benchmarks.
Bellman-Ford GAP Input Generator
Input GAP generator for Bellman-Ford shortest-path benchmarks.
Betweenness Centrality Algorithm
This code is based on the Brandes betweenness centrality algorithm. The current code for the benchmark takes a two step approach. The first step involves going layer by layer from each potential starting node to find the total amount of shortest paths that lead to a node. So for example 4 -> 6 could have 3 diff shortest paths and 4 -> 2 could have only 1 shortest path. The second step is for tracing backwards to see how many times a node appears in other shortest paths. The number of times this node is in one of the shortest path divided by total shortest paths between the two edge nodes gets added to the intermediate nodes bc score.
Input generators (3)
Betweenness Centrality Test Input Generator
Small deterministic betweenness centrality examples.
Betweenness Centrality Input Generator
Input generator for betweenness centrality benchmarks.
Betweenness Centrality GAP Input Generator
Input GAP generator for betweenness centrality benchmarks.
Breadth-First Search Algorithm
The Breadth-First Search algorithm is an important graph traversal technique used to explore vertices by layers. It is a fundamental building block for more complex graph algorithms, especially in areas like parallel processing and high-performance computing.
Input generators (3)
Breadth-First Search Input Generator
Input generator for breadth-first search benchmarks.
Breadth-First Search Test Input Generator
Small deterministic BFS examples with reference outputs.
Breadth-First Search GAP Input Generator
GAP Input generator for breadth-first search benchmarks.
Brusselator — Backward Euler
2D Brusselator ODE with diffusion.
Input generators (1)
Brusselator
2D Brusselator ODE with diffusion.
Brusselator — Forward Euler
2D Brusselator ODE with diffusion.
Input generators (1)
Brusselator
2D Brusselator ODE with diffusion.
Brusselator — RK4
2D Brusselator ODE with diffusion.
Input generators (1)
Brusselator
2D Brusselator ODE with diffusion.
1D Finite Difference (Buckley-Leverett flux)
The purpose of this is to analyze the importance of numerical methods for PDEs, and applications sparse array theory into these method, through the form of benchmarks. This paticular benchmark analyzes the use of the Lax–Friedrichs method for solving nonlinear hyberbolic PDEs, with numerical stability and accuracy not seen in FTCS. This benchmark will run a simulation using both Lax–Friedrichs and analyze core concepts such as numerical stability, conservation law consistency, etc.
Input generators (1)
Finite Difference Data Generator
The finite difference generator uses a finite difference grid of500 by 500 cells, matching roughly the scale of areal finite difference problem, Norris/torso3 from UF Matrix Collection
2D Finite Difference (Buckley-Leverett flux)
The purpose of this is to analyze the importance of numerical methods for PDEs, and applications sparse array theory into these method, through the form of benchmarks. This paticular benchmark analyzes the use of the Lax–Friedrichs method for solving nonlinear hyberbolic PDEs, with numerical stability and accuracy not seen in FTCS. This benchmark will run a simulation using both Lax–Friedrichs and analyze core concepts such as numerical stability, conservation law consistency, etc.
Input generators (1)
Finite Difference Data Generator
The finite difference generator uses a finite difference grid of500 by 500 cells, matching roughly the scale of areal finite difference problem, Norris/torso3 from UF Matrix Collection
1D Finite Difference (Burgers flux)
The purpose of this is to analyze the importance of numerical methods for PDEs, and applications sparse array theory into these method, through the form of benchmarks. This paticular benchmark analyzes the use of the Lax–Friedrichs method for solving nonlinear hyberbolic PDEs, with numerical stability and accuracy not seen in FTCS. This benchmark will run a simulation using both Lax–Friedrichs and analyze core concepts such as numerical stability, conservation law consistency, etc.
Input generators (1)
Finite Difference Data Generator
The finite difference generator uses a finite difference grid of500 by 500 cells, matching roughly the scale of areal finite difference problem, Norris/torso3 from UF Matrix Collection
2D Finite Difference (Burgers flux)
The purpose of this is to analyze the importance of numerical methods for PDEs, and applications sparse array theory into these method, through the form of benchmarks. This paticular benchmark analyzes the use of the Lax–Friedrichs method for solving nonlinear hyberbolic PDEs, with numerical stability and accuracy not seen in FTCS. This benchmark will run a simulation using both Lax–Friedrichs and analyze core concepts such as numerical stability, conservation law consistency, etc.
Input generators (1)
Finite Difference Data Generator
The finite difference generator uses a finite difference grid of500 by 500 cells, matching roughly the scale of areal finite difference problem, Norris/torso3 from UF Matrix Collection
Coupled Cluster Singles and Doubles (CCSD)
Computes T1 and T2 amplitudes for CCSD. Ported from the CTF (Cyclops Tensor Framework) CCSD reference implementation
Input generators (1)
CCSD Input Generator
| Inputs are generated using the same deterministic pseudorandom fill as the C++ CTF reference (ccsd.cxx): canonical antisymmetric elements are set to ((flat_index * multiplier + tensor_id) % 13077) / 13077 - 0.5, then reflected via antisymmetry. This exactly reproduces the C++ reference output | T | = 380638. |
Conjugate Gradient Iterative Solver
Solves sparse symmetric positive definite linear systems with CG.
Input generators (2)
Conjugate Gradient Test Data Generator
Inlined matrices from the CG pytest examples.
Conjugate Gradient SuiteSparse Data Generator
Accesses and prepares symmetric positive definite matrices from SuiteSparse for conjugate gradient.
CANDECOMP/PARAFAC (CP) Decomposition via Alternating Least Squares
Computes the CP decomposition using Alternating Least Squares (ALS). Factorizes an N-D tensor X into factor matrices such that: $X \approx \sum_{r=1}^{R} \lambda_r \cdot a_r \circ b_r \circ …$ where $\circ$ denotes the outer product, R is the rank, and $\lambda$ are the weights. Handwritten code based on the standard CP-ALS algorithm from Kolda and Bader (2009).
Input generators (2)
Factorizable Tensor for CP Decomposition
Generating small factorizable tensors by creating random factor matrices
and reconstructing the tensor from them (tensor should decompose easily
with low reconstruction error).
FROSTT Sparse Tensor Generator for CP-ALS
Real sparse tensors downloaded from FROSTT (frostt.io), factorized directly. No dense reconstruction check is performed since these tensors are stored in genuinely sparse (COO) form.
FastSV Algorithm
The FastSV algorithm is a graph algorithm used to find the connected components for a simple graph. This algorithm introduces several optimizations that allow for faster convergence to a solution compared to the SV algorithm it is based on, specifically through modifications to the tree hooking and termination condition.
Input generators (3)
FastSV Test Input Generator
Small deterministic FastSV examples with reference labels.
FastSV Input Generator
Input generator for FastSV connected-components benchmarks.
FastSV GAP Input Generator
Input GAP generator for FastSV connected-components benchmarks.
Floyd-Warshall
The Floyd-Warshall algorithm computes the shortest paths between every pair of vertices in a weighted directed graph.
Input generators (2)
Floyd-Warshall Test Input Generator
Small deterministic Floyd-Warshall examples.
Floyd-Warshall Input Generator
Data is collected from the SuiteSparse Matrix Collection and standard benchmark graph datasets, with sparse adjacency matrices converted into unweighted all-pairs shortest path inputs. This generator uses real-world networks, including the Chesapeake road network and soc-tribes network from the Network Repository.
4-Clique Counting
4-clique Counting: A 4-clique must contain 6 edges that connect all 4 vertices. The einsum does the following: for a given vertex i, checks for existence of 3 edges to 3 other vertices, then checks for existence of 3 edges between those 3 vertices. This constitutes a 4-clique. Divide by 24 to avoid overcounting. These methods are implemented using the property that multiplying a graph’s adjacency matrix by itself n times yields the number of walks of length n that begin at the vertex denoted by the row label and end at the vertex denoted by the column label.
Input generators (3)
4-Clique Count Test Input Generator
Small deterministic 4-clique-count examples.
4-Clique Count Input Generator
Input generator for 4-clique counting benchmarks.
4-Clique Count GAP Input Generator
Input GAP generator for 4-clique counting benchmarks.
Graph Convolutional Network Inference
Computes a 2-layer Graph Convolutional Network forward pass: h1 = ReLU(adjacency @ features @ weights1 + bias1) output = adjacency @ h1 @ weights2 + bias2 Implementation based on Scorch (Yan et al., 2024).
Input generators (3)
GCN Test Input Generator
Small inlined GCN forward-pass examples.
Graph Convolutional Network Weights
Generates random weights for a 2-layer Graph Convolutional Network.
Open Graph Benchmark GCN Inputs
Loads full OGB node-property graphs for 2-layer GCN inference.
Graph Convolutional Network Inference
Benchmarks 2-layer GCN training loop (forward, backward, weight updates).
Each iteration: Forward pass: Z1 = A @ X H1_pre = Z1 @ W1 + b1 H1 = ReLU(H1_pre) Z2 = A @ H1 Y = Z2 @ W2 + b2
Backward pass (MSE loss):
dY = (2/N) * (Y - T)
dW2 = Z2.T @ dY
db2 = sum(dY, axis=0)
dZ2 = dY @ W2.T
dH1 = A.T @ dZ2
dH1_pre = dH1 * (H1_pre > 0)
dW1 = Z1.T @ dH1_pre
db1 = sum(dH1_pre, axis=0)
Weight updates:
W1 = W1 - lr * dW1
b1 = b1 - lr * db1
W2 = W2 - lr * dW2
b2 = b2 - lr * db2
Input generators (3)
GCN Backward Test Input Generator
Small inlined GCN training examples.
Graph Convolutional Network Weights
Generates random weights for a 2-layer Graph Convolutional Network.
Open Graph Benchmark GCN Backward Inputs
Loads full OGB node-property graphs for 2-layer GCN training.
GMRES Iterative Solver
This code is implements the GMRES algorithm for solving indefinite and non-symmetric linear systems. The algorithm follows the Arnoldi iteration process where a Krylov matrix is maintained at each iteration. Starting with an initial guess and the residual for that guess, the matrix A is dot producted with the previous residual to obtain the next basis vector. This algorithm also uses a similar method to Gram-Schmidt to ensure that the Kyrlov matrix is orthogonal. I also maintain an upper Hessenberg matrix which keeps track of the dot products between different basis vectors and the norm of the new basis vector. The Hessenberg matrix follows the property: Q_n * A = Q_(n+1) * H_n where Q is the Krylov matrix. This matrix allows for a simplified least squares problem to be solved at each iteration so that the residual is minimized at each step. My implementation restarts the Kyrlov matrix every 50 iterations and will end when the current residual / initial residual is less than the tolerance level.
Input generators (2)
GMRES Test Data Generator
Inlined matrices and seeded systems from the GMRES pytest examples.
GMRES SuiteSparse Data Generator
Accesses and prepares sparse matrices from SuiteSparse for GMRES.
High-Order SVD (Tucker Decomposition)
This code implements the Tucker Decomposition or HOSVD algorithm for decomposing high-order tensors into a core-tensor that can be projected onto factor matrices along each mode. A typical 3D tensor will have 3 modes (row, column, and frontal) and thus 3 factor matrices. The algorithm starts by finding the initial factor matrices by performing SVD on matrix unfoldings along each mode. Certain columns in these factor matrices are selected based on the ranks parameter. Then, the algorithm iteratively updates each factor matrix by projecting the original tensor onto other factor matrices. The iteration continues until max iterations is reached or the change in factor matrices becomes insignificant. The resulting factor matrices and the core tensor are returned by the benchmark function.
Input generators (3)
Dense Low-Rank HOSVD Input Generator
Generates dense low-rank tensors using random factor matrices.
Sparse Low-Rank HOSVD Input Generator
Generates sparse low-rank tensors using random factor matrices.
FROSTT Sparse Tensor Generator for HOSVD
Real sparse tensors downloaded from FROSTT (frostt.io), decomposed directly. No dense reconstruction check is performed since these tensors are stored in genuinely sparse (COO) form.
Preconditioned Conjugate Gradient (Jacobi)
Hand-written code modelling the algorithm structure outlined in https://www.netlib.org/templates/templates.pdf Page 13.
Input generators (1)
Jacobi CG SuiteSparse Data Generator
Data collected from SuiteSparse Matrix Collection consisting of symmetric positive definite matrices, particularly those with a low convergence criteria.
Jacobi Iterative Solver
Solves linear systems using the Jacobi iterative method.
Input generators (2)
Jacobi Test Data Generator
Inlined matrices from the Jacobi pytest examples.
Jacobi SuiteSparse Data Generator
Accesses and prepares symmetric positive definite matrices from SuiteSparse.
Johnson-Lindenstrauss Approximate Nearest Neighbor
Benchmarks Johnson-Lindenstrauss projection followed by k-nearest-neighbor ranking in projected space.
Input generators (4)
JL Projection Test Input Generator
Small JL approximate nearest-neighbor example.
JL Projection Input Generator
Generates uniformly random data/query matrices and sparse random projection matrices for JL approximate nearest-neighbor.
JL ANN OpenML Generator
Loads OpenML image datasets for JL approximate nearest-neighbor.
JL ANN Netflix Generator
Loads Netflix Prize ratings for JL approximate nearest-neighbor.
1D Finite Difference (Linear Advection flux)
The purpose of this is to analyze the importance of numerical methods for PDEs, and applications sparse array theory into these method, through the form of benchmarks. This paticular benchmark analyzes the use of the Lax–Friedrichs method for solving nonlinear hyberbolic PDEs, with numerical stability and accuracy not seen in FTCS. This benchmark will run a simulation using both Lax–Friedrichs and analyze core concepts such as numerical stability, conservation law consistency, etc.
Input generators (1)
Finite Difference Data Generator
The finite difference generator uses a finite difference grid of500 by 500 cells, matching roughly the scale of areal finite difference problem, Norris/torso3 from UF Matrix Collection
2D Finite Difference (Linear Advection flux)
The purpose of this is to analyze the importance of numerical methods for PDEs, and applications sparse array theory into these method, through the form of benchmarks. This paticular benchmark analyzes the use of the Lax–Friedrichs method for solving nonlinear hyberbolic PDEs, with numerical stability and accuracy not seen in FTCS. This benchmark will run a simulation using both Lax–Friedrichs and analyze core concepts such as numerical stability, conservation law consistency, etc.
Input generators (1)
Finite Difference Data Generator
The finite difference generator uses a finite difference grid of500 by 500 cells, matching roughly the scale of areal finite difference problem, Norris/torso3 from UF Matrix Collection
LSQR Iterative Solver
Hand written code based on the algorithm defined in Paige and Saunders’ LSQR paper. Implementation structure was also based around the work of Michael Friedlander and Dominique Orban.
Input generators (2)
LSQR Test Data Generator
Inlined matrices from the LSQR pytest examples.
LSQR SuiteSparse Data Generator
Data collected from SuiteSparse Matrix Collection consisting of square and rectangular matrices. Following the methodology of Paige and Saunders the problems span a range of convergence criteria from well-conditioned to extremely ill-conditioned.
MRI Edge Detection
What does this code do: This code implements a masked edge detection algorithm on a 2D MRI image. The benchmark performs boolean threshold mask operations using t1=75% and t2=80% thresholds and a Region-of-Interest (ROI) mask.
Input generators (2)
Masked MRI Edge Test Data Generator
Small deterministic masked MRI examples.
Masked MRI Edge Data Generator
Data Generation: I used MRI image data from this Kaggle set: https://www.kaggle.com/navoneel/brain-mri-images-for-brain-tumor-detection . I used a constant edge threshold of 150.0 with all of the images that I used.
Markov Clustering Algorithm
Computes Markov Clustering on a given sparse adjacency matrix. Handwritten code based on the implementation from GuyAllard on github
Input generators (2)
MCL Test Data Generator
Small MCL examples with expected cluster counts.
MCL SuiteSparse Data Generator
Data collected from SuiteSparse Matrix Collection consisting of sparse adjacency matrices used to evaluate graph clustering performance.
Sobel Operator Edge Detection
What does this code do: This code implements a simple edge detection algorithm on a 2D MRI image. The algorithm computes the gradients in the X and Y directions using the concept of a Sobel operator, which is a common method for edge detection. The sobel operator was recreated using array shifts that account for sparse patterns. The magnitude of the gradients is computed and then masked with a threshold to produce a binary edge map.
Input generators (2)
MRI Sobel Edge Test Input Generator
Small deterministic Sobel edge examples with reference outputs.
MRI Sobel Edge Data Generator
Data Generation: I used MRI image data from this Kaggle set: https://www.kaggle.com/navoneel/brain-mri-images-for-brain-tumor-detection . I used a constant edge threshold of 150.0 with all of the images that I used.
Google Page Rank Algorithm
The out-degree of the adjacency is found by summing columns, giving us the number of outbound links per page. If out-degree is not 0, we divide by k (the number of outbound links). If out-degree is 0, that means the node had no links, so we distribute it evenly among all nodes to preserve probability mass. We then run iteration multiple times so that the PageRank vector converges to its theoretical stationary value.
Input generators (3)
PageRank Test Input Generator
Small deterministic PageRank examples.
PageRank Input Generator
Input generator for PageRank benchmarks.
PageRank GAP Input Generator
Input GAP generator for PageRank benchmarks.
Particle Simulation
Benchmark implementation for Particule_Simulation_Algorithm using sparse array operations. This benchmark evaluates performance characteristics and numerical properties.
Input generators (4)
Particle Simulation Test Input Generator
Small deterministic particle simulation examples using the CS267-style repulsive force parameters: cutoff 0.01, softening 0.0001 from the CS267 min_r = cutoff / 100 constant, dt 0.0005, G 1.0, and scalar mass tensor 0.01.
Synthetic Berkeley CS267 Particle Generator
Generates synthetic initial conditions for particle simulation benchmarks. The force parameters follow the Berkeley CS267 homework constants where available: cutoff 0.01, softening 0.0001 as the benchmark name for CS267 min_r = cutoff / 100, dt 0.0005, and a scalar mass tensor 0.01; G 1.0 is used as the benchmark unit scale.
ETH EWAP Particle Simulation Generator
Loads ETH EWAP pedestrian trajectories as particle initial conditions. EWAP supplies positions and velocities only, so this generator uses the same CS267-style repulsive parameters as the synthetic dataset: cutoff 0.01, softening 0.0001, dt 0.0005, G 1.0, and scalar mass tensor 0.01.
Particle Simulation Real Dataset Generator
Loads real-world initial conditions for particle simulation benchmarks. NEMO datasets use source mass columns, unscaled archive coordinates, Newtonian gravity with G 1.0 in N-body units, dt 1/32, softening 0.05, and source-scale cutoffs selected for the benchmark datasets.
Preconditioned Conjugate Gradient (Block Jacobi)
Hand-written code modelling the algorithm structure outlined in https://www.netlib.org/templates/templates.pdf Page 13.
Input generators (1)
Block Jacobi CG SuiteSparse Data Generator
Data collected from SuiteSparse Matrix Collection consisting of symmetric positive definite matrices, particularly those with a low convergence criteria.
Random Projections for k-means Clustering
Labels points into k clusters.
Input generators (3)
Random Projection k-means Data Generator
Test points for this benchmark were created manually.
RP k-means OpenML Generator
Loads OpenML image datasets for RP k-means clustering.
RP k-means Netflix Generator
Loads Netflix Prize ratings for RP k-means clustering.
Simply Connected Components
Computes the simply connected components of a directed graph using label propagation.
Input generators (3)
Connected Components Test Input Generator
Small deterministic connected-components examples.
Connected Components Input Generator
Input generator for connected components benchmarks.
Connected Components GAP Input Generator
Input GAP generator for connected components benchmarks.
SLICOT Linear Systems — Backward Euler
SLICOT identity-E linear model-reduction ODE.
Input generators (1)
SLICOT Model-Reduction ODE
Loads SLICOT model-reduction problems without explicit E matrices, preserving stored sparse matrices, treating E as the identity, and defaulting missing B to a normalized single-input vector.
SLICOT DAE BDF
Fixed-step BDF2 for SLICOT DAEs with LU factors from the generator.
Input generators (2)
DAE Test Data Generator
Inlined descriptor systems for DAE solver correctness tests.
SLICOT DAE Data Generator
Loads SLICOT descriptor-system benchmarks for implicit DAE solvers.
SLICOT Linear Systems — Forward Euler
SLICOT identity-E linear model-reduction ODE.
Input generators (1)
SLICOT Model-Reduction ODE
Loads SLICOT model-reduction problems without explicit E matrices, preserving stored sparse matrices, treating E as the identity, and defaulting missing B to a normalized single-input vector.
SLICOT Linear Systems — RK4
SLICOT identity-E linear model-reduction ODE.
Input generators (1)
SLICOT Model-Reduction ODE
Loads SLICOT model-reduction problems without explicit E matrices, preserving stored sparse matrices, treating E as the identity, and defaulting missing B to a normalized single-input vector.
Subgraph Matching Algorithm using einsum
Benchmarks subgraph matching algorithms using einsum operations.
Input generators (5)
Subgraph Matching Test Inputs
Small labeled graph queries.
Subgraph G-CARE Generator (Human)
Transforms the G-CARE dataset to the input of subgraph matching algorithms.
Subgraph G-CARE Generator (AIDS)
Transforms the G-CARE dataset to the input of subgraph matching algorithms.
Subgraph G-CARE Generator (LUBM80)
Transforms the G-CARE dataset to the input of subgraph matching algorithms.
Subgraph G-CARE Generator (YAGO)
Transforms the G-CARE dataset to the input of subgraph matching algorithms.
Tensorized Minimax Tic-Tac-Toe
What does this code do: Implement a fully tensorized, non-recursive minimax search over a tic-tac-toe game. Game states are represented as tensors. Game state is represented as S[n, i, j, p] of shape (N, 3, 3, 2) where n indexes boards, i,j are board positions and p is the player channel. Given any board state within the game, it should return the result of the game.
Input generators (1)
Fixed Boards for testing.
These tests covering end-game, mid-game, and early gamethrough using various minimax at different depths.
Transitive Closure
Computes the transitive closure of a directed graph using fixed-point iteration. The algorithm initializes the adjacency matrix with the identity, then iteratively applies the closure operation using sparse matrix operations until convergence. This enables reachability queries.
Input generators (3)
Transitive Closure Input Generator
Input generator for transitive closure benchmarks.
Transitive Closure Test Input Generator
Small deterministic transitive closure examples.
Transitive Closure GAP Input Generator
Input GAP generator for transitive closure benchmarks.
diBELLA Transitive Reduction Algorithm
Iterative transitive reduction on a sparse overlap graph, following the diBELLA reduction step.
Input generators (2)
Transitive Reduction Test Inputs
Small test graphs with expected reduced edges.
Transitive Reduction GAP Input Generator
Input GAP generator for transitive reduction benchmarks.
Triangle Counting
Triangle Counting: Given adjacency matrix A, # triangles = trace(A^3) // 6. This counts the number of walks of length 3 that start at vertex i and end at vertex i, which is exactly a triangle. Divide by 6 to avoid overcounting. These methods are implemented using the property that multiplying a graph’s adjacency matrix by itself n times yields the number of walks of length n that begin at the vertex denoted by the row label and end at the vertex denoted by the column label.
Input generators (3)
Triangle Count Test Input Generator
Small deterministic triangle-count examples.
Triangle Count Input Generator
Input generator for triangle counting benchmarks.
Triangle Count GAP Input Generator
Input GAP generator for triangle counting benchmarks.