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

The geodesic edge center of a polygon is a point c inside the polygon that minimizes the maximum geodesic distance from c to any edge of the polygon, where geodesic distance is the shortest path distance inside the polygon. We give a linear-time algorithm to find a geodesic edge center of a simple polygon. This improves on the previous O(n log n) time algorithm by Lubiw and Naredla [European Symposium on Algorithms, 2021]. The algorithm builds on an algorithm to find the geodesic vertex center of a simple polygon due to Pollack, Sharir, and Rote [Discrete & Computational Geometry, 1989] and an improvement to linear time by Ahn, Barba, Bose, De Carufel, Korman, and Oh [Discrete & Computational Geometry, 2016]. The geodesic edge center can easily be found from the geodesic farthest-edge Voronoi diagram of the polygon. Finding that Voronoi diagram in linear time is an open question, although the geodesic nearest edge Voronoi diagram (the medial axis) can be found in linear time. As a first step of our geodesic edge center algorithm, we give a linear-time algorithm to find the geodesic farthest-edge Voronoi diagram restricted to the polygon boundary.

A linear inference is a valid inequality of Boolean algebra in which each variable occurs at most once on each side. In this work we leverage recently developed graphical representations of linear formulae to build an implementation that is capable of more efficiently searching for switch-medial-independent inferences. We use it to find four `minimal' 8-variable independent inferences and also prove that no smaller ones exist; in contrast, a previous approach based directly on formulae reached computational limits already at 7 variables. Two of these new inferences derive some previously found independent linear inferences. The other two (which are dual) exhibit structure seemingly beyond the scope of previous approaches we are aware of; in particular, their existence contradicts a conjecture of Das and Strassburger. We were also able to identify 10 minimal 9-variable linear inferences independent of all the aforementioned inferences, comprising 5 dual pairs, and present applications of our implementation to recent `graph logics'.

The paper focuses on a new error analysis of a class of mixed FEMs for stationary incompressible magnetohydrodynamics with the standard inf-sup stable velocity-pressure space pairs to Navier-Stokes equations and the N\'ed\'elec's edge element for the magnetic field. The methods have been widely used in various numerical simulations in the last several decades, while the existing analysis is not optimal due to the strong coupling of system and the pollution of the lower-order N\'ed\'elec's edge approximation in analysis. In terms of a newly modified Maxwell projection we establish new and optimal error estimates. In particular, we prove that the method based on the commonly-used Taylor-Hood/lowest-order N\'ed\'elec's edge element is efficient and the method provides the second-order accuracy for numerical velocity. Two numerical examples for the problem in both convex and nonconvex polygonal domains are presented. Numerical results confirm our theoretical analysis.

In 1973, Lemmens and Seidel posed the problem of determining the maximum number of equiangular lines in $\mathbb{R}^r$ with angle $\arccos(\alpha)$ and gave a partial answer in the regime $r \leq 1/\alpha^2 - 2$. At the other extreme where $r$ is at least exponential in $1/\alpha$, recent breakthroughs have led to an almost complete resolution of this problem. In this paper, we introduce a new method for obtaining upper bounds which unifies and improves upon previous approaches, thereby bridging the gap between the aforementioned regimes, as well as significantly extending or improving all previously known bounds when $r \geq 1/\alpha^2 - 2$. Our method is based on orthogonal projection of matrices with respect to the Frobenius inner product and it also yields the first extension of the Alon-Boppana theorem to dense graphs, with equality for strongly regular graphs corresponding to $\binom{r+1}{2}$ equiangular lines in $\mathbb{R}^r$. Applications of our method in the complex setting will be discussed as well.

Assessing predictive models can be challenging. Modelers must navigate a wide array of evaluation methodologies implemented with incompatible interfaces across multiple packages which may give different or even contradictory results, while ensuring that their chosen approach properly estimates the performance of their model when generalizing to new observations. Assessing models fit to spatial data can be particularly difficult, given that model errors may exhibit spatial autocorrelation, model predictions are often aggregated to multiple spatial scales by end users, and models are often tasked with generalizing into spatial regions outside the boundaries of their initial training data. The waywiser package for the R language attempts to make assessing spatial models easier by providing an ergonomic toolkit for model evaluation tasks, with functions for multiple assessment methodologies sharing a unified interface. Functions from waywiser share standardized argument names and default values, making the user-facing interface simple and easy to learn. These functions are additionally designed to be easy to integrate into a wide variety of modeling workflows, accepting standard classes as inputs and returning size- and type-stable outputs, ensuring that their results are of consistent and predictable data types and dimensions. Additional features make it particularly easy to use waywiser along packages and workflows in the tidymodels ecosystem.

We develop a simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as messages failing with constant probability or nodes calling a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a $G(n,p)$ random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of $r$ rounds occurs with probability at most $\exp(-\Omega(r))$. We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal $\Theta(n \log\log n)$ [Karp, Shenker, Schindelhauer, V\"ocking (FOCS 2000)] to $\Theta(n \log n)$. We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the $\Theta(n \log\log n)$ message complexity.

A knot $K$ in a directed graph $D$ is a strongly connected component of size at least two such that there is no arc $(u,v)$ with $u \in V(K)$ and $v\notin V(K)$. Given a directed graph $D=(V,E)$, we study Knot-Free Vertex Deletion (KFVD), where the goal is to remove the minimum number of vertices such that the resulting graph contains no knots. This problem naturally emerges from its application in deadlock resolution since knots are deadlocks in the OR-model of distributed computation. The fastest known exact algorithm in literature for KFVD runs in time $\mathcal{O}^\star(1.576^n)$. In this paper, we present an improved exact algorithm running in time $\mathcal{O}^\star(1.4549^n)$, where $n$ is the number of vertices in $D$. We also prove that the number of inclusion wise minimal knot-free vertex deletion sets is $\mathcal{O}^\star(1.4549^n)$ and construct a family of graphs with $\Omega(1.4422^n)$ minimal knot-free vertex deletion sets

We consider network games where a large number of agents interact according to a network sampled from a random network model, represented by a graphon. By exploiting previous results on convergence of such large network games to graphon games, we examine a procedure for estimating unknown payoff parameters, from observations of equilibrium actions, without the need for exact network information. We prove smoothness and local convexity of the optimization problem involved in computing the proposed estimator. Additionally, under a notion of graphon parameter identifiability, we show that the optimal estimator is globally unique. We present several examples of identifiable homogeneous and heterogeneous parameters in different classes of linear quadratic network games with numerical simulations to validate the proposed estimator.

Complex-variable matrix optimization problems (CMOPs) in Frobenius norm emerge in many areas of applied mathematics and engineering applications. In this letter, we focus on solving CMOPs by iterative methods. For unconstrained CMOPs, we prove that the gradient descent (GD) method is feasible in the complex domain. Further, in view of reducing the computation complexity, constrained CMOPs are solved by a projection gradient descent (PGD) method. The theoretical analysis shows that the PGD method maintains a good convergence in the complex domain. Experiment results well support the theoretical analysis.

Krylov subspace methods are extensively used in scientific computing to solve large-scale linear systems. However, the performance of these iterative Krylov solvers on modern supercomputers is limited by expensive communication costs. The $s$-step strategy generates a series of $s$ Krylov vectors at a time to avoid communication. Asymptotically, the $s$-step approach can reduce communication latency by a factor of $s$. Unfortunately, due to finite-precision implementation, the step size has to be kept small for stability. In this work, we tackle the numerical instabilities encountered in the $s$-step GMRES algorithm. By choosing an appropriate polynomial basis and block orthogonalization schemes, we construct a communication avoiding $s$-step GMRES algorithm that automatically selects the optimal step size to ensure numerical stability. To further maximize communication savings, we introduce scaled Newton polynomials that can increase the step size $s$ to a few hundreds for many problems. An initial step size estimator is also developed to efficiently choose the optimal step size for stability. The guaranteed stability of the proposed algorithm is demonstrated using numerical experiments. In the process, we also evaluate how the choice of polynomial and preconditioning affects the stability limit of the algorithm. Finally, we show parallel scalability on more than 14,000 cores in a distributed-memory setting. Perfectly linear scaling has been observed in both strong and weak scaling studies with negligible communication costs.