In this paper, we consider a bilevel polynomial optimization problem where the objective and the constraint functions of both the upper-and the lower-level problems are polynomials. We present methods for finding its global minimizers and global minimum using a sequence of semidefinite programming (SDP) relaxations and provide convergence results for the methods. Our scheme for problems with a convex lower-level problem involves solving a transformed equivalent single-level problem by a sequence of SDP relaxations, whereas our approach for general problems involving a nonconvex polynomial lower-level problem solves a sequence of approximation problems via another sequence of SDP relaxations.

The goal of this paper is to develop a novel semi-implicit spectral deferred correction (SDC) time marching method. The method can be used in a large class of problems, especially for highly nonlinear ordinary differential equations (ODEs) without easily separating of stiff and non-stiff components, which is more general and efficient comparing with traditional semi-implicit SDC methods. The proposed semi-implicit SDC method is based on low order time integration methods and corrected iteratively. The order of accuracy is increased for each additional iteration. And we also explore its local truncation error analytically. This SDC method is intended to be combined with the method of lines, which provides a flexible framework to develop high order semi-implicit time marching methods for nonlinear partial differential equations (PDEs). In this paper we mainly focus on the applications of the nonlinear PDEs with higher order spatial derivatives, e.g. convection diffusion equation, the surface diffusion and Willmore flow of graphs, the Cahn– Hilliard equation, the Cahn–Hilliard–Brinkman system and the phase field crystal equation. Coupled with the local discontinuous Galerkin (LDG) spatial discretization, the fully discrete schemes are all high order accurate in both space and time, and stable numerically with the time step proportional to the spatial mesh size. Numerical experiments are carried out to illustrate the accuracy and capability of the proposed semi-implicit SDC method.

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!

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.

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.

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.

No abstract uploaded!

We consider numerical boundary conditions for high order finite difference schemes for solving convection-diffusion equations on arbitrary geometry. The two main difficulties for numerical boundary conditions in such situations are: (1) the wide stencil of the high order finite difference operator requires special treatment for a few ghost points near the boundary; (2) the physical boundary may not coincide with grid points in a Cartesian mesh and may intersect with the mesh in an arbitrary fashion. For purely convection equations, the so-called inverse Lax-Wendroff procedure, in which we convert the normal derivatives into the time derivatives and tangential derivatives along the physical boundary by using the equations, have been quite successful. In this paper, we extend this methodology to convection-diffusion equations. It turns out that this extension is non-trivial, because totally different boundary treatments are needed for the diffusion-dominated and the convection-dominated regimes. We design a careful combination of the boundary treatments for the two regimes and obtain a stable and accurate boundary condition for general convection-diffusion equations. We provide extensive numerical tests for one- and two-dimensional problems involving both scalar equations and systems, including the compressible Navier-Stokes equations, to demonstrate the good performance of our numerical boundary conditions.

No abstract uploaded!

Fourier spectral methods achieve exponential accuracy both on the approximation level and for solving partial differential equations (PDEs), if the solution is analytic. If the solution is discontinuous but piecewise analytic up to the discontinuities, Fourier spectral methods produce poor pointwise accuracy, but still maintains exponential accuracy after post-processing. In earlier work, an extended technique is provided to recover exponential accuracy for functions which have end-point singularities, from the knowledge of point values on standard collocation points. In this paper, we develop a technique to recover exponential accuracy from the first $N$ Fourier coefficients of functions which are analytic in the open interval but have unbounded derivative singularities at end points. With this post-processing method, we are able to obtain exponential accuracy of spectral methods applied to linear transport equations involving such functions.

In this paper, we develop bound-preserving modified exponential Runge-Kutta (RK) discontinuous Galerkin (DG) schemes to solve scalar hyperbolic equations with stiff source terms by extending the idea in Zhang and Shu \cite{ZhSh:10max}. Exponential strong stability preserving (SSP) high order time discretizations are constructed and then modified to overcome the stiffness and preserve the bound of the numerical solutions. It is also straightforward to extend the method to two dimensions on rectangular and triangular meshes. Even though we only discuss the bound-preserving limiter for DG schemes, it can also be applied to high order finite volume schemes, such as weighted essentially non-oscillatory (WENO) finite volume schemes as well.

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.

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.

In this paper, we apply the local discontinuous Galerkin (LDG) method to 2D Keller--Segel (KS) chemotaxis model. We improve the results upon (Y. Epshteyn and A. Kurganov, SIAM Journal on Numerical Analysis, 47 (2008), 368-408) and give optimal rate of convergence under special finite element spaces before the blow-up occurs (the exact solutions are smooth). Moreover, to construct physically relevant numerical approximations, we consider $P^1$ LDG scheme and develop a positivity-preserving limiter to the scheme, extending the idea in (Y. Zhang, X. Zhang and C.-W. Shu, Journal of Computational Physics, 229 (2010), 8918-8934). With this limiter, we can prove the $L^1$-stability of the numerical scheme. Numerical experiments are performed to demonstrate the good performance of the positivity-preserving LDG scheme. Moreover, it is known that the chemotaxis model will yield blow-up solutions under certain initial conditions. We numerically demonstrate how to find the approximate blow-up time by using the $L^2$-norm of the $L^1$-stable numerical solution.

No abstract uploaded!

How to properly specify boundary conditions for pressure is a longstanding problem for the incompressible Navier–Stokes equations with no-slip boundary conditions. An analytical resolution of this issue stems from a recently developed formula for the pressure in terms of the commutator of the Laplacian and Leray projection operators. Here we make use of this formula to (a) improve the accuracy of computing pressure in two kinds of existing time-discrete projection methods implicit in viscosity only, and (b) devise new higher-order accurate time-discrete projection methods that extend a slip-correction idea behind the well-known finite-difference scheme of Kim and Moin. We test these schemes for stability and accuracy using various combinations of C0 finite elements. For all three kinds of time discretization, one can obtain third-order accuracy for both pressure and velocity without a time-step stability restriction of diffusive type. Furthermore, two kinds of projection methods are found stable using piecewise-linear elements for both velocity and pressure.

We introduce a new troubled-cell indicator for the discontinuous Galerkin (DG) methods for solving hyperbolic conservation laws. This indicator can be defined on unstructured meshes for high order DG methods and depends only on data from the target cell and its immediate neighbors. It is able to identify shocks without PDE sensitive parameters to tune. Extensive one- and two-dimensional simulations on the hyperbolic systems of Euler equations indicate the good performance of this new troubled-cell indicator coupled with a simple minmod-type TVD limiter for the Runge-Kutta DG (RKDG) methods.

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 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 consider the harmonic extension problem, which is widely used in many applications of machine learning. We formulate the harmonic extension as solving a Laplace-Beltrami equation with Dirichlet boundary condition. We use the point integral method (PIM) to solve the Laplace-Beltrami equation. The basic idea of the PIM method is to approximate the Laplace equation using an integral equation, which is easy to be discretized from points. Based on the integral equation, we found that traditional graph Laplacian method (GLM) may fail to approximate the harmonic functions in the classical sense. For the Laplace-Beltrami equation with Dirichlet boundary, we can prove the convergence of the point integral method. The point integral method is also very easy to implement, which only requires a minor modification of the graph Laplacian. One important application of the harmonic extension in machine learning is semi-supervised learning. We run a popular semi-supervised learning algorithm by Zhu et al. over a couple of well-known datasets and compare the performance of the aforementioned approaches. Our experiments show the PIM performs the best. We also apply PIM to an image recovery problem and show it outperforms GLM. Finally, on a model problem of Laplace-Beltrami equation with Dirichlet boundary, we prove the convergence of the point integral method.

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.

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.

It is well-known that sparse grid algorithm has been widely accepted as an efficient tool to overcome the “curse of dimensionality" in some degree. In this note, we give the error estimate of hyperbolic cross (HC) approximations with all sorts of Askey polynomials. These polynomials are useful in generalized polynomial chaos (gPC) in the field of uncertainty quantification. The exponential convergences in both regular and optimized HC approximations have been shown under the condition that the random variable depends on the random inputs smoothly in some degree. Moreover, we apply gPC to numerically solve the ordinary differential equations with slightly higher dimensional random inputs. Both regular and optimized HC have been investigated with Laguerre-chaos, Charlier-chaos and Hermite-chaos in the numerical experiment. The discussion of the connection between the standard ANOVA approximation and Galerkin approximation is in the appendix.

No abstract uploaded!