Guillaume BalDepartment of Applied Physics and Applied Mathematics, Columbia University, 10027 New York, USA.Wenjia JingD´epartement de Math´ematiques et Applications, Ecole Normale Sup´erieure, 45 Rue d’Ulm, 75230 Paris Cedex 05, France
Analysis of PDEsNumerical Analysis and Scientific ComputingProbabilitymathscidoc:2206.03008
This paper analyzes the random fluctuations obtained by a heterogeneous multi-scale first-order finite element method applied to solve elliptic equations with a random potential. Several multiscale numerical algorithms have been shown to correctly capture the homogenized limit of solutions of elliptic equations with coefficients modeled as stationary and ergodic random fields. Because theoretical results are available in the continuum setting for such equations, we consider here the case of a secondorder elliptic equations with random potential in two dimensions of space. We show that the random fluctuations of such solutions are correctly estimated by the heterogeneous multi-scale algorithm when appropriate fine-scale problems are solved on subsets that cover the whole computational domain. However, when the fine-scale problems are solved over patches that do not cover the entire domain, the random fluctuations may or may not be estimated accurately. In the case of random potentials with short-range interactions, the variance of the random fluctuations is amplified as the inverse of the fraction of the medium covered by the patches. In the case of random potentials with long-range interactions, however, such an amplification does not occur and random fluctuations are correctly captured independent of the (macroscopic) size of the patches. These results are consistent with those obtained in  for more general equations in the one-dimensional setting and provide indications on the loss in accuracy that results from using coarser, and hence computationally less intensive, algorithms.
Habib AmmariDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceThomas BoulierDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceJosselin GarnierLaboratoire de Probabilités et Modèles Aléatoires & Laboratoire Jacques-Louis Lions, Université Paris VII, 75205, Paris Cedex 13, FranceWenjia JingDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceHyeonbae KangDepartment of Mathematics, Inha University, Incheon, 402-751, KoreaHan WangDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, France
Analysis of PDEsMathematical PhysicsNumerical Analysis and Scientific ComputingOptimization and Controlmathscidoc:2206.03006
Foundations of Computational Mathematics, 14, 27-62, 2013.9
The aim of this paper is to provide a fast and efficient procedure for (real-time) target identification in imaging based on matching on a dictionary of precomputed generalized polarization tensors (GPTs). The approach is based on some important properties of the GPTs and new invariants. A new shape representation is given and numerically tested in the presence of measurement noise. The stability and resolution of the proposed identification algorithm is numerically quantified. We compare the proposed GPT-based shape representation with a moment-based one.
Guillaume BalDepartment of Applied Physics and Applied Mathematics, Columbia University, New York 10027Wenjia JingDépartement de Mathématiques et Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75230 ParisCedex 05, France
Numerical Analysis and Scientific ComputingProbabilitymathscidoc:2206.25009
We analyze the random fluctuations of several multiscale algorithms, such as the multiscale finite element method (MsFEM) and the finite element heterogeneous multiscale method (HMM), that have been developed to solve partial differential equations with highly heterogeneous coefficients. Such multiscale algorithms are often shown to correctly capture the homogenization limit when the highly oscillatory random medium is stationary and ergodic. This paper is concerned with the random fluctuations of the solution about the deterministic homogenization limit. We consider the simplified setting of the one-dimensional elliptic equation, where the theory of random fluctuations is well understood. We develop a fluctuation theory for the multiscale algorithms in the presence of random environments with short-range and long-range correlations. For a given mesh size h, we show that the fluctuations converge in distribution in the space of continuous paths to Gaussian processes as the correlation length ε→0. We next derive the limit of such Gaussian processes as h→0 and compare this limit with the distribution of the random fluctuations of the continuous model. When such limits agree, we conclude that the multiscale algorithm captures the random fluctuations accurately and passes the corrector test. This property serves as an interesting benchmark to assess the behavior of the multiscale algorithm in practical situations where the assumptions necessary for the theory of homogenization are not met. What we find is that the computationally more expensive methods MsFEM, and HMM with a choice of parameter δ=h, correctly capture the random fluctuations both for short-range and long-range oscillations in the medium. The less expensive method HMM with δ<h correctly captures the fluctuations for long-range oscillations and strongly amplifies their size in media with short-range oscillations. We present a modified scheme with an intermediate computational cost that captures the random fluctuations in all cases.
In this article, we propose a numerical method based on sparse Gaussian processes (SGPs) to solve nonlinear partial differential equations (PDEs). The SGP algorithm is based on a Gaussian process (GP) method, which approximates the solution of a PDE with the maximum a posteriori probability estimator of a GP conditioned on the PDE evaluated at a finite number of sample points. The main bottleneck of the GP method lies in the inversion of a covariance matrix, whose cost grows cubically with respect to the size of samples. To improve the scalability of the GP method while retaining desirable accuracy, we draw inspiration from SGP approximations, where inducing points are introduced to summarize the information of samples. More precisely, our SGP method uses a Gaussian prior associated with a low-rank kernel generated by inducing points randomly selected from samples. In the SGP method, the size of the matrix to be inverted is proportional to the number of inducing points, which is much less than the size of the samples. The numerical experiments show that the SGP method using less than half of the uniform samples as inducing points achieves comparable accuracy to the GP method using the same number of uniform samples, which significantly reduces the computational cost. We give the existence proof for the approximation to the solution of a PDE and provide rigorous error analysis.
Chenchen MouDepartment of Mathematics, City University of Hong Kong, Hong Kong, ChinaXianjin YangYau Mathematical Sciences Center, Tsinghua University, Haidian District, Beijing, 100084, China; Beijing Institute of Mathematical Sciences and Applications, Huairou District, Beijing, 101408, ChinaChao ZhouDepartment of Mathematics and Risk Management Institute, National University of Singapore, Singapore
Numerical Analysis and Scientific ComputingOptimization and Controlmathscidoc:2206.25007
Journal of Computational Physics, 460, (1), 111188, 2022.7
In this article, we propose two numerical methods, the Gaussian Process (GP) method and the Fourier Features (FF) algorithm, to solve mean field games (MFGs). The GP algorithm approximates the solution of a MFG with maximum a posteriori probability estimators of GPs conditioned on the partial differential equation (PDE) system of the MFG at a finite number of sample points. The main bottleneck of the GP method is to compute the inverse of a square gram matrix, whose size is proportional to the number of sample points. To improve the performance, we introduce the FF method, whose insight comes from the recent trend of approximating positive definite kernels with random Fourier features. The FF algorithm seeks approximated solutions in the space generated by sampled Fourier features. In the FF method, the size of the matrix to be inverted depends only on the number of Fourier features selected, which is much less than the size of sample points. Hence, the FF method reduces the precomputation time, saves the memory, and achieves comparable accuracy to the GP method. We give the existence and the convergence proofs for both algorithms. The convergence argument of the GP method does not depend on any monotonicity condition, which suggests the potential applications of the GP method to solve MFGs with non-monotone couplings in future work. We show the efficacy of our algorithms through experiments on a stationary MFG with a non-local coupling and on a time-dependent planning problem. We believe that the FF method can also serve as an alternative algorithm to solve general PDEs.