Using extensive numerical simulation of the Navier–Stokes equations, we study the transition from the Darcy’s law for slow flow of fluids through a disordered porous medium to the nonlinear flow regime in which the effect of inertia cannot be neglected. The porous medium is represented by two-dimensional slices of a three-dimensional image of a sandstone. We study the problem over wide ranges of porosity and the Reynolds number, as well as two types of boundary conditions, and compute essential features of fluid flow, namely, the strength of the vorticity, the effective permeability of the pore space, the frictional drag, and the relationship between the macroscopic pressure gradient
The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite interval
- NSF-PAR ID:
- 10468074
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Discrete & Computational Geometry
- Volume:
- 71
- Issue:
- 1
- ISSN:
- 0179-5376
- Format(s):
- Medium: X Size: p. 67-94
- Size(s):
- ["p. 67-94"]
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract and the fluid velocity$${\varvec{\nabla }}P$$ v . The results indicate that when the Reynolds number Re is low enough that the Darcy’s law holds, the magnitude of the vorticity is nearly zero. As Re increases, however, so also does$$\omega _z$$ , and its rise from nearly zero begins at the same Re at which the Darcy’s law breaks down. We also show that a nonlinear relation between the macroscopic pressure gradient and the fluid velocity$$\omega _z$$ v , given by, , provides accurate representation of the numerical data, where$$-{\varvec{\nabla }}P=(\mu /K_e)\textbf{v}+\beta _n\rho |\textbf{v}|^2\textbf{v}$$ and$$\mu$$ are the fluid’s viscosity and density,$$\rho$$ is the effective Darcy permeability in the linear regime, and$$K_e$$ is a generalized nonlinear resistance. Theoretical justification for the relation is presented, and its predictions are also compared with those of the Forchheimer’s equation.$$\beta _n$$ -
Abstract We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution
and the corresponding noiseless output distribution$$p_{\text {noisy}}$$ shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmark$$p_{\text {ideal}}$$ F that measures this correlation behaves as , where$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$ is the probability of error per circuit location and$$\epsilon $$ s is the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution and the uniform distribution$$p_{\text {noisy}}$$ decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {unif}}$$ . In other words, although at least one local error occurs with probability$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$ , the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$1-F$$ . Thus, the “white-noise approximation” is meaningful when$$O(F\epsilon \sqrt{s})$$ , a quadratically weaker condition than the$$\epsilon \sqrt{s} \ll 1$$ requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$\epsilon s\ll 1$$ , which corresponds to only$$s \ge \Omega (n\log (n))$$ logarithmic depth circuits, and if, additionally, the inverse error rate satisfies , which is needed to ensure errors are scrambled faster than$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$ F decays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds. -
Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:
Certifying that a list of
n integers has no 3-SUM solution can be done in Merlin–Arthur time . Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n)$$ time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$ and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$ time).$$\tilde{O}(n^{1.5})$$ Counting the number of
k -cliques with total edge weight equal to zero in ann -node graph can be done in Merlin–Arthur time (where$${\tilde{O}}(n^{\lceil k/2\rceil })$$ ). For odd$$k\ge 3$$ k , this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm -edge graph can be done in Merlin–Arthur time . Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only count$${\tilde{O}}(m)$$ k -cliques in unweighted graphs, and had worse running times for smallk .Computing the All-Pairs Shortest Distances matrix for an
n -node graph can be done in Merlin–Arthur time . Note this is optimal, as the matrix can have$$\tilde{O}(n^2)$$ nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\Omega (n^2)$$ nondeterministic time algorithm.$$\tilde{O}(n^{2.94})$$ Certifying that an
n -variablek -CNF is unsatisfiable can be done in Merlin–Arthur time . We also observe an algebrization barrier for the previous$$2^{n/2 - n/O(k)}$$ -time Merlin–Arthur protocol of R. Williams [CCC’16] for$$2^{n/2}\cdot \textrm{poly}(n)$$ SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol for$$\#$$ k -UNSAT running in time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.$$2^{n/2}/n^{\omega (1)}$$ Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time
. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{4n/5}\cdot \textrm{poly}(n)$$ time.$$2^{2n/3}\cdot \textrm{poly}(n)$$ n integers can be done in Merlin–Arthur time , improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{n/3}\cdot \textrm{poly}(n)$$ time.$$2^{0.49991n}\cdot \textrm{poly}(n)$$ -
Abstract Matrix reduction is the standard procedure for computing the persistent homology of a filtered simplicial complex with
m simplices. Its output is a particular decomposition of the total boundary matrix, from which the persistence diagrams and generating cycles are derived. Persistence diagrams are known to vary continuously with respect to their input, motivating the study of their computation for time-varying filtered complexes. Computing persistence dynamically can be reduced to maintaining a valid decomposition under adjacent transpositions in the filtration order. Since there are such transpositions, this maintenance procedure exhibits limited scalability and is often too fine for many applications. We propose a coarser strategy for maintaining the decomposition over a 1-parameter family of filtrations. By reduction to a particular longest common subsequence problem, we show that the minimal number of decomposition updates$$O(m^2)$$ d can be found in time and$$O(m \log \log m)$$ O (m ) space, and that the corresponding sequence of permutations—which we call aschedule —can be constructed in time. We also show that, in expectation, the storage needed to employ this strategy is actually sublinear in$$O(d m \log m)$$ m . Exploiting this connection, we show experimentally that the decrease in operations to compute diagrams across a family of filtrations is proportional to the difference between the expected quadratic number of states and the proposed sublinear coarsening. Applications to video data, dynamic metric space data, and multiparameter persistence are also presented. -
Abstract Let
be an elliptically fibered$$X\rightarrow {{\mathbb {P}}}^1$$ K 3 surface, admitting a sequence of Ricci-flat metrics collapsing the fibers. Let$$\omega _{i}$$ V be a holomorphicSU (n ) bundle overX , stable with respect to . Given the corresponding sequence$$\omega _i$$ of Hermitian–Yang–Mills connections on$$\Xi _i$$ V , we prove that, ifE is a generic fiber, the restricted sequence converges to a flat connection$$\Xi _i|_{E}$$ . Furthermore, if the restriction$$A_0$$ is of the form$$V|_E$$ for$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$ n distinct points , then these points uniquely determine$$q_j\in E$$ .$$A_0$$