Search for: All records

This paper introduces EXaCTz, a parallel algorithm that concurrently preserves extremum graphs and contour trees in lossy-compressed scalar field data. While error-bounded lossy compression is essential for large-scale scientific simulations and workflows, existing topology-preserving methods suffer from (1) a significant throughput disparity, where topology correction speeds are on the order of MB/s, lagging orders of magnitude behind compression speeds on the order of GB/s, (2) limited support for diverse topological descriptors, and (3) a lack of theoretical convergence bounds. To address these challenges, EXaCTz introduces a high-performance, bounded-iteration algorithm that enforces topological consistency by deriving targeted edits for decompressed data. Unlike prior methods that rely on explicit topology reconstruction, EXaCTz enforces consistent min/max neighbors of all vertices, along with global ordering among critical points. As such, the algorithm enforces consistent critical-point classification, saddle extremum connectivity, and the preservation of merge/split events. We theoretically prove the convergence of our algorithm, bounded by the longest path in a vulnerability graph that characterizes potential cascading effects during correction. Experiments on real-world datasets show that EXaCTz achieves a single-GPU throughput of up to 4.52 GB/s, outperforming the state-of-the-art contour-tree-preserving method (Gorski et al.) by up to 213x (with a single-core CPU implementation for fair comparison) and 3,285x (with a single-GPU version). In distributed environments, EXaCTz scales to 128 GPUs with 55.6\% efficiency (compared with 6.4\% for a naive parallelization), processing datasets of up to 512 GB in under 48 seconds and achieving an aggregate correction throughput of up to 32.69 GB/s. 

Abstract Network data are ubiquitous in the real world, capturing pairwise and high-order relations among objects. We introduce a class of measure-theoretic network objects, termed partitioned measure networks, that generalize many existing representations of network data, including graphs, hypergraphs and augmented graphs (i.e. graphs whose nodes are associated with categorical classes). We then propose a metric, the partitioned network distance, between partitioned measure networks, which extends both the Gromov-Wasserstein distance for graphs and the co-optimal transport distance for hypergraphs. By characterizing the geometry of the space of partitioned measure networks, we provide a unified theoretical treatment of generalized network structures encompassing both pairwise and higher-order relations. In particular, we show that this metric endows the space with an Alexandrov geometry of non-negative curvature and leverages this structure to define gradients for certain functionals commonly encountered in geometric data analysis. We further extend our framework to incorporate node-level label information and derive efficient computational schemes for utilizing the partitioned network distance in practice. Equipped with these theoretical and computational advances, we demonstrate the utility of our framework across diverse applications, including hypergraph alignment, clustering and dictionary learning from ensemble data, multi-omics alignment, as well as multiscale network alignment. 

Hypergraphs have seen widespread application in network and data science communities in recent years.We present a survey of recentwork to construct auxiliary structures fromhypergraphs—specifically simplicial, relative, and chain complexes—that can be used to build homology theories for hypergraphs. We define and describe nine different constructions and their associated homology theories.We discuss some interesting properties of each homology theory to show how various hypergraph properties imply properties of the homology groups. We also include discussion of functoriality for several of the homology theories. Finally, we provide a series of illustrative examples by computing many of these homology theories for small hypergraphs to show the variability of the methods and build intuition. 

Scientific simulations and observations are generating massive volumes of time-varying vector field data, posing significant challenges for long-term storage and data transmission. Lossy compression is widely regarded as a promising approach for reducing data volume, as lossless methods typically achieve only modest compression ratios and therefore provide limited reduction. However, directly applying existing lossy compression techniques to time-varying vector fields can introduce undesirable distortions in critical-point trajectories, which encode essential structural properties of the underlying field. In this work, we present an efficient lossy compression framework that exactly preserves all critical-point trajectories in time-varying vector fields. Our contributions are threefold. First, we extend the theory of critical-point preservation from the spatial domain to space-time and develop a corresponding compression framework to guarantee trajectory preservation. Second, we introduce a semi-Lagrangian predictor to more effectively exploit spatiotemporal correlations in advection-dominated regions, and integrate it with the classical Lorenzo predictor to further improve compression efficiency. Third, we evaluate the proposed approach against state-of-the-art lossy and lossless compressors on four real-world scientific datasets. Experimental results show that our method achieves compression ratios of up to 124.48X while effectively preserving all critical-point trajectories. This compression ratio is up to 56.07X higher than the best-performing lossless compressors. In contrast, none of the existing lossy compressors can preserve all critical-point trajectories at comparable compression ratios. 

Lossy compression, widely used by scientists to reduce data from simulations, experiments, and observations, can distort features of interest even under bounded error. Such distortions may compromise downstream analyses and lead to incorrect scientific conclusions in applications such as combustion and cosmology. This paper presents a distributed and parallel algorithm for correcting topological features, specifically, piecewise linear Morse–Smale segmentations (PLMSS), which decompose the domain into monotone regions labeled by their corresponding local minima and maxima. While a single-GPU algorithm (MSz) exists for PLMSS correction after compression, no methodology has been developed that scales beyond a single GPU for extreme-scale data. We identify the key bottleneck in scaling PLMSS correction as the parallel computation of integral paths, a communication-intensive computation that is notoriously difficult to scale. Instead of explicitly computing and correcting integral paths, our algorithm simplifies MSz by preserving steepest ascending and descending directions across all locations, thereby minimizing interprocess communication while introducing negligible additional storage overhead. With this simplified algorithm and relaxed synchronization, our method achieves over 90% parallel efficiency on 128 GPUs on the Perlmutter supercomputer for real-world datasets. 

Electrification of vehicle fleets has advanced significantly in recent years to achieve net-zero greenhouse gas (GHG) emissions. As a cost-effective strategy, shared charging facilities are increasingly used by public and private sectors. For example, the unoccupied time of a bus charging station can be leveraged to charge other electric vehicles (EVs). This shared usage model presents both opportunities and challenges for organizations considering transitions to electrified mobility. It is especially difficult when considering the variability in daily fleet operations and the availability of charging infrastructures. This paper presents a bi-objective optimization model designed to strategically guide the replacement of vehicle fleets with EV. The model aligns the spatial- temporal dynamics of vehicle routes with the availability of shared charging facilities. It is particularly relevant for organizations managing vehicle fleets that are considering a strategic transition to EVs, with the goals of minimizing GHG emissions from fuel consumption and vehicle idling, and reducing operational delays (e.g. detour and charging time for the EV fleet). We applied this model to the University of Utah campus fleet, utilizing shared charging facilities operated by the Utah Transit Authority. The results demonstrate effective strategies for replacing vehicles with varied operational characteristics, offering detailed plans and schedules that balance GHG emission reductions with operational efficiency. Additionally, we conducted a sensitivity analysis to assess the effects of different battery sizes, station disruptions, and traffic delays on the model’s outcomes and a feasibility analysis to prioritize the replacement of high-utility vehicles. Our research provides a foundation for fleet agencies to develop strategic EV replacement plans that consider multiple goals and leverage shared charging infrastructure, ultimately leading to optimized charging facility utilization and reduced maintenance costs. These strategies support more efficient, reliable, and sustainable operations in urban fleet systems.