More Like this

1. Distributed Graph Diameter Approximation

   https://doi.org/10.3390/a13090216  

   Ceccarello, Matteo; Pietracaprina, Andrea; Pucci, Geppino; Upfal, Eli (September 2020, Algorithms)

   null (Ed.)

   We present an algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. In order to be efficient in terms of both time and space, our algorithm is based on a decomposition strategy which partitions the graph into disjoint clusters of bounded radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; most importantly, for a large family of graphs, it features a round complexity asymptotically smaller than the one exhibited by a natural approximation algorithm based on the state-of-the-art Δ-stepping SSSP algorithm, which is its only practical, linear-space competitor in the distributed setting. We complement our theoretical findings with a proof-of-concept experimental analysis on large benchmark graphs, which suggests that our algorithm may attain substantial improvements in terms of running time compared to the aforementioned competitor, while featuring, in practice, a similar approximation ratio. 

   more » « less
2. Communication-Efficient ∆-Stepping for Distributed Computing Systems

   https://doi.org/10.1109/WiMob58348.2023.10187809  

   Zhang, Haomeng; Xie, Junfei; Zhang, Xinyu (June 2023, 2023 19th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob))

   This paper considers the single source shortest path (SSSP) problem, which is the key for many applications such as navigation, mapping, routing, and social networking. Existing SSSP algorithms are designed mostly for shared-memory systems. Nevertheless, with the prevalence of diverse smart devices like drones, there is a growing interest in deploying SSSP algorithms over distributed computing systems so that they can run efficiently onboard of smart devices via Mobile Ad Hoc Computing or at the network edges via Mobile Edge Computing. In this paper, we introduce a communication-efficient ∆-stepping algorithm for distributed computing systems. The proposed algorithm is featured by 1) a message coordination architecture for reducing message exchanges between workers, 2) a pruning technique for reducing redundant computations, and 3) an aggregation technique for further reducing message exchanges when communication delay is significant. Theoretical analyses and experimental studies on real-world graph datasets demonstrate the promising performance of proposed algorithm. 

   more » « less
3. Efficient Variable Time-stepping Adaptive DLN Algorithms for the Allen-Cahn Equation

   https://doi.org/10.1007/s10915-025-02980-4  

   Chen, Yiming; Luo, Dianlun; Pei, Wenlong; Xing, Yulong (July 2025, Journal of Scientific Computing)

   Abstract We consider a family of variable time-stepping Dahlquist-Liniger-Nevanlinna (DLN) schemes, which is unconditionally non-linear stable and second order accurate, for the Allen-Cahn equation. The finite element methods are used for the spatial discretization. For the non-linear term, we combine the DLN scheme with two efficient temporal algorithms: partially implicit modified algorithm and scalar auxiliary variable algorithm. For both approaches, we prove the unconditional, long-term stability of the model energy under any arbitrary time step sequence. Moreover, we provide rigorous error analysis for the partially implicit modified algorithm with variable time-stepping. Efficient time-adaptive algorithms based on these schemes are also proposed. Several one- and two-dimensional numerical tests are presented to verify the properties of the proposed time-adaptive DLN methods. 

   more » « less
4. Brief Announcement: A Parallel (Δ, Γ)-Stepping Algorithm for the Constrained Shortest Path Problem

   https://doi.org/10.1145/3490148.3538555  

   Bahreini, Tayebeh; Fisher, Nathan; Grosu, Daniel (July 2022, SPAA '22: Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures)

   We design a parallel algorithm for the Constrained Shortest Path (CSP) problem. The CSP problem is known to be NP-hard and there exists a pseudo-polynomial time sequential algorithm that solves it. To design the parallel algorithm, we extend the techniques used in the design of the Δ-stepping algorithm for the single-source shortest paths problem. 

   more » « less
5. High-order accurate implicit-explicit time-stepping schemes for wave equations on overset grids

   https://doi.org/10.1016/j.jcp.2024.113513  

   Carson, Allison M; Banks, Jeffrey W; Henshaw, William D; Schwendeman, Donald W (January 2025, Journal of Computational Physics)

   New implicit and implicit-explicit time-stepping methods for the wave equation in second-order form are described with application to two and three-dimensional problems discretized on overset grids. The implicit schemes are single step, three levels in time, and based on the modified equation approach. Second and fourth-order accurate schemes are developed and they incorporate upwind dissipation for stability on overset grids. The fully implicit schemes are useful for certain applications such as the WaveHoltz algorithm for solving Helmholtz problems where very large time-steps are desired. Some wave propagation problems are geometrically stiff due to localized regions of small grid cells, such as grids needed to resolve fine geometric features, and for these situations the implicit time-stepping scheme is combined with an explicit scheme: the implicit scheme is used for component grids containing small cells while the explicit scheme is used on the other grids such as background Cartesian grids. The resulting partitioned implicit-explicit scheme can be many times faster than using an explicit scheme everywhere. The accuracy and stability of the schemes are studied through analysis and numerical computations. 

   more » « less