亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We describe a `discretize-then-relax' strategy to globally minimize integral functionals over functions $u$ in a Sobolev space satisfying prescribed Dirichlet boundary conditions. The strategy applies whenever the integral functional depends polynomially on $u$ and its derivatives, even if it is nonconvex. The `discretize' step uses a bounded finite-element scheme to approximate the integral minimization problem with a convergent hierarchy of polynomial optimization problems over a compact feasible set, indexed by the decreasing size $h$ of the finite-element mesh. The `relax' step employs sparse moment-SOS relaxations to approximate each polynomial optimization problem with a hierarchy of convex semidefinite programs, indexed by an increasing relaxation order $\omega$. We prove that, as $\omega\to\infty$ and $h\to 0$, solutions of such semidefinite programs provide approximate minimizers that converge in $L^p$ to the global minimizer of the original integral functional if this is unique. We also report computational experiments that show our numerical strategy works well even when technical conditions required by our theoretical analysis are not satisfied.

In this work we present a new WENO b-spline based quasi-interpolation algorithm. The novelty of this construction resides in the application of the WENO weights to the b-spline functions, that are a partition of unity, instead to the coefficients that multiply the b-spline functions of the spline. The result obtained conserves the smoothness of the original spline and presents adaption to discontinuities in the function. Another new idea that we introduce in this work is the use of different base weight functions from those proposed in classical WENO algorithms. Apart from introducing the construction of the new algorithms, we present theoretical results regarding the order of accuracy obtained at smooth zones and close to the discontinuity, as well as theoretical considerations about how to design the new weight functions. Through a tensor product strategy, we extend our results to several dimensions. In order to check the theoretical results obtained, we present an extended battery of numerical experiments in one, two and tree dimensions that support our conclussions.

Given a property (graph class) $\Pi$, a graph $G$, and an integer $k$, the \emph{$\Pi$-completion} problem consists in deciding whether we can turn $G$ into a graph with the property $\Pi$ by adding at most $k$ edges to $G$. The $\Pi$-completion problem is known to be NP-hard for general graphs when $\Pi$ is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem %when $\Pi$ is the class of proper interval graphs (PIG) within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.

We study the problem of reconstructing the Faber--Schauder coefficients of a continuous function $f$ from discrete observations of its antiderivative $F$. Our approach starts with formulating this problem through piecewise quadratic spline interpolation. We then provide a closed-form solution and an in-depth error analysis. These results lead to some surprising observations, which also throw new light on the classical topic of quadratic spline interpolation itself: They show that the well-known instabilities of this method can be located exclusively within the final generation of estimated Faber--Schauder coefficients, which suffer from non-locality and strong dependence on the initial value and the given data. By contrast, all other Faber--Schauder coefficients depend only locally on the data, are independent of the initial value, and admit uniform error bounds. We thus conclude that a robust and well-behaved estimator for our problem can be obtained by simply dropping the final-generation coefficients from the estimated Faber--Schauder coefficients.

For terminal value problems of fractional differential equations of order $\alpha \in (0,1)$ that use Caputo derivatives, shooting methods are a well developed and investigated approach. Based on recently established analytic properties of such problems, we develop a new technique to select the required initial values that solves such shooting problems quickly and accurately. Numerical experiments indicate that this new proportional secting technique converges very quickly and accurately to the solution. Run time measurements indicate a speedup factor of between 4 and 10 when compared to the standard bisection method.

Given a surface $\Sigma$ equipped with a set $P$ of marked points, we consider the triangulations of $\Sigma$ with vertex set $P$. The flip-graph of $\Sigma$ whose vertices are these triangulations, and whose edges correspond to flipping arcs appears in the study of moduli spaces and mapping class groups. We consider the number of geodesics in the flip-graph of $\Sigma$ between two triangulations as a function of their distance. We show that this number grows exponentially provided the surface has enough topology, and that in the remaining cases the growth is polynomial.

In this work, we first develop a general mesoscopic multiple-relaxation-time lattice Boltzmann (MRT-LB) model for the two-dimensional diffusion equation with the constant diffusion coefficient and source term, where the D2Q5 (five discrete velocities in two-dimensional space) lattice structure is considered. Then we exactly derive the equivalent macroscopic finite-difference scheme of the MRT-LB model. Additionally, we also propose a proper MRT-LB model for the diffusion equation with a linear source term, and obtain an equivalent macroscopic six-level finite-difference scheme. After that, we conduct the accuracy and stability analysis of the finite-difference scheme and the mesoscopic MRT-LB model. It is found that at the diffusive scaling, both of them can achieve a fourth-order accuracy in space based on the Taylor expansion. The stability analysis also shows that they are both unconditionally stable. Finally, some numerical experiments are conducted, and the numerical results are also consistent with our theoretical analysis.

This paper describes a purely functional library for computing level-$p$-complexity of Boolean functions, and applies it to two-level iterated majority. Boolean functions are simply functions from $n$ bits to one bit, and they can describe digital circuits, voting systems, etc. An example of a Boolean function is majority, which returns the value that has majority among the $n$ input bits for odd $n$. The complexity of a Boolean function $f$ measures the cost of evaluating it: how many bits of the input are needed to be certain about the result of $f$. There are many competing complexity measures but we focus on level-$p$-complexity -- a function of the probability $p$ that a bit is 1. The level-$p$-complexity $D_p(f)$ is the minimum expected cost when the input bits are independent and identically distributed with Bernoulli($p$) distribution. We specify the problem as choosing the minimum expected cost of all possible decision trees -- which directly translates to a clearly correct, but very inefficient implementation. The library uses thinning and memoization for efficiency and type classes for separation of concerns. The complexity is represented using (sets of) polynomials, and the order relation used for thinning is implemented using polynomial factorisation and root-counting. Finally we compute the complexity for two-level iterated majority and improve on an earlier result by J.~Jansson.

An $n$-vertex $m$-edge graph is \emph{$k$-vertex connected} if it cannot be disconnected by deleting less than $k$ vertices. After more than half a century of intensive research, the result by [Li et al. STOC'21] finally gave a \emph{randomized} algorithm for checking $k$-connectivity in near-optimal $\widehat{O}(m)$ time. (We use $\widehat{O}(\cdot)$ to hide an $n^{o(1)}$ factor.) Deterministic algorithms, unfortunately, have remained much slower even if we assume a linear-time max-flow algorithm: they either require at least $\Omega(mn)$ time [Even'75; Henzinger Rao and Gabow, FOCS'96; Gabow, FOCS'00] or assume that $k=o(\sqrt{\log n})$ [Saranurak and Yingchareonthawornchai, FOCS'22]. We show a \emph{deterministic} algorithm for checking $k$-vertex connectivity in time proportional to making $\widehat{O}(k^{2})$ max-flow calls, and, hence, in $\widehat{O}(mk^{2})$ time using the deterministic max-flow algorithm by [Brand et al. FOCS'23]. Our algorithm gives the first almost-linear-time bound for all $k$ where $\sqrt{\log n}\le k\le n^{o(1)}$ and subsumes up to a sub polynomial factor the long-standing state-of-the-art algorithm by [Even'75] which requires $O(n+k^{2})$ max-flow calls. Our key technique is a deterministic algorithm for terminal reduction for vertex connectivity: given a terminal set separated by a vertex mincut, output either a vertex mincut or a smaller terminal set that remains separated by a vertex mincut. We also show a deterministic $(1+\epsilon)$-approximation algorithm for vertex connectivity that makes $O(n/\epsilon^2)$ max-flow calls, improving the bound of $O(n^{1.5})$ max-flow calls in the exact algorithm of [Gabow, FOCS'00]. The technique is based on Ramanujan graphs.

Metric spaces $(X, d)$ are ubiquitous objects in mathematics and computer science that allow for capturing (pairwise) distance relationships $d(x, y)$ between points $x, y \in X$. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "$k$-wise distance relationships" $d(x_1, \ldots, x_k)$ among points $x_1, \ldots, x_k \in X$ for $k > 2$. To that end, G\"{a}hler (Math. Nachr., 1963) (and perhaps others even earlier) defined $k$-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality $d(x_1, x_2) \leq d(x_1, y) + d(y, x_2)$ to the "simplex inequality" $d(x_1, \ldots, x_k) \leq \sum_{i=1}^k d(x_1, \ldots, x_{i-1}, y, x_{i+1}, \ldots, x_k)$. (The definition holds for any fixed $k \geq 2$, and a $2$-metric space is just a (standard) metric space.) In this work, we introduce strong $k$-metric spaces, $k$-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary $k$-metrics, which generalize $\ell_p$ metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain $k$-metrics, which generalize shortest path metrics (and capture all strong $k$-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fr\'{e}chet embedding (isometric embedding into $\ell_{\infty}$) and isometric embedding of all tree metrics into $\ell_1$. We also study relationships between families of (strong) $k$-metrics, and show that natural quantities, like simplex volume, are strong $k$-metrics.