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 study how to characterize the families of paths between any two nodes s, t in a sensor network with holes. Two paths that can be deformed to one another through local changes are called homotopy equivalent. Two paths that pass around holes in different ways have different homotopy types. With a distributed algorithm we compute an embedding of the network in hyperbolic space by using Ricci flow such that paths of different homotopy types are mapped naturally to paths connecting s with different images of t. Greedy routing to a particular image is guaranteed with success to find a path with a given homotopy type. This leads to simple greedy routing algorithms that are resilient to both local link dynamics and large scale jamming attacks and improve load balancing over previous greedy routing algorithms.

We introduce a finite volume scheme for multi-dimensional drift-diffusion equations. Such equations arise from the theory of semiconductors and are composed of two continuity equations coupled with a Poisson equation. In the case that the continuity equations are non degenerate, we prove the convergence of the scheme and then the existence of solutions to the problem. The key point of the proof relies on the construction of an approximate gradient of the electric potential which allows us to deal with coupled terms in the continuity equations. Finally, a numerical example is given to show the efficiency of the scheme.

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.

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.

This paper presents a novel mass-conservative mixed multiscale method for solving flow equations in heterogeneous porous media. The media properties (the permeability) contain multiple scales and high contrast. The proposed method solves the flow equation in a mixed formulation on a coarse grid by constructing multiscale basis functions. The resulting velocity field is mass-conservative on the fine grid. Our main goal is to obtain first-order convergence in terms of the mesh size which is independent of local contrast. This is achieved, first, by constructing some auxiliary spaces, which contain global information that cannot be localized, in general. This is built on our previous work on the generalized multiscale finite element method (GMsFEM). In the auxiliary space, multiscale basis functions corresponding to small (contrast-dependent) eigenvalues are selected. These basis functions represent the high

This paper discusses three basic issues related to the design of finite difference schemes for unsteadyviscous incompressible flows using vorticity formulations: the boundary condition for vorticity, an efficient time-stepping procedure, and the relation between these schemes and the ones based on velocity-pressure formulation. We show that many of the newly developed global vorticity boundary conditions can actually be written as some local formulas derived earlier. We also show that if we couple a standard centered difference scheme with third- or fourth-order explicit Runge-Kutta methods, the resulting schemes have nocell Reynolds number constraints. For high Reynolds number flows, these schemes are stable under the CFL condition given by the convective terms. Finally, we show that the classical MAC scheme is the same as Thom's formula coupled with second-order centered differences in the interior, in the sense that one can define discrete vorticity in a natural way for the MAC scheme and get the same values as the ones computed from Thom's formula. We use this to derive an efficient fourth-order Runge-Kutta time discretization for the MAC scheme from the one for Thom's formula. We present numerical results for driven cavity flow at high Reynolds number (10 ).

Differential optical absorption spectroscopy (DOAS) is a powerful tool for detecting and quantifying trace gases in atmospheric chemistry\cite {Platt_Stutz08}. DOAS spectra consist of a linear combination of complex multi-peak multi-scale structures. Most DOAS analysis routines in use today are based on least squares techniques, for example, the approach developed in the 1970s uses polynomial fits to remove a slowly varying background, and known reference spectra to retrieve the identity and concentrations of reference gases. An open problem is to identify unknown gases in the fitting residuals for complex atmospheric mixtures.

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

A key difficulty in the analysis and numerical approximation of the shallow water equations is the nonconservative product of measures due to the gravitational force acting on a sloped bottom. Solutions may be nonunique, and numerical schemes are not only consistent discretizations of the shallow water equations, but they also determine how to model the physics. Our derivation is based on a subcell reconstruction using infinitesimal singular layers at the cell boundaries, as inspired by S. Noelle, Y. Xing, and C.-W. Shu [J. Comput. Phys., 226 (2007), pp. 29-58]. One key step is to separate the singular measures. Another aspect is the reconstruction of the solution variables in the singular layers. We study three reconstructions. The first leads to the well-known scheme of Audusse et al., [SIAM J. Sci. Comput., 25 (2004), pp. 2050-2065], which introduces the hydrostatic reconstruction. The second is a modification proposed in [T. Morales de Luna, M. J. Castro D´ıaz, and C. Par´es, Appl. Math. Comput., 219 (2013), pp. 9012-9032], which analyzes whether a wave has enough energy to overcome a step. The third is our new scheme, which borrows its structure from the wet-dry front. For a number of cases discussed in recent years, where water runs down a hill, Audusse’s scheme converges slowly or fails. Morales’ scheme gives a visible improvement. Both schemes are clearly outperformed by our new scheme.

Let $\Omega\subset\mathbb R^d$, $1\leq d\leq 3$, be a bounded $d$-polytope. Consider the parabolic equation on $\Omega$ with the Dirac delta function on the right hand side. We study the well-posedness, regularity, and the interior error estimate of semidiscrete finite element approximations of the equation. In particular, we derive that the interior error is bounded by the best local approximation error, the negative norms of the error, and the negative norms of the time derivative of the error. This result implies different convergence rates for the numerical solution in different interior regions, especially when the region is close to the singular point. Numerical test results are reported to support the theoretical prediction.

Systematically generalizing planar geometric algorithms to manifold domains is of fundamental importance in computer aided design field. This paper proposes a novel theoretic framework, <i>geometric structure</i>, to conquer this problem. In order to discover the intrinsic geometric structures of general surfaces, we developed a theoretic rigorous and practical efficient method, <i>Discrete Variational Ricci flow</i>.

With rheology applications in mind, we present a fast solver for the time-dependent effective viscosity of an infinite lattice containing one or more neutrally buoyant smooth rigid particles per unit cell, in a two-dimensional Stokes fluid with given shear rate. At each time, the mobility problem is reformulated as a 2nd-kind boundary integral equation, then discretized to spectral accuracy by the Nyström method and solved iteratively, giving typically 10 digits of accuracy. Its solution controls the evolution of particle locations and angles in a first-order system of ordinary differential equations. The formulation is placed on a rigorous footing by defining a generalized periodic Green’s function for the skew lattice. Numerically, the periodized integral operator is split into a near image sum— applied in linear time via the fast multipole method—plus a correction field solved cheaply via proxy Stokeslets. We use barycentric quadratures to evaluate particle interactions and velocity fields accurately, even at distances much closer than the node spacing. Using first- order time-stepping we simulate, for example, 25 ellipses per unit cell to 3-digit accuracy on a desktop in 1 hour per shear time. Our examples show equilibration at long times, force chains, and two types of blow-ups (jamming) whose power laws match lubrication theory asymptotics.

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

Finding the stationary states of a free energy functional is an important problem in phase field crystal (PFC) models. Many efforts have been devoted to designing numerical schemes with energy dissipation and mass conservation properties. However, most existing approaches are time-consuming due to the requirement of small effective step sizes. In this paper, we discretize the energy functional and propose efficient numerical algorithms for solving the constrained nonconvex minimization problem. A class of gradient-based approaches, which are the so-called adaptive accelerated Bregman proximal gradient (AA-BPG) methods, is proposed, and the convergence property is established without the global Lipschitz constant requirements. A practical Newton method is also designed to further accelerate the local convergence with convergence guarantee. One key feature of our algorithms is that the energy dissipation and mass conservation properties hold during the iteration process. Moreover, we develop a hybrid acceleration framework to accelerate the AA-BPG methods and most of the existing approaches through coupling with the practical Newton method. Extensive numerical experiments, including two three-dimensional periodic crystals in the Landau--Brazovskii (LB) model and a two-dimensional quasicrystal in the Lifshitz--Petrich (LP) model, demonstrate that our approaches have adaptive step sizes which lead to a significant acceleration over many existing methods when computing complex structures.

No abstract uploaded!

In this paper we derive new fractional error bounds for polynomial systems with exponents explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. Our major result extends the existing error bounds from the system involving only a single polynomial to a general polynomial system and do not require any regularity assumptions. In this way we resolve, in particular, some open questions posed in the literature. The developed techniques are largely based on variational analysis and generalized differentiation, which allow us to establish, e.g., a nonsmooth extension of the seminal Łojasiewicz’s gradient inequality to maxima of polynomials with explicitly determined exponents. Our major applications concern quantitative Hölderian stability of solution maps for parameterized polynomial optimization problems and nonlinear complementarity systems with polynomial data as well as high-order semismooth properties of the eigenvalues of symmetric tensors.

In this paper, we design and analyze third order positivity-preserving discontinuous Galerkin (DG) schemes for solving the time-dependent system of Poisson–Nernst–Planck (PNP) equations, which have found much use in diverse applications. Our DG method with Euler forward time discretization is shown to preserve the positivity of cell averages at all time steps. The positivity of numerical solutions is then restored by a scaling limiter in reference to positive weighted cell averages. The method is also shown to preserve steady states. Numerical examples are presented to demonstrate the third order accuracy and illustrate the positivity-preserving property in both one and two dimensions.

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 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

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

No abstract uploaded!

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.

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.

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