More Like this

1. Transport With Bimolecular Reactions in a Fracture‐Matrix System: Analytical Solutions With Applications to In Situ Chemical Oxidation

   https://doi.org/10.1029/2019WR024762  

   Arshadi, Masoud ; Rajaram, Harihar ( May 2019 , Water Resources Research)

   We present analytical solutions for transport with bimolecular reactions in a single fracture embedded within an infinite rock matrix. The fracture and matrix are initially assumed to contain one aqueous species (B) at a uniform concentration. A second aqueous species (A) is injected into the fracture and reacts with B and an additional immobile species (N) in the rock matrix. Under these conditions, moving reaction fronts form and propagate along the fracture and into the rock matrix. We employ a composite similarity variable involving two space variables to derive analytical solutions for all species concentrations and the geometry of reaction fronts in the fracture and matrix. The behavior of the reaction‐diffusion equations in the rock matrix is posed as a Stefan problem. For uniform advection in the fracture, our analytical solutions establish that the reaction fronts propagate as the square root of time in both the matrix and the fracture. Our analytical solutions agree very well with numerical simulations. We extend our analytical solutions to nonuniform flows in the fracture by invoking a travel‐time transformation. We present applications of our analytical solutions to in situ chemical oxidation of dense nonaqueous phase liquids in fractured rock, wherein an oxidant (A, e.g., permanganate) is injected through fractures and consumed by bimolecular reactions with dissolved dense nonaqueous phase liquids (B, e.g., trichloroethylene) and natural organic matter (N) in the fracture and rock matrix. Our analytical solutions are also relevant to a broad class of reactive transport problems in fracture‐matrix systems where moving reaction fronts occur.

    

   more » « less
2. Counting and Sampling Orientations on Chordal Graphs

   https://doi.org/10.1007/978-3-030-96731-4_29  

   Bezakova, Ivona ; Sun, Wenbo ( January 2022 , International Conference and Workshops on Algorithms and Computation (WALCOM))

   We study counting problems for several types of orientations of chordal graphs: source-sink-free orientations, sink-free orientations, acyclic orientations, and bipolar orientations, and, for the latter two, we also present linear-time uniform samplers. Counting sink-free, acyclic, or bipolar orientations are known to be #P-complete for general graphs, motivating our study on a restricted, yet well-studied, graph class. Our main focus is source-sink-free orientations, a natural restricted version of sink-free orientations related to strong orientations, which we introduce in this work. These orientations are intriguing, since despite their similarity, currently known FPRAS and sampling techniques (such as Markov chains or sink-popping) that apply to sink-free orientations do not seem to apply to source-sink-free orientations. We present fast polynomialtime algorithms counting these orientations on chordal graphs. Our approach combines dynamic programming with inclusion-exclusion (going two levels deep for source-sink-free orientations and one level for sinkfree orientations) throughout the computation. Dynamic programming counting algorithms can be typically used to produce a uniformly random sample. However, due to the negative terms of the inclusion-exclusion, the typical approach to obtain a polynomial-time sampling algorithm does not apply in our case. Obtaining such an almost uniform sampling algorithm for source-sink-free orientations in chordal graphs remains an open problem. Little is known about counting or sampling of acyclic or bipolar orientations, even on restricted graph classes. We design efficient (linear-time) exact uniform sampling algorithms for these orientations on chordal graphs. These algorithms are a byproduct of our counting algorithms, but unlike in other works that provide dynamic-programming-based samplers, we produce a random orientation without computing the corresponding count, which leads to a faster running time than the counting algorithm (since it avoids manipulation of large integers). 

   more » « less
3. Active subspace-based dimension reduction for chemical kinetics applications with epistemic uncertainty

   Vohra, M. ( March 2019 , Combustion and flame)

   We focus on an efficient approach for quantification of uncertainty in complex chemical reaction networks with a large number of uncertain parameters and input conditions. Parameter dimension reduction is accomplished by computing an active subspace that predominantly captures the variability in the quantity of interest (QoI). In the present work, we compute the active subspace for a H2/O2 mechanism that involves 19 chemical reactions, using an efficient iterative strategy. The active subspace is first computed for a 19-parameter problem wherein only the uncertainty in the pre-exponents of the individual reaction rates us considered. This is followed by the analysis of a 36-dimensional case wherein the activation energies and initial conditions are also considered uncertain. In both cases, a 1-dimensional active subspace is observed to capture the uncertainty in the QoI, which indicates enormous potential for efficient statistical analysis of complex chemical systems. In addition, we explore links between active subspaces and global sensitivity analysis, and exploit these links for identification of key contributors to the variability in the model response. 

   more » « less
4. Talya Eden, Saleet Mossel, Ronitt Rubinfeld, Sampling Multiple Edges Efficiently

   Eden, T. ; Mossel, S. ; Rubinfeld, R. ( January 2021 , RANDOM 2021)

   We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise ε-close to the uniform distribution, in an amortized-efficient fashion. We consider the adjacency list query model, where access to a graph G is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let n and m denote the number of vertices and edges of G, respectively. Eden and Rosenbaum provided upper and lower bounds of Θ^*(n/√ m) for sampling a single edge in general graphs (where O^*(⋅) suppresses poly(1/ε) and poly(log n) dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples q in advance, has an overall cost that is sublinear in q, namely, O^*(√ q ⋅(n/√ m)), which is strictly preferable to O^*(q⋅ (n/√ m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tětek and Thorup (arXiv, preprint) proved that this bound is essentially optimal. 

   more » « less
5. Sampling Multiple Edges Efficiently

   Eden, T. ; Mossel, S. ; Rubinfeld, R. ( January 2021 , Random)

   We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise ϵ-close to the uniform distribution, in an amortized-efficient fashion. We consider the adjacency list query model, where access to a graph G is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let n and m denote the number of vertices and edges of G, respectively. Eden and Rosenbaum provided upper and lower bounds of Θ∗(n/ √ m) for sampling a single edge in general graphs (where O ∗(·) suppresses poly(1/ϵ) and poly(log n) dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples q in advance, has an overall cost that is sublinear in q, namely, O∗(√ q · (n/ √ m)), which is strictly preferable to O∗(q · (n/ √ m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tětek and Thorup (arXiv, preprint) proved that this bound is essentially optimal. 

   more » « less