This paper considers the numerical treatment of the time-dependent Gross-Pitaevskii equation. In order to conserve the time invariants of the equation as accurately as possible, we propose a Crank-Nicolson-type time discretization that is combined with a suitable generalized finite element discretization in space. The space discretization is based on the technique of Localized Orthogonal Decompositions (LOD) and allows to capture the time invariants with an accuracy of order $\mathcal{O}(H^6)$ with respect to the chosen mesh size $H$. This accuracy is preserved due to the conservation properties of the time stepping method. Furthermore, we prove that the resulting scheme approximates the exact solution in the $L^{\infty}(L^2)$-norm with order $\mathcal{O}(\tau^2 + H^4)$, where $\tau$ denotes the step size. The computational efficiency of the method is demonstrated in numerical experiments for a benchmark problem with known exact solution.
相關內容
In this paper, a class of statistics based on high frequency observations of oscillating and skew Brownian motions is considered. Their convergence rate towards the local time of the underlying process is obtained in form of a Central Limit Theorem. Oscillating and skew Brownian motions are solutions to stochastic differential equations with singular coefficients: piecewise constant diffusion coefficient or drift involving the local time. The result is applied to provide estimators of the parameter of skew Brownian motion and study their asymptotic behavior. Moreover, in the case of the classical statistic given by the normalized number of crossings, the result is proved to hold for a larger class of It\^o-processes with singular coefficients.
Chernoff bounds are a powerful application of the Markov inequality to produce strong bounds on the tails of probability distributions. They are often used to bound the tail probabilities of sums of Poisson trials, or in regression to produce conservative confidence intervals for the parameters of such trials. The bounds provide expressions for the tail probabilities that can be inverted for a given probability/confidence to provide tail intervals. The inversions involve the solution of transcendental equations and it is often convenient to substitute approximations that can be exactly solved e.g. by the quadratic equation. In this paper we introduce approximations for the Chernoff bounds whose inversion can be exactly solved with a quadratic equation, but which are closer approximations than those adopted previously.
In this paper, we derive improved a priori error estimates for families of hybridizable interior penalty discontinuous Galerkin (H-IP) methods using a variable penalty for second-order elliptic problems. The strategy is to use a penalization function of the form $\mathcal{O}(1/h^{1+\delta})$, where $h$ denotes the mesh size and $\delta$ is a user-dependent parameter. We then quantify its direct impact on the convergence analysis, namely, the (strong) consistency, discrete coercivity, and boundedness (with $h^{\delta}$-dependency), and we derive updated error estimates for both discrete energy- and $L^{2}$-norms. The originality of the error analysis relies specifically on the use of conforming interpolants of the exact solution. All theoretical results are supported by numerical evidence.
Let a polytope $\mathcal{P}$ be defined by one of the following ways: (i) $\mathcal{P} = \{x \in \mathbb{R}^n \colon A x \leq b\}$, where $A \in \mathbb{Z}^{(n+m) \times n}$, $b \in \mathbb{Z}^{(n+m)}$, and $rank(A) = n$, (ii) $\mathcal{P} = \{x \in \mathbb{R}_+^n \colon A x = b\}$, where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^{m}$, and $rank(A) = m$, and let all the rank minors of $A$ be bounded by $\Delta$ in the absolute values. We show that $|\mathcal{P} \cap \mathbb{Z}^n|$ can be computed with an algorithm, having the arithmetic complexity bound $$ O\bigl(d^{m + 4} \cdot \Delta^4 \cdot \log(\Delta) \bigr), $$ where $d = \dim(\mathcal{P})$, which outperforms the previous best known complexity bound $O(d^{m + O(1)} \cdot d^{\log_2(\Delta)})$. We do not directly compute the short rational generating function for $\mathcal{P} \cap \mathbb{Z}^n$, but compute its particular representation in the form of exponential series that depends on only one variable. The parametric versions of the above problem are also considered.
We consider a Random Graph Model on $\mathbb{Z}^{d}$ that incorporates the interplay between the statistics of the graph and the underlying space where the vertices are located. Based on a graphical construction of the model as the invariant measure of a birth and death process, we prove the existence and uniqueness of a measure defined on graphs with vertices in $\mathbb{Z}^{d}$ which coincides with the limit along the measures over graphs with finite vertex set. As a consequence, theoretical properties such as exponential mixing of the infinite volume measure and central limit theorem for averages of a real-valued function of the graph are obtained. Moreover, a perfect simulation algorithm based on the clan of ancestors is described in order to sample a finite window of the equilibrium measure defined on $\mathbb{Z}^{d}$.
A matching is a set of edges in a graph with no common endpoint. A matching $M$ is called acyclic if the induced subgraph on the endpoints of the edges in $M$ is acyclic. Given a graph $G$ and an integer $k$, Acyclic Matching Problem seeks for an acyclic matching of size $k$ in $G$. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter $k$. On the other hand, the problem is fixed parameter tractable with respect to $k$, for line graphs, $C_4$-free graphs and every proper minor-closed class of graphs (including bounded tree-width and planar graphs).
Block coordinate descent (BCD), also known as nonlinear Gauss-Seidel, is a simple iterative algorithm for nonconvex optimization that sequentially minimizes the objective function in each block coordinate while the other coordinates are held fixed. We propose a version of BCD that, for block multi-convex and smooth objective functions under constraints, is guaranteed to converge to the stationary points with worst-case rate of convergence of $O((\log n)^{2}/n)$ for $n$ iterations, and a bound of $O(\epsilon^{-1}(\log \epsilon^{-1})^{2})$ for the number of iterations to achieve an $\epsilon$-approximate stationary point. Furthermore, we show that these results continue to hold even when the convex sub-problems are inexactly solved if the optimality gaps are uniformly summable against initialization. A key idea is to restrict the parameter search within a diminishing radius to promote stability of iterates. As an application, we provide an alternating least squares algorithm with diminishing radius for nonnegative CP tensor decomposition that converges to the stationary points of the reconstruction error with the same robust worst-case convergence rate and complexity bounds. We also experimentally validate our results with both synthetic and real-world data and demonstrate that using auxiliary search radius restriction can in fact improve the rate of convergence.
The implementation of discontinuous functions occurs in many of today's state of the art partial differential equation solvers. In finite element methods this poses an inherent difficulty: there are no quadrature rules readily available, when integrating functions whose discontinuity falls in the interior of the element. Many approaches to this issue have been developed in recent years, among them is the equivalent polynomial technique. This method replaces the discontinuous function with a polynomial, potentially allowing for the integration to occur over the entire domain, rather than integrating over complex subdomains. Although, eliminating the issues involved with discontinuous function integration, the equivalent polynomial tactic introduces its own set of problems. In particular, either adaptivity is required to capture the discontinuity or error is introduced when regularization of the discontinuous function is implemented. In the current work we eliminate both of these issues. The results of this work provide exact algebraic expressions for subdomain and interface polynomial integration, where the interface represents the boundary of the cut domain. We also provide algorithms for the implementation of these expressions for standard finite element shapes in one, two, and three dimensions, along with a hypercube of arbitrary dimension .
This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP has been widely applied to many areas, including healthcare, power system, manufacturing and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study an efficient sampling algorithm and develop its approximation bound for MESP, which improves the best-known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. By developing new mathematical tools for the singular matrices and analyzing the Lagrangian dual of the proposed convex integer program, we investigate the widely-used local search algorithm and prove its first-known approximation bound for MESP. The proof techniques further inspire us with an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-sized and large-scale instances to near-optimality. Our proposed algorithms are coded and released as open-source software. Finally, we extend the analyses to the A-Optimal MESP (A-MESP), where the objective is to minimize the trace of the inverse of the selected principal submatrix.
Considering the large number of fractional operators that exist, and since it does not seem that their number will stop increasing soon at the time of writing this paper, it is presented for the first time, as far as the authors know, a simplified and compact way to work the fractional calculus through the classification of fractional operators using sets. This new way of working with fractional operators, which may be called as fractional calculus of sets, allows to generalize objects of the conventional calculus such as tensor operators, the diffusion equation, the heat equation, the Taylor series of a vector-valued function, and the fixed point method in several variables which allows to generate the method known as the fractional fixed point method. It is also shown that each fractional fixed point method that generates a convergent sequence has the ability to generate an uncountable family of fractional fixed point methods that generate convergent sequences. So, it is shown one way to estimate numerically the mean order of convergence of any fractional fixed point method in a region $\Omega$ through the problem of determining the critical points of a scalar function, and it is shown how to construct a hybrid fractional iterative method to determine the critical points of a scalar function.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191