In this paper we introduce a multilevel Picard approximation algorithm for general semilinear parabolic PDEs with gradient-dependent nonlinearities whose coefficient functions do not need to be constant. We also provide a full convergence and complexity analysis of our algorithm. To obtain our main results, we consider a particular stochastic fixed-point equation (SFPE) motivated by the Feynman-Kac representation and the Bismut-Elworthy-Li formula. We show that the PDE under consideration has a unique viscosity solution which coincides with the first component of the unique solution of the stochastic fixed-point equation. Moreover, the gradient of the unique viscosity solution of the PDE exists and coincides with the second component of the unique solution of the stochastic fixed-point equation.
In this paper, we are concerned about the lattice Boltzmann methods (LBMs) based on vector-kinetic models for hyperbolic partial differential equations. In addition to usual lattice Boltzmann equation (LBE) derived by explicit discretisation of vector-kinetic equation (VKE), we also consider LBE derived by semi-implicit discretisation of VKE and compare the relaxation factors of both. We study the properties such as H-inequality, total variation boundedness and positivity of both the LBEs, and infer that the LBE due to semi-implicit discretisation naturally satisfies all the properties while the LBE due to explicit discretisation requires more restrictive condition on relaxation factor compared to the usual condition obtained from Chapman-Enskog expansion. We also derive the macroscopic finite difference form of the LBEs, and utilise it to establish the consistency of LBEs with the hyperbolic system. Further, we extend this LBM framework to hyperbolic conservation laws with source terms, such that there is no spurious numerical convection due to imbalance between convection and source terms. We also present a D$2$Q$9$ model that allows upwinding even along diagonal directions in addition to the usual upwinding along coordinate directions. The different aspects of the results are validated numerically on standard benchmark problems.
The theory of generalized locally Toeplitz (GLT) sequences is a powerful apparatus for computing the asymptotic spectral distribution of matrices $A_n$ arising from numerical discretizations of differential equations. Indeed, when the mesh fineness parameter $n$ tends to infinity, these matrices $A_n$ give rise to a sequence $\{A_n\}_n$, which often turns out to be a GLT sequence. In this paper, we extend the theory of GLT sequences in several directions: we show that every GLT sequence enjoys a normal form, we identify the spectral symbol of every GLT sequence formed by normal matrices, and we prove that, for every GLT sequence $\{A_n\}_n$ formed by normal matrices and every continuous function $f:\mathbb C\to\mathbb C$, the sequence $\{f(A_n)\}_n$ is again a GLT sequence whose spectral symbol is $f(\kappa)$, where $\kappa$ is the spectral symbol of $\{A_n\}_n$. In addition, using the theory of GLT sequences, we prove a spectral distribution result for perturbed normal matrices.
One tuple of probability vectors is more informative than another tuple when there exists a single stochastic matrix transforming the probability vectors of the first tuple into the probability vectors of the other. This is called matrix majorization. Solving an open problem raised by Mu et al, we show that if certain monotones - namely multivariate extensions of R\'{e}nyi divergences - are strictly ordered between the two tuples, then for sufficiently large $n$, there exists a stochastic matrix taking the $n$-fold Kronecker power of each input distribution to the $n$-fold Kronecker power of the corresponding output distribution. The same conditions, with non-strict ordering for the monotones, are also necessary for such matrix majorization in large samples. Our result also gives conditions for the existence of a sequence of statistical maps that asymptotically (with vanishing error) convert a single copy of each input distribution to the corresponding output distribution with the help of a catalyst that is returned unchanged. Allowing for transformation with arbitrarily small error, we find conditions that are both necessary and sufficient for such catalytic matrix majorization. We derive our results by building on a general algebraic theory of preordered semirings recently developed by one of the authors. This also allows us to recover various existing results on majorization in large samples and in the catalytic regime as well as relative majorization in a unified manner.
In this paper we study the convergence of a second order finite volume approximation of the scalar conservation law. This scheme is based on the generalized Riemann problem (GRP) solver. We firstly investigate the stability of the GRP scheme and find that it might be entropy unstable when the shock wave is generated. By adding an artificial viscosity we propose a new stabilized GRP scheme. Under the assumption that numerical solutions are uniformly bounded, we prove consistency and convergence of this new GRP method.
It is known that standard stochastic Galerkin methods encounter challenges when solving partial differential equations with high-dimensional random inputs, which are typically caused by the large number of stochastic basis functions required. It becomes crucial to properly choose effective basis functions, such that the dimension of the stochastic approximation space can be reduced. In this work, we focus on the stochastic Galerkin approximation associated with generalized polynomial chaos (gPC), and explore the gPC expansion based on the analysis of variance (ANOVA) decomposition. A concise form of the gPC expansion is presented for each component function of the ANOVA expansion, and an adaptive ANOVA procedure is proposed to construct the overall stochastic Galerkin system. Numerical results demonstrate the efficiency of our proposed adaptive ANOVA stochastic Galerkin method for both diffusion and Helmholtz problems.
Personalized recommendations form an important part of today's internet ecosystem, helping artists and creators to reach interested users, and helping users to discover new and engaging content. However, many users today are skeptical of platforms that personalize recommendations, in part due to historically careless treatment of personal data and data privacy. Now, businesses that rely on personalized recommendations are entering a new paradigm, where many of their systems must be overhauled to be privacy-first. In this article, we propose an algorithm for personalized recommendations that facilitates both precise and differentially-private measurement. We consider advertising as an example application, and conduct offline experiments to quantify how the proposed privacy-preserving algorithm affects key metrics related to user experience, advertiser value, and platform revenue compared to the extremes of both (private) non-personalized and non-private, personalized implementations.
By using the stochastic particle method, the truncated Euler-Maruyama (TEM) method is proposed for numerically solving McKean-Vlasov stochastic differential equations (MV-SDEs), possibly with both drift and diffusion coefficients having super-linear growth in the state variable. Firstly, the result of the propagation of chaos in the L^q (q\geq 2) sense is obtained under general assumptions. Then, the standard 1/2-order strong convergence rate in the L^q sense of the proposed method corresponding to the particle system is derived by utilizing the stopping time analysis technique. Furthermore, long-time dynamical properties of MV-SDEs, including the moment boundedness, stability, and the existence and uniqueness of the invariant probability measure, can be numerically realized by the TEM method. Additionally, it is proven that the numerical invariant measure converges to the underlying one of MV-SDEs in the L^2-Wasserstein metric. Finally, the conclusions obtained in this paper are verified through examples and numerical simulations.
We introduce two iterative methods, GPBiLQ and GPQMR, for solving unsymmetric partitioned linear systems. The basic mechanism underlying GPBiLQ and GPQMR is a novel simultaneous tridiagonalization via biorthogonality that allows for short-recurrence iterative schemes. Similar to the biconjugate gradient method, it is possible to develop another method, GPBiCG, whose iterate (if it exists) can be obtained inexpensively from the GPBiLQ iterate. Whereas the iterate of GPBiCG may not exist, the iterates of GPBiLQ and GPQMR are always well defined as long as the biorthogonal tridiagonal reduction process does not break down. We discuss connections between the proposed methods and some existing methods, and give numerical experiments to illustrate the performance of the proposed methods.
In this paper, we conduct rigorous error analysis of the Lie-Totter time-splitting Fourier spectral scheme for the nonlinear Schr\"odinger equation with a logarithmic nonlinear term $f(u)=u\ln|u|^2$ (LogSE) and periodic boundary conditions on a $d$-dimensional torus $\mathbb T^d$. Different from existing works based on regularisation of the nonlinear term $ f(u)\approx f^\varepsilon(u)=u\ln (|u| + \varepsilon )^2,$ we directly discretize the LogSE with the understanding $f(0)=0.$ Remarkably, in the time-splitting scheme, the solution flow map of the nonlinear part: $g(u)= u {\rm e}^{-{\rm} i t \ln|u|^{2}}$ has a higher regularity than $f(u)$ (which is not differentiable at $u=0$ but H\"older continuous), where $g(u)$ is Lipschitz continuous and possesses a certain fractional Sobolev regularity with index $0<s<1$. Accordingly, we can derive the $L^2$-error estimate: $O\big((\tau^{s/2} + N^{-s})\ln\! N\big)$ of the proposed scheme for the LogSE with low regularity solution $u\in C((0,T]; H^s( \mathbb{T}^d)\cap L^\infty( \mathbb{T}^d)).$ Moreover, we can show that the estimate holds for $s=1$ with more delicate analysis of the nonlinear term and the associated solution flow maps. Furthermore, we provide ample numerical results to demonstrate such a fractional-order convergence for initial data with low regularity. This work is the first one devoted to the analysis of splitting scheme for the LogSE without regularisation in the low regularity setting, as far as we can tell.
We introduce in this paper the numerical analysis of high order both in time and space Lagrange-Galerkin methods for the conservative formulation of the advection-diffusion equation. As time discretization scheme we consider the Backward Differentiation Formulas up to order $q=5$. The development and analysis of the methods are performed in the framework of time evolving finite elements presented in C. M. Elliot and T. Ranner, IMA Journal of Numerical Analysis \textbf{41}, 1696-1845 (2021). The error estimates show through their dependence on the parameters of the equation the existence of different regimes in the behavior of the numerical solution; namely, in the diffusive regime, that is, when the diffusion parameter $\mu$ is large, the error is $O(h^{k+1}+\Delta t^{q})$, whereas in the advective regime, $\mu \ll 1$, the convergence is $O(\min (h^{k},\frac{h^{k+1} }{\Delta t})+\Delta t^{q})$. It is worth remarking that the error constant does not have exponential $\mu ^{-1}$ dependence.