In this work we present a class of high order unconditionally strong stability preserving (SSP) implicit multi-derivative Runge--Kutta schemes, and SSP implicit-explicit (IMEX) multi-derivative Runge--Kutta schemes where the time-step restriction is independent of the stiff term. The unconditional SSP property for a method of order $p>2$ is unique among SSP methods, and depends on a backward-in-time assumption on the derivative of the operator. We show that this backward derivative condition is satisfied in many relevant cases where SSP IMEX schemes are desired. We devise unconditionally SSP implicit Runge--Kutta schemes of order up to $p=4$, and IMEX Runge--Kutta schemes of order up to $p=3$. For the multi-derivative IMEX schemes, we also derive and present the order conditions, which have not appeared previously. The unconditional SSP condition ensures that these methods are positivity preserving, and we present sufficient conditions under which such methods are also asymptotic preserving when applied to a range of problems, including a hyperbolic relaxation system, the Broadwell model, and the Bhatnagar-Gross-Krook (BGK) kinetic equation. We present numerical results to support the theoretical results, on a variety of problems.
相關內容
We employ kernel-based approaches that use samples from a probability distribution to approximate a Kolmogorov operator on a manifold. The self-tuning variable-bandwidth kernel method [Berry \& Harlim, \emph{Appl.\ Comput.\ Harmon.\ Anal.}, 40(1):68--96, 2016] computes a large, sparse matrix that approximates the differential operator. Here, we use the eigendecomposition of the discretization to (i) invert the operator, solving a differential equation, and (ii) represent gradient vector fields on the manifold. These methods only require samples from the underlying distribution and, therefore, can be applied in high dimensions or on geometrically complex manifolds when spatial discretizations are not available. We also employ an efficient $k$-$d$ tree algorithm to compute the sparse kernel matrix, which is a computational bottleneck.
Many important differential equations model quantities whose value must remain positive or stay in some bounded interval. These bounds may not be preserved when the model is solved numerically. We propose to ensure positivity or other bounds by applying Runge-Kutta integration in which the method weights are adapted in order to enforce the bounds. The weights are chosen at each step after calculating the stage derivatives, in a way that also preserves (when possible) the order of accuracy of the method. The choice of weights is given by the solution of a linear program. We investigate different approaches to choosing the weights by considering adding further constraints. We also provide some analysis of the properties of Runge-Kutta methods with perturbed weights. Numerical examples demonstrate the effectiveness of the approach, including application to both stiff and non-stiff problems.
We propose new preconditioned iterative solvers for linear systems arising in primal-dual interior point methods for convex quadratic programming problems. These preconditioned conjugate gradient methods operate on an implicit Schur complement of the KKT system at each iteration. In contrast to standard approaches, the Schur complement we consider enables the reuse of the factorization of the Hessian of the equality-constraint Lagrangian across all interior point iterations. Further, the resulting reduced system admits preconditioners that directly alleviate the ill-conditioning associated with the strict complementarity condition in interior point methods. The two preconditioners we propose also provably reduce the number of unique eigenvalues for the coefficient matrix (CG iteration count). One is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-M\'esz\'aros QP collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost. Across all test problems for which the direct method is not fastest, our preconditioned methods achieve a reduction in cost by a geometric mean of 1.432 relative to the best alternative preconditioned method for each problem.
Given a set $P$ of $n$ points and a set $S$ of $m$ weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of $P$. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line $L$ (while points of $P$ can be anywhere in the plane). We present an $O((m+n)\log(m+n)+\kappa\log m)$ time algorithm for the problem, where $\kappa$ is the number of pairs of disks that intersect. Alternatively, we can also solve the problem in $O(nm\log(m+n))$ time. For the unit-disk case where all disks have the same radius, the running time can be reduced to $O((n+m)\log(m+n))$. In addition, we solve in $O((m+n)\log(m+n))$ time the $L_{\infty}$ and $L_1$ cases of the problem, in which the disks are squares and diamonds, respectively. As a by-product, the 1D version of the problem where all points of $P$ are on $L$ and the disks are line segments on $L$ is also solved in $O((m+n)\log(m+n))$ time. We also show that the problem has an $\Omega((m+n)\log (m+n))$ time lower bound even for the 1D case. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set $P$ of $n$ points and a set $S$ of $n$ weighted half-planes, we solve in $O(n^4\log n)$ time the problem of finding a subset of half-planes to cover $P$ so that their total weight is minimized. This improves the previous best algorithm of $O(n^5)$ time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in $O(n^2\log n)$ time, which improves the previous best algorithm of $O(n^4)$ time by almost a quadratic factor.
In this paper, we construct and analyze a uniquely solvable, positivity preserving and unconditionally energy stable finite-difference scheme for the periodic three-component Macromolecular Microsphere Composite (MMC) hydrogels system, a ternary Cahn-Hilliard system with a Flory-Huggins-deGennes free energy potential. The proposed scheme is based on a convex-concave decomposition of the given energy functional with two variables, and the centered difference method is adopted in space. We provide a theoretical justification that this numerical scheme has a pair of unique solutions, such that the positivity is always preserved for all the singular terms, i.e., not only two phase variables are always between $0$ and $1$, but also the sum of two phase variables is between $0$ and $1$, at a point-wise level. In addition, we use the local Newton approximation and multigrid method to solve this nonlinear numerical scheme, and various numerical results are presented, including the numerical convergence test, positivity-preserving property test, energy dissipation and mass conservation properties.
We propose a uniform block diagonal preconditioner for the condensed $H$(div)-conforming HDG scheme of a parameter-dependent saddle point problem that includes the generalized Stokes problem and linear elasticity. An optimal preconditioner is obtained for the stiffness matrix for the velocity/displacement block via auxiliary space preconditioning (ASP) technique. A robust preconditioner spectrally equivalent to the Schur complement of element-piecewise constant pressure space is also constructed. Finally, numerical results of generalized Stokes and steady linear elasticity equations verify the robustness of our proposed preconditioner with respect to mesh size, Lam\'e parameters and time step size.
In this paper, we study the "a posteriori" error estimate corresponding to the Brinkman-Darcy-Forchheimer problem. We introduce the variational formulation discretised by using the finite element method. Then, we establish an "a posteriori" error estimation with two types of error indicators related to the discretization and to the linearization. Finally, numerical investigations are shown and discussed.
In this note, we consider the complexity of optimizing a highly smooth (Lipschitz $k$-th order derivative) and strongly convex function, via calls to a $k$-th order oracle which returns the value and first $k$ derivatives of the function at a given point, and where the dimension is unrestricted. Extending the techniques introduced in Arjevani et al. [2019], we prove that the worst-case oracle complexity for any fixed $k$ to optimize the function up to accuracy $\epsilon$ is on the order of $\left(\frac{\mu_k D^{k-1}}{\lambda}\right)^{\frac{2}{3k+1}}+\log\log\left(\frac{1}{\epsilon}\right)$ (in sufficiently high dimension, and up to log factors independent of $\epsilon$), where $\mu_k$ is the Lipschitz constant of the $k$-th derivative, $D$ is the initial distance to the optimum, and $\lambda$ is the strong convexity parameter.
We present some learning theory results on vector-valued reproducing kernel Hilbert space (RKHS) regression, where the input space is allowed to be non-compact and the output space is a (possibly infinite-dimensional) Hilbert space.
This paper proposes a multiscale method for solving the numerical solution of mean field games which accelerates the convergence and addresses the problem of determining the initial guess. Starting from an approximate solution at the coarsest level, the method constructs approximations on successively finer grids via alternating sweeping, which not only allows for the use of classical time marching numerical schemes but also enables applications to both local and nonlocal problems. At each level, numerical relaxation is used to stabilize the iterative process. A second-order discretization scheme is derived for higher-order convergence. Numerical examples are provided to demonstrate the efficiency of the proposed method in both local and nonlocal, 1-dimensional and 2-dimensional cases.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191