In this paper, we develop an adaptive generalized multiscale discontinuous Galerkin method (GMsDGM) for a class of high-contrast flow problems and derive a priori and a posteriori error estimates for the method. Based on the a posteriori error estimator, we develop an adaptive enrichment algorithm for our GMsDGM and prove its convergence. The adaptive enrichment algorithm gives an automatic way to enrich the approximation space in regions where the solution requires more basis functions, which are shown to perform well compared with a uniform enrichment. We also discuss an approach that adaptively selects multiscale basis functions by correlating the residual to multiscale basis functions (cf. [S. S. Chen, D. L. Donoho, and M. A. Saunders, <i>SIAM Rev.</i>, 43 (2001), pp. 129--159]). The proposed error indicators are L_2-based and can be inexpensively computed, which makes our approach efficient

In this paper, we present two adaptive methods for the basis enrichment of the mixed Generalized Multiscale Finite Element Method (GMsFEM) for solving the flow problem in heterogeneous media. We develop an a-posteriori error indicator which depends on the norm of a local residual operator. Based on this indicator, we construct an offline adaptive method to increase the number of basis functions locally in coarse regions with large local residuals. We also develop an online adaptive method which iteratively enriches the function space by adding new functions computed based on the residual of the previous solution and special minimum energy snapshots. We show theoretically and numerically the convergence of the two methods. The online method is, in general, better than the offline method as the online method is able to capture distant effects (at a cost of online computations), and both

We consider a strongly heterogeneous medium saturated by an incompressible viscous fluid as it appears in geomechanical modeling. This poroelasticity problem suffers from rapidly oscillating material parameters, which calls for a thorough numerical treatment. In this paper, we propose a method based on the local orthogonal decomposition technique and motivated by a similar approach used for linear thermoelasticity. Therein, local corrector problems are constructed in line with the static equations, whereas we propose to consider the full system. This allows to benefit from the given saddle point structure and results in two decoupled corrector problems for the displacement and the pressure. We prove the optimal first-order convergence of this method and verify the result by numerical experiments.

We develop Random Batch Methods for interacting particle systems with large number of particles. These methods use small but random batches for particle interactions, thus the computational cost is reduced from $O(N^2)$ per time step to $O(N)$, for a system with $N$ particles with binary interactions. On one hand, these methods are efficient Asymptotic-Preserving schemes for the underlying particle systems, allowing $N$-independent time steps and also capture, in the $N \to \infty$ limit, the solution of the mean field limit which are nonlinear Fokker-Planck equations; on the other hand, the stochastic processes generated by the algorithms can also be regarded as new models for the underlying problems. For one of the methods, we give a particle number independent error estimate under some special interactions. Then, we apply these methods to some representative problems in mathematics, physics, social and data sciences, including the Dyson Brownian motion from random matrix theory, Thomson's problem, distribution of wealth, opinion dynamics and clustering. Numerical results show that the methods can capture both the transient solutions and the global equilibrium in these problems.

The equilibrium metric for minimizing a continuous congested traffic model is the solution of a variational problem involving geodesic distances. The continuous equilibrium metric and its associated variational problem are closely related to the classical discrete Wardrops equilibrium. We propose an adjoint state method to numerically approximate continuous traffic congestion equilibria through the continuous formulation. The method formally derives an adjoint state equation to compute the gradient descent direction so as to minimize a nonlinear functional involving the equilibrium metric and the resulting geodesic distances. The geodesic distance needed for the state equation is computed by solving a factored eikonal equation, and the adjoint state equation is solved by a fast sweeping method. Numerical examples demonstrate that the proposed adjoint state method produces desired equilibrium metrics and

Blind source separation (BSS) methods are useful tools to recover or enhance individual speech sources from their mixtures in a multi-talker environment. A class of efficient BSS methods are based on the mutual exclusion hypothesis of the source signal Fourier spectra on the timefrequency (TF) domain, and subsequent data clustering and classification. Though such methodology is simple, the discontinuous decisions in the TF domain for classification often cause defects in the recovered signals in the time domain. The defects are perceived as unpleasant ringing sounds, the so called musical noise. Post-processing is desired for further quality enhancement. In this paper, an efficient musical noise reduction method is presented based on a convex model of time-domain sparse filters. The sparse filters are intended to cancel out the interference due to major sparse peaks in the mixing coefficients or physically the early arrival and high energy portion of the room impulse responses. This strategy is efficiently carried out by l1 regularization and the split Bregman method. Evaluations by both synthetic and room recorded speech and music data show that our method outperforms existing musical noise reduction methods in terms of objective and subjective measures. Our method can be used as a post-processing tool for more general and recent versions of TF domain BSS methods as well.

In this paper, we develop an effective and robust adaptive time-frequency analysis method for signals with intra-wave frequency modulation. To handle this kind of signals effectively, we generalize our data-driven time-frequency analysis by using a shape function to describe the intra-wave frequency modulation. The idea of using a shape function in time-frequency analysis was first proposed by Wu (Wu 2013 Appl. Comput. Harmon. Anal. 35, 181–199. (doi:10.1016/j.acha.2012.08.008)). A shape function could be any smooth 2π-periodic function. Based on this model, we propose to solve an optimization problem to extract the shape function. By exploring the fact that the shape function is a periodic function with respect to its phase function, we can identify certain low-rank structure of the signal. This low-rank structure enables us to extract the shape function from the signal. Once the shape function is obtained, the instantaneous frequency with intra-wave modulation can be recovered from the shape function. We demonstrate the robustness and efficiency of our method by applying it to several synthetic and real signals. One important observation is that this approach is very stable to noise perturbation. By using the shape function approach, we can capture the intrawave frequency modulation very well even for noisepolluted signals. In comparison, existing methods such as empirical mode decomposition/ensemble empiricalmode decomposition seem to have difficulty in capturing the intra-wave modulation when the signal is polluted by noise.

In this paper, we analyze the uniqueness of the sparse time frequency decomposition and investigate the eciency of the nonlinear matching pursuit method. Under the assumption of scale separation, we show that the sparse time frequency decomposition is unique up to an error that is determined by the scale separation property of the signal. We further show that the unique decomposition can be obtained approximately by the sparse time frequency decomposition using nonlinear matching pursuit.

The problem is concerned about computing virtual coordinates for greedy routing in a wireless ad hoc network. Consider a set of wireless nodes S densely deployed inside a geometric domain R2. Nodes within communication range can directly communicate with each other. We ask whether one can compute a set of virtual coordinates for S such that greedy routing has guaranteed delivery. In particular, each node forwards the message to the neighbor whose distance to the destination, computed under the virtual coordinates and some metric function d, is the smallest. If such a neighbor can always be found, greedy routing successfully delivers the message to the destination. The problem can be phrased as finding a greedy embedding of S in some geometric space, such that greedy routing always succeeds. In the setting of this entry, we assume that the nodes are a dense sample of the domain such that

For the steady-state solution of a differential equation from a one-dimensional multistate model in transport theory, we shall derive and study a nonsymmetric algebraic Riccati equation <i>B</i> <i>XF</i> <i>F</i>⁺<i>X</i> + <i>XB</i>⁺<i>X</i> = 0, where <i>F</i> (<i>I</i> <i>F</i>)<i>D</i> and <i>B</i> <i>BD</i> with positive diagonal matrices <i>D</i> and possibly low-ranked matrices <i>F</i> and <i>B</i>. We prove the existence of the minimal positive solution <i>X</i>^* under a set of physically reasonable assumptions and study its numerical computation by fixed-point iteration, Newtons method and the doubling algorithm. We shall also study several special cases. For example when <i>B</i> and <i>F</i> are low ranked then X*=(i=14UiViT) with low-ranked <i>U_i</i> and <i>V_i</i> that can be computed using more efficient iterative processes. Numerical examples will be given to illustrate our theoretical results.

In this paper, we establish a connection between the recently developed data-driven timefrequency analysis [10, 11] and the classical second order differential equations. The main idea of the data-driven time-frequency analysis is to decompose a multiscale signal into the sparsest collection of Intrinsic Mode Functions (IMFs) over the largest possible dictionary via nonlinear optimization. These IMFs are of the form a(t) cos(θ(t)) where the amplitude a(t) is positive and slowly varying. The non-decreasing phase function θ(t) is determined by the data and in general depends on the signal in a nonlinear fashion. One of the main results of this paper is that we show that each IMF can be associated with a solution of a second order ordinary differential equation of the form x¨ + p(x, t)x˙ + q(x, t) = 0. Further, we propose a localized variational formulation for this problem and develop an effective l1-based optimization method to recover p(x, t) and q(x, t) by looking for a sparse representation of p and q in terms of the polynomial basis. Depending on the form of nonlinearity in p(x, t) and q(x, t), we can define the order of nonlinearity for the associated IMF. This generalizes a concept recently introduced by Prof. N. E. Huang et al. [15]. Numerical examples will be provided to illustrate the robustness and stability of the proposed method for data with or without noise. This manuscript should be considered as a proof of concept.

In this work, we present an upscaled model for mixed dimensional coupled flow problem in fractured porous media. We consider both embedded and discrete fracture models (EFM and DFM) as fine scale models which contain coupled system of equations. For fine grid discretization, we use a conservative finite-volume approximation. We construct an upscaled model using the non-local multicontinuum (NLMC) method for the coupled system. The proposed upscaled model is based on a set of simplified multiscale basis functions for the auxiliary space and a constraint energy minimization principle for the construction of multiscale basis functions. Using the constructed NLMC-multiscale basis functions, we obtain an accurate coarse grid upscaled model. We present numerical results for both fine-grid models and upscaled coarse-grid models using our NLMC method. We consider model problems with (1) discrete fracture fine grid model with low and high permeable fractures;(2) embedded fine grid model for two types of geometries with differnet fracture networks and (3) embedded fracture fine grid model with heterogeneous permeability. The simulations using the upscaled model provide very accurate solutions with significant reduction in the dimension of the problem.

The goal of smooth function reconstruction on a 2D or 3D manifold is to obtain a smooth function on surfaces or higher dimensional manifolds. It is a common problem in computer graphics and computational mathematics, especially in civil engineering including structural analysis of solid objects. In this chapter, we introduce a new method using harmonic functions for solving this problem. This method contains the following steps: (1) Partition the boundary surfaces of the 3D manifold based on sample points so that each sample point is on the edge of the partition. (2) Use gradually varied interpolation on the edges so that each point on the edge will be assigned a value. In addition, all values on the edge are gradually varied. (3) Use discrete harmonic functions to fit the unknown points, i.e. the points inside each partition patch. This solution of the fitting becomes the piecewise harmonic function.

In E & Liu (SIAM J Numer. Anal., 1995), we studied convergence and the structure of the error for several projection methods when the spatial variable was kept continuous (we call this the semi-discrete case). In this paper, we address similar questions for the fully discrete case when the spatial variables are discretized using a staggered grid. We prove that the numerical solution in velocity has full accuracy up to the boundary, despite the fact that there are numerical boundary layers present in the semi-discrete solutions.

We begin a systematical study on the effect of numerical viscosities. In this paper we investigate the behavior of shock-capturing methods for slowly moving shocks. It is known that for slowly moving shocks even a first-order scheme, such as the Godunov or Roe type methods, will generate downstream oscillatory wave patterns that cannot be effectively damped by the dissipation of these first-order schemes. The purpose of this paper is to understand the formation and behavior of these downstream patterns. Our study shows that the downstream errors are generated by the unsteady nature of the viscous shock profiles and behave diffusively. The scenario is as follows. When solving the compressible Euler equations by shock capturing methods, the smeared density profile introduces a momentum spike at the shock location if the shock moves slowly. Downstream waves will necessarily emerge in order to balance the momentum mass carried by the spike for the momentum conservation. Although each family of waves decays inl∞andl2while they preserve the same mass, the perturbing nature of the viscous or spike profile is a constant source for the generation of new downstream waves, causing spurious solutions foralltime. Higher order TVD or ENO type interpolations accentuate this problem.

Consider the single-facility Euclidean -centrum location problem in R n. This problem is a generalization of the classical Euclidean 1-median problem and 1-center problem. In this paper, we develop two efficient algorithms that are particularly suitable for problems where n is large by using unconstrained optimization techniques. The first algorithm is based on the neural networks smooth approximation for the plus function and reduces the problem to an unconstrained smooth convex minimization problem. The second algorithm is based on the FischerBurmeister merit function for the second-order cone complementarity problem and transforms the KKT system of the second-order cone programming reformulation for the problem into an unconstrained smooth minimization problem. Our computational experiments indicate that both methods are extremely efficient for large problems and the first algorithm is able to

In this paper we introduce a high-order discontinuous Galerkin method for two-dimensional incompressible flow in the vorticity stream-function formulation. The momentum equation is treated explicitly, utilizing the efficiency of the discontinuous Galerkin method. The stream function is obtained by a standard Poisson solver using continuous finite elements. There is a natural matching between these two finite element spaces, since the normal component of the velocity field is continuous across element boundaries. This allows for a correct upwinding gluing in the discontinuous Galerkin framework, while still maintaining total energy conservation with no numerical dissipation and total enstrophy stability. The method is efficient for inviscid or high Reynolds number flows. Optimal error estimates are proved and verified by numerical experiments.

In this paper, we present a measure of distance in a second-order cone based on a class of continuously differentiable strictly convex functions on ₊₊. Since the distance function has some favorable properties similar to those of the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451464 [1992]), we refer to it as a quasi D-function. Then, a proximal-like algorithm using the quasi D-function is proposed and applied to the second-cone programming problem, which is to minimize a closed proper convex function with general second-order cone constraints. Like the proximal point algorithm using the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451464 [1992]; Chen and Teboulle in SIAM J. Optim. 3:538543 [1993]), under some mild assumptions we establish the global convergence of the algorithm expressed in terms of function values; we show that the sequence generated by the

We present a hybrid asymptotic/numerical method for the accurate computation of single- and double-layer heat potentials in two dimensions. It has been shown in previous work that simple quadrature schemes suffer from a phenomenon called “geometrically induced stiffness,” meaning that formally high-order accurate methods require excessively small time steps before the rapid convergence rate is observed. This can be overcome by analytic integration in time, requiring the evaluation of a collection of spatial boundary integral operators with non-physical, weakly singular kernels. In our hybrid scheme, we combine a local asymptotic approximation with the evaluation of a few boundary integral operators involving only Gaussian kernels, which are easily accelerated by a new version of the fast Gauss transform. This new scheme is robust, avoids geometrically induced stiffness, and is easy to use in the presence of moving geometries. Its extension to three dimensions is natural and straightforward, and should permit layer heat potentials to become flexible and powerful tools for modeling diffusion processes.

We establish uniform error bounds of a finite difference method for the Klein-Gordon-Zakharov system (KGZ) with a dimensionless parameter ε∈(0,1], which is inversely proportional to the acoustic speed. In the subsonic limit regime, i.e. 0<ε≪1, the solution propagates highly oscillatory waves in time and/or rapid outgoing initial layers in space due to the singular perturbation in the Zakharov equation and/or the incompatibility of the initial data. Specifically, the solution propagates waves with O(ε)-wavelength in time and O(1)-wavelength in space as well as outgoing initial layers in space at speed O(1/ε). This high oscillation in time and rapid outgoing waves in space of the solution cause significant burdens in designing numerical methods and establishing error estimates for KGZ. By adapting an asymptotic consistent formulation, we propose a uniformly accurate finite difference method and rigorously establish two independent error bounds at O(h^2+τ^2/ε) and O(h^2+τ+ε) with h mesh size and τ time step. Thus we obtain a uniform error bound at O(h^2+τ) for 0<ε≤1. The main techniques in the analysis include the energy method, cut-off of the nonlinearity to bound the numerical solution, the integral approximation of the oscillatory term, and ε-dependent error bounds between the solutions of KGZ and its limiting model when ε→0+. Finally, numerical results are reported to confirm our error bounds.

In this paper, we study the problem of computing the effective diffusivity for a particle moving in chaotic and stochastic flows. In addition, we numerically investigate the residual diffusion phenomenon in chaotic advection. The residual diffusion refers to the nonzero effective (homogenized) diffusion in the limit of zero molecular diffusion as a result of chaotic mixing of the streamlines. In this limit, traditional numerical methods typically fail since the solutions of the advection-diffusion equations develop sharp gradients. Instead of solving the Fokker--Planck equation in the Eulerian formulation, we compute the motion of particles in the Lagrangian formulation, which is modeled by stochastic differential equations (SDEs). We propose an effective numerical integrator based on a splitting method to solve the corresponding SDEs in which the deterministic subproblem is symplectic preserving while the random subproblem

Greedy forwarding with geographical locations in a wireless sensor network may fail at a local minimum. In this paper we propose to use conformal mapping to compute a new embedding of the sensor nodes in the plane such that greedy forwarding with the virtual coordinates guarantees delivery. In particular, we extract a planar triangulation of the sensor network with non-triangular faces as holes, by either using the nodes' location or using a landmark-based scheme without node location. The conformal map is computed with Ricci flow such that all the non-triangular faces are mapped to perfect circles. Thus greedy forwarding will never get stuck at an intermediate node. The computation of the conformal map and the virtual coordinates is performed at a preprocessing phase and can be implemented by local gossip-style computation. The method applies to both unit disk graph models and quasi-unit disk graph

Recent technical advances lead to the coupling of PET and MRI scanners, enabling one to acquire functional and anatomical data simultaneously. In this paper, we propose a tight frame based PET-MRI joint reconstruction model via the joint sparsity of tight frame coefficients. In addition, a nonconvex balanced approach is adopted to take the different regularities of PET and MRI images into account. To solve the nonconvex and nonsmooth model, a proximal alternating minimization algorithm is proposed, and the global convergence is present based on the Kurdyka--Łojasiewicz property. Finally, the numerical experiments show that our proposed models achieve better performance over the existing PET-MRI joint reconstruction models.

The Euler equation of compressible flows is solved by the finite volume method, where high order accuracy is achieved by the reconstruction of each component of upwind fluxes of a flux splitting using the biased averaging procedure. Compared to the solution reconstruction in Godunov-type methods, its implementation is simple and easy, and the computational complexity is relatively low. This approach is parameter-free and requires neither a Riemann solver nor field-by-field decomposition. The numerical results from both dynamic and steady state calculations demonstrate the accuracy and robustness of this approach. Some techniques for the acceleration of the convergence to the steady state are discussed, including multigrid and multistage Runge–Kutta time methods.

Shape optimization aims to optimize an objective function by changing the shape of the computational domain. In recent years, shape optimization has received considerable attentions. On the theoretical side there are several publications dealing with the existence of solution and the sensitivity analysis of the problem; see e.g., [6] and references therein.