More Like this

1. Online Spanners in Metric Spaces

   Bhore, Sujoy ; Filtser, Arnold ; Khodabandeh, Hadi ; Toth, Csaba D. ( September 2022 , 30th Annual European Symposium on Algorithms (ESA 2022))

   Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂-norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)-spanner algorithm with competitive ratio O_d(ε^{-d} log n), improving the previous bound of O_d(ε^{-(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{-3/2}logε^{-1}log n), by comparing the online spanner with an instance-optimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{-d}) lower bound for the competitive ratio for online (1+ε)-spanner algorithms in ℝ^d under the L₁-norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k-1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{-1}logε^{-1})⋅ n^{1+1/k} edges and O(ε^{-1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the trade-off among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)-spanner for ultrametrics with O(ε^{-1}logε^{-1})⋅ n edges and O(ε^{-2}) lightness. 

   more » « less
2. Online Spanners in Metric Spaces

   Bhore, Sujoy ; Filtser, Arnold ; Khodabandeh, Hadi ; Toth, Csaba D. ( September 2022 , Proc. 30th Annual European Symposium on Algorithms (ESA))

   Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂-norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)-spanner algorithm with competitive ratio O_d(ε^{-d} log n), improving the previous bound of O_d(ε^{-(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{-3/2}logε^{-1}log n), by comparing the online spanner with an instance-optimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{-d}) lower bound for the competitive ratio for online (1+ε)-spanner algorithms in ℝ^d under the L₁-norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k-1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{-1}logε^{-1})⋅ n^{1+1/k} edges and O(ε^{-1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the trade-off among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)-spanner for ultrametrics with O(ε^{-1}logε^{-1})⋅ n edges and O(ε^{-2}) lightness. 

   more » « less
3. Using stereo XPTV to determine cylindrical particle distribution and velocity in a binary fluidized bed

   https://doi.org/10.1002/aic.16485  

   Chen, Xi ; Zhong, Wenqi ; Heindel, Theodore J. ( December 2018 , AIChE Journal)

   Nonspherical particles are commonly found when processing biomass or municipal solid waste. In this study, cylindrical particles are used as generic nonspherical particles and are co‐fluidized with small spherical particles. X‐ray particle tracking velocimetry is used to track the three‐dimensional particle position and velocity of a single tagged cylindrical particle over a long time period in the binary fluidized bed. The effects of superficial gas velocity (u_f), cylindrical particle mass fraction (α), particle sphericity (Φ), and bed material size on the cylindrical tracer particle location and velocity are investigated. Overall, the cylindrical particles are found in the near‐wall region more often than in the bed center region. Increasing the superficial gas velocityu_fprovide a slight improvement in the uniformity of the vertical and horizontal distributions. Increasing the cylindrical particle mass fractionαcauses the bed mixing conditions to transition from complete mixing into partial mixing. © 2018 American Institute of Chemical EngineersAIChE J, 65: 520–535, 2019

    

   more » « less
4. Deep learning closure models for large-eddy simulation of flows around bluff bodies

   https://doi.org/10.1017/jfm.2023.446  

   Sirignano, Justin ; MacArt, Jonathan F. ( July 2023 , Journal of Fluid Mechanics)

   Near-wall flow simulation remains a central challenge in aerodynamics modelling: Reynolds-averaged Navier–Stokes predictions of separated flows are often inaccurate, and large-eddy simulation (LES) can require prohibitively small near-wall mesh sizes. A deep learning (DL) closure model for LES is developed by introducing untrained neural networks into the governing equations and training in situ for incompressible flows around rectangular prisms at moderate Reynolds numbers. The DL-LES models are trained using adjoint partial differential equation (PDE) optimization methods to match, as closely as possible, direct numerical simulation (DNS) data. They are then evaluated out-of-sample – for aspect ratios, Reynolds numbers and bluff-body geometries not included in the training data – and compared with standard LES models. The DL-LES models outperform these models and are able to achieve accurate LES predictions on a relatively coarse mesh (downsampled from the DNS mesh by factors of four or eight in each Cartesian direction). We study the accuracy of the DL-LES model for predicting the drag coefficient, near-wall and far-field mean flow, and resolved Reynolds stress. A crucial challenge is that the LES quantities of interest are the steady-state flow statistics; for example, a time-averaged velocity component $\langle {u}_i\rangle (x) = \lim _{t \rightarrow \infty } ({1}/{t}) \int _0^t u_i(s,x)\, {\rm d}s$ . Calculating the steady-state flow statistics therefore requires simulating the DL-LES equations over a large number of flow times through the domain. It is a non-trivial question whether an unsteady PDE model with a functional form defined by a deep neural network can remain stable and accurate on $t \in [0, \infty )$ , especially when trained over comparatively short time intervals. Our results demonstrate that the DL-LES models are accurate and stable over long time horizons, which enables the estimation of the steady-state mean velocity, fluctuations and drag coefficient of turbulent flows around bluff bodies relevant to aerodynamics applications. 

   more » « less
5. Connections between nonrotating, slowly rotating, and rapidly rotating turbulent convection transport scalings

   Aurnou, J.M. ( July 2020 , Physical review research)

   null (Ed.)

   In this study, we investigate and develop scaling laws as a function of external non-dimensional control parameters for heat and momentum transport for non-rotating, slowly rotating and rapidly rotating turbulent convection systems, with the end goal of forging connections and bridging the various gaps between these regimes. Two perspectives are considered, one where turbulent convection is viewed from the standpoint of an applied temperature drop across the domain and the other with a viewpoint in terms of an applied heat flux. While a straightforward transformation exist between the two perspectives indicating equivalence, it is found the former provides a clear set of connections that bridge between the three regimes. Our generic convection scalings, based upon an Inertial-Archimedean balance, produce the classic diffusion-free scalings for the non-rotating limit (NRL) and the slowly rotating limit (SRL). This is characterized by a free-falling fluid parcel on the global scale possessing a thermal anomaly on par with the temperature drop across the domain. In the rapidly rotating limit (RRL), the generic convection scalings are based on a Coriolis-Inertial-Archimedean (CIA) balance, along with a local fluctuating-mean advective temperature balance. This produces a scenario in which anisotropic fluid parcels attain a thermal wind velocity and where the thermal anomalies are greatly attenuated compared to the total temperature drop. We find that turbulent scalings may be deduced simply by consideration of the generic non-dimensional transport parameters --- local Reynolds $Re_\ell = U \ell /\nu$; local P\'eclet $Pe_\ell = U \ell /\kappa$; and Nusselt number $Nu = U \vartheta/(\kappa \Delta T/H)$ --- through the selection of physically relevant estimates for length $\ell$, velocity $U$ and temperature scales $\vartheta$ in each regime. Emergent from the scaling analyses is a unified continuum based on a single external control parameter, the convective Rossby number\JMA{,} $\RoC = \sqrt{g \alpha \Delta T / 4 \Omega^2 H}$, that strikingly appears in each regime by consideration of the local, convection-scale Rossby number $\Rol=U/(2\Omega \ell)$. Thus we show that $\RoC$ scales with the local Rossby number $\Rol$ in both the slowly rotating and the rapidly rotating regimes, explaining the ubiquity of $\RoC$ in rotating convection studies. We show in non-, slowly, and rapidly rotating systems that the convective heat transport, parameterized via $Pe_\ell$, scales with the total heat transport parameterized via the Nusselt number $Nu$. Within the rapidly-rotating limit, momentum transport arguments generate a scaling for the system-scale Rossby number, $Ro_H$, that, recast in terms of the total heat flux through the system, is shown to be synonymous with the classical flux-based `CIA' scaling, $Ro_{CIA}$. These, in turn, are then shown to asymptote to $Ro_H \sim Ro_{CIA} \sim \RoC^2$, demonstrating that these momentum transport scalings are identical in the limit of rapidly rotating turbulent heat transfer. 

   more » « less