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

In [3] it was shown that four seemingly different algorithms for computing low-rank approximate solutions $X_j$ to the solution $X$ of large-scale continuous-time algebraic Riccati equations (CAREs) $0 = \mathcal{R}(X) := A^HX+XA+C^HC-XBB^HX $ generate the same sequence $X_j$ when used with the same parameters. The Hermitian low-rank approximations $X_j$ are of the form $X_j = Z_jY_jZ_j^H,$ where $Z_j$ is a matrix with only few columns and $Y_j$ is a small square Hermitian matrix. Each $X_j$ generates a low-rank Riccati residual $\mathcal{R}(X_j)$ such that the norm of the residual can be evaluated easily allowing for an efficient termination criterion. Here a new family of methods to generate such low-rank approximate solutions $X_j$ of CAREs is proposed. Each member of this family of algorithms proposed here generates the same sequence of $X_j$ as the four previously known algorithms. The approach is based on a block rational Arnoldi decomposition and an associated block rational Krylov subspace spanned by $A^H$ and $C^H.$ Two specific versions of the general algorithm will be considered; one will turn out to be a rediscovery of the RADI algorithm, the other one allows for a slightly more efficient implementation compared to the RADI algorithm (in case the Sherman-Morrision-Woodbury formula and a direct solver is used to solve the linear systems that occur). Moreover, our approach allows for adding more than one shift at a time.

The structured $\varepsilon$-stability radius is introduced as a quantity to assess the robustness of transient bounds of solutions to linear differential equations under structured perturbations of the matrix. This applies to general linear structures such as complex or real matrices with a given sparsity pattern or with restricted range and corange, or special classes such as Toeplitz matrices. The notion conceptually combines unstructured and structured pseudospectra in a joint pseudospectrum, allowing for the use of resolvent bounds as with unstructured pseudospectra and for structured perturbations as with structured pseudospectra. We propose and study an algorithm for computing the structured $\varepsilon$-stability radius. This algorithm solves eigenvalue optimization problems via suitably discretized rank-1 matrix differential equations that originate from a gradient system. The proposed algorithm has essentially the same computational cost as the known rank-1 algorithms for computing unstructured and structured stability radii. Numerical experiments illustrate the behavior of the algorithm.

In the $0$-Extension problem, we are given an edge-weighted graph $G=(V,E,c)$, a set $T\subseteq V$ of its vertices called terminals, and a semi-metric $D$ over $T$, and the goal is to find an assignment $f$ of each non-terminal vertex to a terminal, minimizing the sum, over all edges $(u,v)\in E$, the product of the edge weight $c(u,v)$ and the distance $D(f(u),f(v))$ between the terminals that $u,v$ are mapped to. Current best approximation algorithms on $0$-Extension are based on rounding a linear programming relaxation called the \emph{semi-metric LP relaxation}. The integrality gap of this LP, with best upper bound $O(\log |T|/\log\log |T|)$ and best lower bound $\Omega((\log |T|)^{2/3})$, has been shown to be closely related to the best quality of cut and flow vertex sparsifiers. We study a variant of the $0$-Extension problem where Steiner vertices are allowed. Specifically, we focus on the integrality gap of the same semi-metric LP relaxation to this new problem. Following from previous work, this new integrality gap turns out to be closely related to the quality achievable by cut/flow vertex sparsifiers with Steiner nodes, a major open problem in graph compression. Our main result is that the new integrality gap stays superconstant $\Omega(\log\log |T|)$ even if we allow a super-linear $O(|T|\log^{1-\varepsilon}|T|)$ number of Steiner nodes.

We introduce a strict saddle property for $\ell_p$ regularized functions, and propose an iterative reweighted $\ell_1$ algorithm to solve the $\ell_p$ regularized problems. The algorithm is guaranteed to converge only to local minimizers when randomly initialized. The strict saddle property is shown generic on these sparse optimization problems. Those analyses as well as the proposed algorithm can be easily extended to general nonconvex regularized problems.

SARRIGUREN, a new complete algorithm for SAT based on counting clauses (which is valid also for Unique-SAT and #SAT) is described, analyzed and tested. Although existing complete algorithms for SAT perform slower with clauses with many literals, that is an advantage for SARRIGUREN, because the more literals are in the clauses the bigger is the probability of overlapping among clauses, a property that makes the clause counting process more efficient. Actually, it provides a $O(m^2 \times n/k)$ time complexity for random $k$-SAT instances of $n$ variables and $m$ relatively dense clauses, where that density level is relative to the number of variables $n$, that is, clauses are relatively dense when $k\geq7\sqrt{n}$. Although theoretically there could be worst-cases with exponential complexity, the probability of those cases to happen in random $k$-SAT with relatively dense clauses is practically zero. The algorithm has been empirically tested and that polynomial time complexity maintains also for $k$-SAT instances with less dense clauses ($k\geq5\sqrt{n}$). That density could, for example, be of only 0.049 working with $n=20000$ variables and $k=989$ literals. In addition, they are presented two more complementary algorithms that provide the solutions to $k$-SAT instances and valuable information about number of solutions for each literal. Although this algorithm does not solve the NP=P problem (it is not a polynomial algorithm for 3-SAT), it broads the knowledge about that subject, because $k$-SAT with $k>3$ and dense clauses is not harder than 3-SAT. Moreover, the Python implementation of the algorithms, and all the input datasets and obtained results in the experiments are made available.

We prove discrete versions of the first and second Weber inequalities on $\boldsymbol{H}(\mathbf{curl})\cap\boldsymbol{H}(\mathrm{div}_{\eta})$-like hybrid spaces spanned by polynomials attached to the faces and to the cells of a polyhedral mesh. The proven hybrid Weber inequalities are optimal in the sense that (i) they are formulated in terms of $\boldsymbol{H}(\mathbf{curl})$- and $\boldsymbol{H}(\mathrm{div}_{\eta})$-like hybrid semi-norms designed so as to embed optimally (polynomially) consistent face penalty terms, and (ii) they are valid for face polynomials in the smallest possible stability-compatible spaces. Our results are valid on domains with general, possibly non-trivial topology. In a second part we also prove, within a general topological setting, related discrete Maxwell compactness properties.

We present approximation algorithms for the Fault-tolerant $k$-Supplier with Outliers ($\mathsf{F}k\mathsf{SO}$) problem. This is a common generalization of two known problems -- $k$-Supplier with Outliers, and Fault-tolerant $k$-Supplier -- each of which generalize the well-known $k$-Supplier problem. In the $k$-Supplier problem the goal is to serve $n$ clients $C$, by opening $k$ facilities from a set of possible facilities $F$; the objective function is the farthest that any client must travel to access an open facility. In $\mathsf{F}k\mathsf{SO}$, each client $v$ has a fault-tolerance $\ell_v$, and now desires $\ell_v$ facilities to serve it; so each client $v$'s contribution to the objective function is now its distance to the $\ell_v^{\text{th}}$ closest open facility. Furthermore, we are allowed to choose $m$ clients that we will serve, and only those clients contribute to the objective function, while the remaining $n-m$ are considered outliers. Our main result is a $\min\{4t-1,2^t+1\}$-approximation for the $\mathsf{F}k\mathsf{SO}$ problem, where $t$ is the number of distinct values of $\ell_v$ that appear in the instance. At $t=1$, i.e. in the case where the $\ell_v$'s are uniformly some $\ell$, this yields a $3$-approximation, improving upon the $11$-approximation given for the uniform case by Inamdar and Varadarajan [2020], who also introduced the problem. Our result for the uniform case matches tight $3$-approximations that exist for $k$-Supplier, $k$-Supplier with Outliers, and Fault-tolerant $k$-Supplier. Our key technical contribution is an application of the round-or-cut schema to $\mathsf{F}k\mathsf{SO}$. Guided by an LP relaxation, we reduce to a simpler optimization problem, which we can solve to obtain distance bounds for the "round" step, and valid inequalities for the "cut" step.

In this work, we study the Hermite interpolation on $n$-dimensional non-equally spaced, rectilinear grids over a field $\Bbbk $ of characteristic zero, given the values of the function at each point of the grid and the partial derivatives up to a maximum degree. First, we prove the uniqueness of the interpolating polynomial, and we further obtain a compact closed form that uses a single summation, irrespective of the dimensionality, which is algebraically simpler than the only alternative closed form for the $n$-dimensional classical Hermite interpolation [1]. We provide the remainder of the interpolation in integral form; we derive the ideal of the interpolation and express the interpolation remainder using only polynomial divisions, in the case of interpolating a polynomial function. Moreover, we prove the continuity of Hermite polynomials defined on adjacent $n$-dimensional grids, thus establishing spline behavior. Finally, we perform illustrative numerical examples to showcase the applicability and high accuracy of the proposed interpolant, in the simple case of few points, as well as hundreds of points on 3D-grids using a spline-like interpolation, which compares favorably to state-of-the-art spline interpolation methods.

Dirac delta distributionally sourced differential equations emerge in many dynamical physical systems from neuroscience to black hole perturbation theory. Most of these lack exact analytical solutions and are thus best tackled numerically. This work describes a generic numerical algorithm which constructs discontinuous spatial and temporal discretisations by operating on discontinuous Lagrange and Hermite interpolation formulae recovering higher order accuracy. It is shown by solving the distributionally sourced wave equation, which has analytical solutions, that numerical weak-form solutions can be recovered to high order accuracy by solving a first-order reduced system of ordinary differential equations. The method-of-lines framework is applied to the DiscoTEX algorithm i.e through discontinuous collocation with implicit-turned-explicit (IMTEX) integration methods which are symmetric and conserve symplectic structure. Furthermore, the main application of the algorithm is proved, for the first-time, by calculating the amplitude at any desired location within the numerical grid, including at the position (and at its right and left limit) where the wave- (or wave-like) equation is discontinuous via interpolation using DiscoTEX. This is shown, firstly by solving the wave- (or wave-like) equation and comparing the numerical weak-form solution to the exact solution. Finally, one shows how to reconstruct the scalar and gravitational metric perturbations from weak-form numerical solutions of a non-rotating black hole, which do not have known exact analytical solutions, and compare against state-of-the-art frequency domain results. One concludes by motivating how DiscoTEX, and related algorithms, open a promising new alternative Extreme-Mass-Ratio-Inspiral (EMRI)s waveform generation route via a self-consistent evolution for the gravitational self-force programme in the time-domain.

A set $S$ of vertices of a digraph $D$ is called an open neighbourhood locating-dominating set if every vertex in $D$ has an in-neighbour in $S$, and for every pair $u,v$ of vertices of $D$, there is a vertex in $S$ that is an in-neighbour of exactly one of $u$ and $v$. The smallest size of an open neighbourhood locating-dominating set of a digraph $D$ is denoted by $\gamma_{OL}(D)$. We study the class of digraphs $D$ whose only open neighbourhood locating-dominating set consists of the whole set of vertices, in other words, $\gamma_{OL}(D)$ is equal to the order of $D$. We call those digraphs extremal. By considering digraphs with loops allowed, our definition also applies to the related (and more widely studied) concept of identifying codes. We extend previous studies from the literature for both open neighbourhood locating-dominating sets and identifying codes of both undirected and directed graphs. These results all correspond to studying open neighbourhood locating-dominating sets on special classes of digraphs. To do so, we prove general structural properties of extremal digraphs, and we describe how they can all be constructed. We then use these properties to give new proofs of several known results from the literature. We also give a recursive and constructive characterization of the extremal di-trees (digraphs whose underlying undirected graph is a tree).