In this paper, we develop, analyze and test the Fourier spectral methods for solving the Degasperis-Procesi(DP) equation which contains nonlinear high order derivatives, and possibly discontinuous or sharp transition solutions. The $L^2$ stability is obtained for general numerical solutions of the Fourier Galerkin method and Fourier collocation (pseudospectral) method.By applying the Gegenbauer reconstruction technique as a post-processing method to the Fourier spectral solution, we reduce the oscillations arising from the discontinuity successfully. The numerical simulation results for different types of solutions of the nonlinear Degasperis-Procesi equation are provided to illustrate the accuracy and capability of the methods.

We propose a computational efficient yet simple numerical algorithm to solve the surface eikonal equation on general implicit surfaces. The method is developed based on the embedding idea and the fast sweeping methods. We first approximate the solution to the surface eikonal equation by the Euclidean weighted distance function defined in a tubular neighbourhood of the implicit surface, and then apply the efficient fast sweeping method to numerically compute the corresponding viscosity solution. Unlike some other embedding methods which require the radius of the computational tube satisfies h = O ( x ) for some h = O ( x ) , our approach allows h = O ( x ) . This implies that the total number of grid points in the computational tube is optimal and is given by h = O ( x ) for a co-dimensional one surface in h = O ( x ) . The method can be easily extended to general static HamiltonJacobi equation defined on implicit

No abstract uploaded!

We study analytical and numerical properties of the L 1 - L 2 minimization problem for sparse representation of a signal over a highly coherent dictionary. Though the L 1 - L 2 metric is non-convex, it is Lipschitz continuous. The difference of convex algorithm (DCA) is readily applicable for computing the sparse representation coefficients. The L 1 - L 2 minimization appears as an initialization step of DCA. We further integrate DCA with a non-standard simulated annealing methodology to approximate globally sparse solutions. Non-Gaussian random perturbations are more effective than standard Gaussian perturbations for improving sparsity of solutions. In numerical experiments, we conduct an extensive comparison among sparse penalties such as L 1 - L 2 for L 1 - L 2 based on data from three specific applications (over-sampled discreet cosine basis, differential absorption optical spectroscopy, and image denoising) where

No abstract uploaded!

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.

We present an efficient null space free Jacobi–Davidson method to compute the positive eigenvalues of time harmonic Maxwell’s equations. We focus on a class of spatial discretizations that guarantee the existence of discrete vector potentials, such as Yee’s scheme and the edge elements. During the Jacobi–Davidson iteration, the correction process is applied to the vector potential instead. The correction equation is solved approximately as in the standard Jacobi–Davidson approach. The computational cost of the transformation from the vector potential to the corrector is negligible. As a consequence, the expanding subspace automatically stays out of the null space and no extra projection step is needed. Numerical evidence confirms that the proposed scheme indeed outperforms the standard and projection-based Jacobi–Davidson methods by a significant margin.

No abstract uploaded!

No abstract uploaded!

Robustness of numerical methods has attracted an increasing interest in the community of computational fluid dynamics. One mathematical aspect of robustness for numerical methods is the positivity-preserving property. At high Mach numbers or for flows near vacuum, solving the conservative Euler equations may generate negative density or internal energy numerically, which may lead to nonlinear instability and crash of the code. This difficulty is particularly profound for high order methods, for multi-material flows and for problems with moving meshes, such as the Lagrangian methods. In this paper, we construct both first order and uniformly high order accurate conservative Lagrangian schemes which preserve positivity of physically positive variables such as density and internal energy in the simulation of compressible multi-material flows with general equations of state (EOS). We first develop a positivity-preserving approximate Riemann solver for the Lagrangian scheme solving compressible Euler equations with both ideal and non ideal EOS. Then we design a class of high order positivity-preserving and conservative Lagrangian schemes by using the essentially non-oscillatory (ENO) reconstruction, the strong stability preserving (SSP) high order time discretizations and the positivity-preserving scaling limiter which can be proven to maintain conservation and uniformly high order accuracy and is easy to implement. One-dimensional and two-dimensional numerical tests for the positivity-preserving Lagrangian schemes are provided to demonstrate the effectiveness of these methods.

This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize. The great performance of coordinate update methods depends on solving simple sub-problems. To derive simple subproblems for several new classes of applications, this paper systematically studies coordinate-friendly operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history. The obtained algorithms are scalable to large instances through parallel and even asynchronous computing. We present numerical examples to illustrate how effective these algorithms are.

No abstract uploaded!

We present the application of a low dimensional manifold model (LDMM) on hyperspectral image (HSI) reconstruction. An important property of hyperspectral images is that the patch manifold, which is sampled by the three-dimensional blocks in the data cube, is generally of a low dimensional nature. This is a generalization of low-rank models in that hyperspectral images with nonlinear mixing terms can also fit in this framework. The point integral method (PIM) is used to solve a Laplace-Beltrami equation over a point cloud sampling the patch manifold in LDMM. Both numerical simulations and theoretical analysis show that the sample points constraint is correctly enforced by PIM. The framework is demonstrated by experiments on the reconstruction of both linear and nonlinear mixed hyperspectral images with a significant number of missing voxels and several entirely missing spectral bands.

In our earlier work, we constructed uniformly high order accurate discontinuous Galerkin (DG) and finite volume schemes which preserve positivity of density and pressure for the Euler equations of compressible gas dynamics. In this paper, we present an extension of this framework to construct positivity-preserving high order essentially non-oscillatory (ENO) and weighted essentially non-oscillatory (WENO) finite difference schemes for compressible Euler equations. General equations of state and source terms are also discussed. Numerical tests of the fifth order finite difference WENO scheme are reported to demonstrate the good behavior of such schemes.

No abstract uploaded!

In earlier work, two of the authors developed a high order accurate numerical boundary condition procedure for hyperbolic conservation laws, which allows the computation using high order finite difference schemes on Cartesian meshes to solve problems in arbitrary physical domains whose boundaries do not coincide with grid lines. This procedure is based on the so-called inverse Lax-Wendroff (ILW) procedure for inflow boundary conditions and high order extrapolation for outflow boundary conditions. However, the algebra of the ILW procedure is quite heavy for two dimensional (2D) hyperbolic systems, which makes it difficult to implement the procedure for order of accuracy higher than three. In this paper, we first discuss a simplified and improved implementation for this procedure, which uses the relatively complicated ILW procedure only for the evaluation of the first order normal derivatives. Fifth order WENO type extrapolation is used for all other derivatives, regardless of the direction of the local characteristics and the smoothness of the solution. This makes the implementation of a fifth order boundary treatment practical for 2D systems with source terms. For no-penetration boundary condition of compressible inviscid flows, a further simplification is discussed, in which the evaluation of the tangential derivatives involved in the ILW procedure is avoided. We test our simplified and improved boundary treatment for Euler equations with or without source terms representing chemical reactions in detonations. The results demonstrate the designed fifth order accuracy, stability, and good performance for problems involving complicated interactions between detonation/shock waves and solid boundaries.

In this paper, we propose and analyze a new stabilized finite element method using continuous piecewise linear (or bilinear) elements for solving 2D reaction-convection-diffusion equations. The equation under consideration involves a small diffusivity $\varepsilon$ and a large reaction coefficient $\sigma$, leading to high P\'eclet number and high Damk\"{o}hler number. In addition to giving error estimates of the approximations in $L^2$ and $H^1$ norms, we explicitly establish the dependence of error bounds on the diffusivity, the $L^{\infty}$ norm of convection field, the reaction coefficient and the mesh size. Our analysis shows that the proposed method is particularly suitable for problems with a small diffusivity and a large reaction coefficient, or more precisely, with a large mesh P\'eclet number and a large mesh Damk\"{o}hler number. Several numerical examples exhibiting boundary or interior layers are given to illustrate the high accuracy and stability of the proposed method. The results obtained are also compared with those of existing stabilization methods.

In this paper, we develop the Hamiltonian conservative and L2 conservative local discontinuous Galerkin (LDG) schemes for the Korteweg-de Vries (KdV) type equations with the minimal stencil. For the time discretization, we adopt the semi- implicit spectral deferred correction (SDC) method to achieve the high order accuracy and efficiency. Also we compare the schemes with the dissipative LDG scheme. Stabil- ity of the fully discrete schemes is provided by Fourier analysis for the linearized KdV equation. Numerical examples are shown to illustrate the capability of these schemes. Compared with the dissipative LDG scheme, the numerical simulations also indicate that the conservative LDG scheme with high order time discretization can reduce the long time phase error validly.

The numerical approximation of high-frequency wave propagation in inhomogeneous media is a challenging problem. In particular, computing high-frequency solutions by direct simulations requires several points per wavelength for stability and usually requires many points per wavelength for a satisfactory accuracy. In this paper, we propose a new method for the acoustic wave equation in inhomogeneous media in the time domain to achieve superior accuracy and stability without using a large number of unknowns. The method is based on a discontinuous Galerkin discretization together with carefully chosen basis functions. To obtain the basis functions, we use the idea from geometrical optics and construct the basis functions by using the leading order term in the asymptotic expansion. Also, we use a wavefront tracking method and a dimension reduction procedure to obtain dominant rays in each cell. We show

No abstract uploaded!

In this paper, we generalize the point integral method to solve the general elliptic PDEs with variable coefficients and corresponding eigenvalue problems with Neumann, Robin and Dirichlet boundary conditions on point cloud. The main idea is using integral equations to approximate the original PDEs. The integral equations are easy to discretize on the point cloud. The truncation error of the integral approximation is analyzed. Numerical examples are presented to demonstrate that PIM is an effective method to solve the elliptic PDEs with smooth coefficients on point cloud.

We develop a method searching for quasi-conformal maps from point-cloud surfaces to Euclidean plane. The maps can be got by directly solving Beltrami equation with proper boundary condition or solving optimization problem of the variational formu- lation. The point integral methd (PIM) is used for discretization on point clouds. Numerical experiments suggest that the method converges as the density of points in- creases.

In this paper, we develop a class of nonlinear compact schemes based on our previous linear central compact schemes with spectral-like resolution [X. Liu, S. Zhang, H. Zhang and C-W. Shu, A new class of central compact schemes with spectral-like resolution I: Linear schemes, Journal of Computational Physics 248 (2013) 235-256]. In our approach, we compute the flux derivatives on the cell-nodes by the physical fluxes on the cell nodes and numerical fluxes on the cell centers. To acquire the numerical fluxes on the cell centers, we perform a weighted hybrid interpolation of an upwind interpolation and a central interpolation. Through systematic analysis and numerical tests, we show that our nonlinear compact scheme has high order, high resolution and low dissipation, and has the same ability to capture strong discontinuities as regular weighted essentially non-oscillatory (WENO) schemes. It is a good choice for the simulation of multiscale problems with shock waves.

Accurate simulation of seismic waves is of critical importance in a variety of geophysical applications. Based on recent works on staggered discontinuous Galerkin methods, we have developed a new method for the simulations of seismic waves, which has energy conservation and extremely low grid dispersion, so that it naturally provided accurate numerical simulations of wave propagation useful for geophysical applications and was a generalization of classical staggered-grid finite-difference methods. Moreover, it could handle with ease irregular surface topography and discontinuities in the subsurface models. Our new method discretized the velocity and the stress tensor on this staggered grid, with continuity imposed on different parts of the mesh. The symmetry of the stress tensor was enforced by the Lagrange multiplier technique. The resulting method was an explicit scheme, requiring the solutions of a

In this paper, we study the superconvergence of the error for the discontinuous Galerkin (DG) finite element method for linear conservation laws when upwind fluxes are used. We prove that if we apply piecewise $k$-th degree polynomials, the error between the DG solution and the exact solution is ($k+2$)-th order superconvergent at the downwind-biased Radau points with suitable initial discretization. Moreover, we also prove the DG solution is ($k+2$)-th order superconvergent both for the cell averages and for the error to a particular projection of the exact solution. The superconvergence result in this paper leads to a new {\em a posteriori} error estimate. Our analysis is valid for arbitrary regular meshes and for $\mathcal{P}^k$ polynomials with arbitrary $k\geq1$, and for both periodic boundary conditions and for initial-boundary value problems. We perform numerical experiments to demonstrate that the superconvergence rate proved in this paper is optimal.