A convergence theory for the $hp$-FEM applied to a variety of constant-coefficient Helmholtz problems was pioneered in the papers [Melenk-Sauter, 2010], [Melenk-Sauter, 2011], [Esterhazy-Melenk, 2012], [Melenk-Parsania-Sauter, 2013]. This theory shows that, if the solution operator is bounded polynomially in the wavenumber $k$, then the Galerkin method is quasioptimal provided that $hk/p \leq C_1$ and $p\geq C_2 \log k$, where $C_1$ is sufficiently small, $C_2$ is sufficiently large, and both are independent of $k,h,$ and $p$. The significance of this result is that if $hk/p= C_1$ and $p=C_2\log k$, then quasioptimality is achieved with the total number of degrees of freedom proportional to $k^d$; i.e., the $hp$-FEM does not suffer from the pollution effect. This paper proves the analogous quasioptimality result for the heterogeneous (i.e. variable-coefficient) Helmholtz equation, posed in $\mathbb{R}^d$, $d=2,3$, with the Sommerfeld radiation condition at infinity, and $C^\infty$ coefficients. We also prove a bound on the relative error of the Galerkin solution in the particular case of the plane-wave scattering problem. These are the first ever results on the wavenumber-explicit convergence of the $hp$-FEM for the Helmholtz equation with variable coefficients.
相關內容
We propose a deterministic Kaczmarz algorithm for solving linear systems $A\x=\b$. Different from previous Kaczmarz algorithms, we use reflections in each step of the iteration. This generates a series of points distributed with patterns on a sphere centered at a solution. Firstly, we prove that taking the average of $O(\eta/\epsilon)$ points leads to an effective approximation of the solution up to relative error $\epsilon$, where $\eta$ is a parameter depending on $A$ and can be bounded above by the square of the condition number. We also show how to select these points efficiently. From the numerical tests, our Kaczmarz algorithm usually converges more quickly than the (block) randomized Kaczmarz algorithms. Secondly, when the linear system is consistent, the Kaczmarz algorithm returns the solution that has the minimal distance to the initial vector. This gives a method to solve the least-norm problem. Finally, we prove that our Kaczmarz algorithm indeed solves the linear system $A^TW^{-1}A \x = A^TW^{-1} \b$, where $W$ is the low-triangular matrix such that $W+W^T=2AA^T$. The relationship between this linear system and the original one is studied.
Our objective is to stabilise and accelerate the time-domain boundary element method (TDBEM) for the three-dimensional wave equation. To overcome the potential time instability, we considered using the Burton--Miller-type boundary integral equation (BMBIE) instead of the ordinary boundary integral equation (OBIE), which consists of the single- and double-layer potentials. In addition, we introduced a smooth temporal basis, i.e. the B-spline temporal basis of order $d$, whereas $d=1$ was used together with the OBIE in a previous study [Takahashi 2014]. Corresponding to these new techniques, we generalised the interpolation-based fast multipole method that was developed in \cite{takahashi2014}. In particular, we constructed the multipole-to-local formula (M2L) so that even for $d\ge 2$ we can maintain the computational complexity of the entire algorithm, i.e. $O(N_{\rm s}^{1+\delta} N_{\rm t})$, where $N_{\rm s}$ and $N_{\rm t}$ denote the number of boundary elements and the number of time steps, respectively, and $\delta$ is theoretically estimated as $1/3$ or $1/2$. The numerical examples indicated that the BMBIE is indispensable for solving the homogeneous Dirichlet problem, but the order $d$ cannot exceed 1 owing to the doubtful cancellation of significant digits when calculating the corresponding layer potentials. In regard to the homogeneous Neumann problem, the previous TDBEM based on the OBIE with $d=1$ can be unstable, whereas it was found that the BMBIE with $d=2$ can be stable and accurate. The present study will enhance the usefulness of the TDBEM for 3D scalar wave problems.
We derive a priori error of the Godunov method for the multidimensional Euler system of gas dynamics. To this end we apply the relative energy principle and estimate the distance between the numerical solution and the strong solution. This yields also the estimates of the $L^2$-norm of errors in density, momentum and entropy. Under the assumption that the numerical density and energy are bounded, we obtain a convergence rate of $1/2$ for the relative energy in the $L^1$-norm. Further, under the assumption -- the total variation of numerical solution is bounded, we obtain the first order convergence rate for the relative energy in the $L^1$-norm. Consequently, numerical solutions (density, momentum and entropy) converge in the $L^2$-norm with the convergence rate of $1/2$. The numerical results presented for Riemann problems are consistent with our theoretical analysis.
Multilevel methods are among the most efficient numerical methods for solving large-scale linear systems that arise from discretized partial differential equations. The fundamental module of such methods is a two-level procedure, which consists of compatible relaxation and coarse-level correction. Regarding two-level convergence theory, most previous works focus on the case of exact (Galerkin) coarse solver. In practice, however, it is often too costly to solve the Galerkin coarse-level system exactly when its size is relatively large. Compared with the exact case, the convergence theory of inexact two-level methods is of more practical significance, while it is still less developed in the literature, especially when nonlinear coarse solvers are used. In this paper, we establish a general framework for analyzing the convergence of inexact two-level methods, in which the coarse-level system is solved approximately by an inner iterative procedure. The framework allows us to use various (linear, nonlinear, deterministic, randomized, or hybrid) solvers in the inner iterations, as long as the corresponding accuracy estimates are available.
In this work we undertake a thorough study of the non-asymptotic properties of the vanilla generative adversarial networks (GANs). We derive theoretical guarantees for the density estimation with GANs under a proper choice of the deep neural networks classes representing generators and discriminators. In particular, we prove that the resulting estimate converges to the true density $\mathsf{p}^*$ in terms of Jensen-Shannon (JS) divergence at the rate $(\log{n}/n)^{2\beta/(2\beta+d)}$ where $n$ is the sample size and $\beta$ determines the smoothness of $\mathsf{p}^*$. To the best of our knowledge, this is the first result in the literature on density estimation using vanilla GANs with JS convergence rates faster than $n^{-1/2}$ in the regime $\beta > d/2$. Moreover, we show that the obtained rate is minimax optimal (up to logarithmic factors) for the considered class of densities.
For a $d$-dimensional log-concave distribution $\pi(\theta)\propto e^{-f(\theta)}$ on a polytope $K$, we consider the problem of outputting samples from a distribution $\nu$ which is $O(\varepsilon)$-close in infinity-distance $\sup_{\theta\in K}|\log\frac{\nu(\theta)}{\pi(\theta)}|$ to $\pi$. Such samplers with infinity-distance guarantees are specifically desired for differentially private optimization as traditional sampling algorithms which come with total-variation distance or KL divergence bounds are insufficient to guarantee differential privacy. Our main result is an algorithm that outputs a point from a distribution $O(\varepsilon)$-close to $\pi$ in infinity-distance and requires $O((md+dL^2R^2)\times(LR+d\log(\frac{Rd+LRd}{\varepsilon r}))\times md^{\omega-1})$ arithmetic operations, where $f$ is $L$-Lipschitz, $K$ is defined by $m$ inequalities, is contained in a ball of radius $R$ and contains a ball of smaller radius $r$, and $\omega$ is the matrix-multiplication constant. In particular this runtime is logarithmic in $\frac{1}{\varepsilon}$ and significantly improves on prior works. Technically, we depart from the prior works that construct Markov chains on a $\frac{1}{\varepsilon^2}$-discretization of $K$ to achieve a sample with $O(\varepsilon)$ infinity-distance error, and present a method to convert continuous samples from $K$ with total-variation bounds to samples with infinity bounds. To achieve improved dependence on $d$, we present a "soft-threshold" version of the Dikin walk which may be of independent interest. Plugging our algorithm into the framework of the exponential mechanism yields similar improvements in the running time of $\varepsilon$-pure differentially private algorithms for optimization problems such as empirical risk minimization of Lipschitz-convex functions and low-rank approximation, while still achieving the tightest known utility bounds.
Due to the high communication cost in distributed and federated learning, methods relying on compressed communication are becoming increasingly popular. Besides, the best theoretically and practically performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of communications (faster convergence), e.g., Nesterov's accelerated gradient descent (Nesterov, 1983, 2004) and Adam (Kingma and Ba, 2014). In order to combine the benefits of communication compression and convergence acceleration, we propose a \emph{compressed and accelerated} gradient method based on ANITA (Li, 2021) for distributed optimization, which we call CANITA. Our CANITA achieves the \emph{first accelerated rate} $O\bigg(\sqrt{\Big(1+\sqrt{\frac{\omega^3}{n}}\Big)\frac{L}{\epsilon}} + \omega\big(\frac{1}{\epsilon}\big)^{\frac{1}{3}}\bigg)$, which improves upon the state-of-the-art non-accelerated rate $O\left((1+\frac{\omega}{n})\frac{L}{\epsilon} + \frac{\omega^2+\omega}{\omega+n}\frac{1}{\epsilon}\right)$ of DIANA (Khaled et al., 2020) for distributed general convex problems, where $\epsilon$ is the target error, $L$ is the smooth parameter of the objective, $n$ is the number of machines/devices, and $\omega$ is the compression parameter (larger $\omega$ means more compression can be applied, and no compression implies $\omega=0$). Our results show that as long as the number of devices $n$ is large (often true in distributed/federated learning), or the compression $\omega$ is not very high, CANITA achieves the faster convergence rate $O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$, i.e., the number of communication rounds is $O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$ (vs. $O\big(\frac{L}{\epsilon}\big)$ achieved by previous works). As a result, CANITA enjoys the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds).
This paper is concerned with superconvergence properties of the direct discontinuous Galerkin (DDG) method for two-dimensional nonlinear convection-diffusion equations. By using the idea of correction function, we prove that, for any piecewise tensor-product polynomials of degree $k\geq 2$, the DDG solution is superconvergent at nodes and Lobatto points, with an order of ${\cal O}(h^{2k})$ and ${\cal O}(h^{k+2})$, respectively. Moreover, superconvergence properties for the derivative approximation are also studied and the superconvergence points are identified at Gauss points, with an order of ${\cal O}(h^{k+1})$. Numerical experiments are presented to confirm the sharpness of all the theoretical findings.
Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users' local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size $M$ and the network load $R$ for networks where a server with $N$ files is connected to $H$ relays (without caches), which in turn are connected to $K$ users equipped with caches of $M$ files. When each user is connected to a different subset of $r$ relays, i.e., $K = \binom{H}{r}$, the system is referred to as a {\it combination network with end-user-caches}. In this work, converse bounds are derived for the practically motivated case of {\it uncoded} cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the user demands are known, the problem reduces to a general index coding problem.This paper shows that relying on a well-known "acyclic index coding converse bound" results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. The proposed schemes are proved: (i) to be (order) optimal for some $(N,M,H,r)$ parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations.
In this paper, we revisit the $L_2$-norm error estimate for $C^0$-interior penalty analysis of Dirichlet boundary control problem governed by biharmonic operator. In this work, we have relaxed the interior angle condition of the domain from $120$ degrees to $180$ degrees, therefore this analysis can be carried out for any convex domain. The theoretical findings are illustrated by numerical experiments. Moreover, we propose a new analysis to derive the error estimates for the biharmonic equation with Cahn-Hilliard type boundary condition under minimal regularity assumption.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191