We consider a \emph{family} $(P_\omega)_{\omega \in \Omega}$ of elliptic second order differential operators on a domain $U_0 \subset \mathbb{R}^m$ whose coefficients depend on the space variable $x \in U_0$ and on $\omega \in \Omega,$ a probability space. We allow the coefficients $a_{ij}$ of $P_\omega$ to have jumps over a fixed interface $\Gamma \subset U_0$ (independent of $\omega \in \Omega$). We obtain polynomial in the norms of the coefficients estimates on the norm of the solution $u_\omega$ to the equation $P_\omega u_\omega = f$ with transmission and mixed boundary conditions (we consider ``sign-changing'' problems as well). In particular, we show that, if $f$ and the coefficients $a_{ij}$ are smooth enough and follow a log-normal-type distribution, then the map $\Omega \ni \omega \to \|u_\omega\|_{H^{k+1}(U_0)}$ is in $L^p(\Omega)$, for all $1 \le p < \infty$. The same is true for the norms of the inverses of the resulting operators. We expect our estimates to be useful in Uncertainty Quantification.
相關內容
We consider a matching problem in a bipartite graph $G=(A\cup B,E)$ where nodes in $A$ are agents having preferences in partial order over their neighbors, while nodes in $B$ are objects without preferences. We propose a polynomial-time combinatorial algorithm based on LP duality that finds a maximum matching or assignment in $G$ that is popular among all maximum matchings, if there exists one. Our algorithm can also be used to achieve a trade-off between popularity and cardinality by imposing a penalty on unmatched nodes in $A$. We also provide an $O^*(|E|^k)$ algorithm that finds an assignment whose unpopularity margin is at most $k$; this algorithm is essentially optimal, since the problem is $\mathsf{NP}$-complete and $\mathsf{W}_l[1]$-hard with parameter $k$. We also prove that finding a popular assignment of minimum cost when each edge has an associated binary cost is $\mathsf{NP}$-hard, even if agents have strict preferences. By contrast, we propose a polynomial-time algorithm for the variant of the popular assignment problem with forced/forbidden edges. Finally, we present an application in the context of housing markets.
We introduce a novel formulation for the evolution of parametric curves by anisotropic curve shortening flow in ${\mathbb R}^d$, $d\geq2$. The reformulation hinges on a suitable manipulation of the parameterization's tangential velocity, leading to a strictly parabolic differential equation. Moreover, the derived equation is in divergence form, giving rise to a natural variational numerical method. For a fully discrete finite element approximation based on piecewise linear elements we prove optimal error estimates. Numerical simulations confirm the theoretical results and demonstrate the practicality of the method.
We show that the problem of counting the number of $n$-variable unate functions reduces to the problem of counting the number of $n$-variable monotone functions. Using recently obtained results on $n$-variable monotone functions, we obtain counts of $n$-variable unate functions up to $n=9$. We use an enumeration strategy to obtain the number of $n$-variable balanced monotone functions up to $n=7$. We show that the problem of counting the number of $n$-variable balanced unate functions reduces to the problem of counting the number of $n$-variable balanced monotone functions, and consequently, we obtain the number of $n$-variable balanced unate functions up to $n=7$. Using enumeration, we obtain the numbers of equivalence classes of $n$-variable balanced monotone functions, unate functions and balanced unate functions up to $n=6$. Further, for each of the considered sub-class of $n$-variable monotone and unate functions, we also obtain the corresponding numbers of $n$-variable non-degenerate functions.
We present a new and straightforward derivation of a family $\mathcal{F}(h,\tau)$ of exponential splittings of Strang-type for the general linear evolutionary equation with two linear components. One component is assumed to be a time-independent, unbounded operator, while the other is a bounded one with explicit time dependence. The family $\mathcal{F}(h,\tau)$ is characterized by the length of the time-step $h$ and a continuous parameter $\tau$, which defines each member of the family. It is shown that the derivation and error analysis follows from two elementary arguments: the variation of constants formula and specific quadratures for integrals over simplices. For these Strang-type splittings, we prove their convergence which, depending on some commutators of the relevant operators, may be of first or second order. As a result, error bounds appear in terms of commutator bounds. Based on the explicit form of the error terms, we establish the influence of $\tau$ on the accuracy of $\mathcal{F}(h,\tau)$, allowing us to investigate the optimal value of $\tau$. This simple yet powerful approach establishes the connection between exponential integrators and splitting methods. Furthermore, the present approach can be easily applied to the derivation of higher-order splitting methods under similar considerations. Needless to say, the obtained results also apply to Strang-type splittings in the case of time independent-operators. To complement rigorous results, we present numerical experiments with various values of $\tau$ based on the linear Schr\"odinger equation.
We consider the problem of fitting a centered ellipsoid to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to \infty$ with $n/d^2 \to \alpha > 0$. It has been conjectured that this problem is, with high probability, satisfiable (SAT; that is, there exists an ellipsoid passing through all $n$ points) for $\alpha < 1/4$, and unsatisfiable (UNSAT) for $\alpha > 1/4$. In this work we give a precise analytical argument, based on the non-rigorous replica method of statistical physics, that indeed predicts a SAT/UNSAT transition at $\alpha = 1/4$, as well as the shape of a typical fitting ellipsoid in the SAT phase (i.e., the lengths of its principal axes). Besides the replica method, our main tool is the dilute limit of extensive-rank "HCIZ integrals" of random matrix theory. We further study different explicit algorithmic constructions of the matrix characterizing the ellipsoid. In particular, we show that a procedure based on minimizing its nuclear norm yields a solution in the whole SAT phase. Finally, we characterize the SAT/UNSAT transition for ellipsoid fitting of a large class of rotationally-invariant random vectors. Our work suggests mathematically rigorous ways to analyze fitting ellipsoids to random vectors, which is the topic of a companion work.
We discuss the numerical solution of initial value problems for $\varepsilon^2\,\varphi''+a(x)\,\varphi=0$ in the highly oscillatory regime, i.e., with $a(x)>0$ and $0<\varepsilon\ll 1$. We analyze and implement an approximate solution based on the well-known WKB-ansatz. The resulting approximation error is of magnitude $\mathcal{O}(\varepsilon^{N})$ where $N$ refers to the truncation order of the underlying asymptotic series. When the optimal truncation order $N_{opt}$ is chosen, the error behaves like $\mathcal{O}(\varepsilon^{-2}\exp(-c\varepsilon^{-1}))$ with some $c>0$.
The alpha complex is a fundamental data structure from computational geometry, which encodes the topological type of a union of balls $B(x; r) \subset \mathbb{R}^m$ for $x\in S$, including a weighted version that allows for varying radii. It consists of the collection of "simplices" $\sigma = \{x_0, ..., x_k \} \subset S$, which correspond to nomempty $(k + 1)$-fold intersections of cells in a radius-restricted version of the Voronoi diagram. Existing algorithms for computing the alpha complex require that the points reside in low dimension because they begin by computing the entire Delaunay complex, which rapidly becomes intractable, even when the alpha complex is of a reasonable size. This paper presents a method for computing the alpha complex without computing the full Delaunay triangulation by applying Lagrangian duality, specifically an algorithm based on dual quadratic programming that seeks to rule simplices out rather than ruling them in.
We consider the problem of counting 4-cycles ($C_4$) in an undirected graph $G$ of $n$ vertices and $m$ edges (in bipartite graphs, 4-cycles are also often referred to as $\textit{butterflies}$). There have been a number of previous algorithms for this problem based on sorting the graph by degree and using randomized hash tables. These are appealing in theory due to compact storage and fast access on average. But, the performance of hash tables can degrade unpredictably and are also vulnerable to adversarial input. We develop a new simpler algorithm for counting $C_4$ requiring $O(m\bar\delta(G))$ time and $O(n)$ space, where $\bar \delta(G) \leq O(\sqrt{m})$ is the $\textit{average degeneracy}$ parameter introduced by Burkhardt, Faber \& Harris (2020). It has several practical improvements over previous algorithms; for example, it is fully deterministic, does not require any sorting of the input graph, and uses only addition and array access in its inner loops. To the best of our knowledge, all previous efficient algorithms for $C_4$ counting have required $\Omega(m)$ space in addition to storing the input graph. Our algorithm is very simple and easily adapted to count 4-cycles incident to each vertex and edge. Empirical tests demonstrate that our array-based approach is $4\times$ -- $7\times$ faster on average compared to popular hash table implementations.
The grounded Laplacian matrix $\LL_{-S}$ of a graph $\calG=(V,E)$ with $n=|V|$ nodes and $m=|E|$ edges is a $(n-s)\times (n-s)$ submatrix of its Laplacian matrix $\LL$, obtained from $\LL$ by deleting rows and columns corresponding to $s=|S| \ll n $ ground nodes forming set $S\subset V$. The smallest eigenvalue of $\LL_{-S}$ plays an important role in various practical scenarios, such as characterizing the convergence rate of leader-follower opinion dynamics, with a larger eigenvalue indicating faster convergence of opinion. In this paper, we study the problem of adding $k \ll n$ edges among all the nonexistent edges forming the candidate edge set $Q = (V\times V)\backslash E$, in order to maximize the smallest eigenvalue of the grounded Laplacian matrix. We show that the objective function of the combinatorial optimization problem is monotone but non-submodular. To solve the problem, we first simplify the problem by restricting the candidate edge set $Q$ to be $(S\times (V\backslash S))\backslash E$, and prove that it has the same optimal solution as the original problem, although the size of set $Q$ is reduced from $O(n^2)$ to $O(n)$. Then, we propose two greedy approximation algorithms. One is a simple greedy algorithm with an approximation ratio $(1-e^{-\alpha\gamma})/\alpha$ and time complexity $O(kn^4)$, where $\gamma$ and $\alpha$ are, respectively, submodularity ratio and curvature, whose bounds are provided for some particular cases. The other is a fast greedy algorithm without approximation guarantee, which has a running time $\tilde{O}(km)$, where $\tilde{O}(\cdot)$ suppresses the ${\rm poly} (\log n)$ factors. Numerous experiments on various real networks are performed to validate the superiority of our algorithms, in terms of effectiveness and efficiency.
We consider the two-pronged fork frame $F$ and the variety $\mathbf{Eq}(B_F)$ generated by its dual closure algebra $B_F$. We describe the finite projective algebras in $\mathbf{Eq}(B_F)$ and give a purely semantic proof that unification in $\mathbf{Eq}(B_F)$ is finitary and not unitary.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191