Search

We systematically study a numerical procedure that reveals the asymptotically selfsimilar dynamics of solutions of partial differential equations (PDEs). This procedure, based on the renormalization group (RG) theory for PDEs, appeared initially in a conference proceedings [G. A. Braga, F. Furtado, and V. Isaia, in Proceedings of the Fifth International Conference on Dynamical Systems and Differential Equations, Pomona, CA, 2004, pp. 1--13]. A numerical version of the RG method, dubbed nRG, rescales the temporal and spatial variables in each iteration and drives the solutions to a fixed point exponentially fast, which corresponds to the self-similar dynamics of the equations. In this paper, we carefully examine and validate this class of algorithms by comparing the numerical solutions with either exact or asymptotic solutions of model equations found in the literature. The other contribution of the current paper is that we present several examples to demonstrate that this class of nRG algorithms can be applied to a wide range of PDEs to shed light on long time self-similar dynamics of certain physical systems modeled by PDEs. [ABSTRACT FROM AUTHOR]

In this paper we propose an efficient method to compress a high dimensional function into a tensor ring format, based on alternating least squares (ALS). Since the function has size exponential in d, where d is the number of dimensions, we propose an efficient sampling scheme to obtain O(d) important samples in order to learn the tensor ring. Furthermore, we devise an initialization method for ALS that allows fast convergence in practice. Numerical examples show that to approximate a function with similar accuracy, the tensor ring format provided by the proposed method has fewer parameters than the tensor-train format and also better respects the structure of the original function. [ABSTRACT FROM AUTHOR]

The goal of this paper is to describe the oscillatory microstructure that can emerge from minimizing sequences for nonconvex energies. We consider integral functionals that are defined on real valued (scalar) functions u(x) which are nonconvex in the gradient ∇ u and possibly also in u. To characterize the microstructures for these nonconvex energies, we minimize the associated relaxed energy using two novel approaches: (i) a semianalytical method based on control systems theory, (ii) and a numerical scheme that combines convex splitting together with a modified version of the split Bregman algorithm. These solutions are then used to gain information about minimizing sequences of the original problem and the spatial distribution of microstructure. [ABSTRACT FROM AUTHOR]

In this paper, we present a new multiscale d omain decomposition algorithm for computing solutions of static Eikonal equations. In our new method, the decomposition of the domain does not depend on the slowness function in the Eikonal equati on or the boundary conditions. The novelty of our new method is a coupling of coarse grid and fine grid solvers to propagate information along the characteristics of the equation efficiently. The method involves an iterative parareal-like update scheme in order to stabilize the method and speed up convergence. One can view the new method as a general framework where an effective coarse grid s olver is computed "on the fly" from coarse and fine grid solutions that are computed in previous iterations. We study the optimal weights used to define the effective coarse grid solver and the stable update scheme via a model problem. To demonstrate the framework, we develop a specific scheme using Cartesian grids and the fast sweeping method for solving Eikonal equations. Numerical examples are given to show the method's effectiveness on Eikonal equations involving a variety of multiscale slowness functions. [ABSTRACT FROM AUTHOR]

Surface hopping algorithms are popular tools to study dynamics of the quantum-classical mixed systems. In this paper, we propose a surface hopping algorithm in diabatic representations, based on time dependent perturbation theory and semiclassical analysis. The algorithm can be viewed as a Monte Carlo sampling algorithm on the semiclassical path space for a piecewise deterministic path with stochastic jumps between the energy surfaces. The algorithm is validated numerically and it shows good performance in both weak coupling and avoided crossing regimes [ABSTRACT FROM AUTHOR]

This paper discusses the multiscale analysis of the initial-boundary value problem for three-dimensional (3D) time-dependent Maxwell's equations in composite materials. The new contributions in this paper are the determination of higher-order correctors and an explicit convergence rate for the approximate solution. Consequently, a multiscale hybrid finite element finite-difference time-domain (FE-FDTD) method is presented. The numerical results demonstrate that this multiscale method has potential applications in engineering electromagnetics. [ABSTRACT FROM AUTHOR]

Superparameterization is a fast numerical algorithm to mitigate implicit scale separation of dynamical systems with large-scale, slowly varying "mean" and smaller-scale, rapidly fluctuating "eddy" term. The main idea of superparameterization is to embed parallel highly resolved simulations of small-scale eddies on each grid cell of coarsely resolved large-scale dynamics. In this paper, we study the effect of model errors in using superparameterization for filtering multiscale turbulent dynamical systems. In particular, we use a simple test model, designed to mimic typical multiscale turbulent dynamics with small-scale intermittencies without local statistical equilibriation conditional to the large-scale mean dynamics, and simultaneously force the large-scale dynamics through eddy flux terms. In this paper, we consider the Fourier domain Kalman filter for filtering regularly spaced sparse observations of the large-scale mean variables. We find high filtering and statistical prediction skill with superparameterization (identical to the skill with perfect model), beyond conventional approaches such as the "bare truncation model" that ignores completely the eddy fluxes and the "equilibrium closure" model that crudely approximates the eddy fluxes with classical averaging theory. We show that this high filtering skill is robust even for very sparse observation networks and turbulent signals with a very steep, -6, spectrum. This is a counterexample to naive thinking that the small-scale processes are not so important in multiscale turbulent dynamics with steep energy spectrum. We find that the high filtering skill with superparameterization is robust for small enough scale gap, provided that the filter prior model satisfies the classical linear controllability condition. We will demonstrate a spectacular failure of filtering deterministically forced true signals with the exactly perfect model that does not satisfy controllability condition and a dramatic improvement when the controllability condition is restored with additional stochastic forcings. This result reconfirms and justifies the counterintuitive viewpoint that judicious model errors (or noises) can help filtering turbulent signals. [ABSTRACT FROM AUTHOR]

Finding metastable sets as dominant structures of Markov processes has been shown to be especially useful in modeling interesting slow dynamics of various real world complex processes. Furthermore, coarse graining of such processes based on their dominant structures leads to better understanding and dimension reduction of observed systems. However, in many cases, e.g., for nonreversible Markov processes, dominant structures are often not formed by metastable sets but by important cycles or a mixture of both. This paper aims at understanding and identifying these different types of dominant structures for reversible as well as nonreversible ergodic Markov processes. Our algorithmic approach generalizes spectral-based methods for reversible processes by using Schur decomposition techniques which can also tackle nonreversible cases. We illustrate the mathematical construction of our new approach by numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper we derive a framework for multiscale approximation of elliptic problems on standard and mixed form. The method presented is based on a splitting into coarse and fine scales together with a systematic technique for approximation of the fine scale part, based on the solution of decoupled localized subgrid problems. The fine scale approximation is then used to modify the coarse scale equations. A key feature of the method is that symmetry in the bilinear form is preserved in the discrete system. Other key features are a posteriori error bounds and adaptive algorithms based on these bounds. The adaptive algorithms are used for automatic tuning of the method parameters. In the last part of the paper we present numerical examples where we apply the framework to a problem in oil reservoir simulation. [ABSTRACT FROM AUTHOR]

This paper introduces a new sweeping preconditioner for the iterative solution of the variable coefficient Helmholtz equation in two and three dimensions. The algorithms follow the general structure of constructing an approximate LDLI factorization by eliminating the unknowns layer by layer starting from an absorbing layer or boundary condition. The central idea of this paper is to approximate the Schur complement matrices of the factorization using moving perfectly matched layers (PMLs) introduced in the interior of the domain. Applying each Schur complement matrix is equivalent to solving a quasi-1D problem with a banded LU factorization in the 2D case and to solving a quasi-2D problem with B multifrontal method in the 3D case. The resulting preconditioner has linear application cost, and the preconditioned iterative solver converges in a number of iterations that is essentially independent of the number of unknowns or the frequency. Numerical results are presented in both two and three dimensions to demonstrate the efficiency of this new preconditioner. [ABSTRACT FROM AUTHOR]

This paper is concerned with the fast computation of Fourier integral operators of the general form ∫ℝd e²πɩΩ(x,k) f(k)dk, where k is a frequency variable, Ω(x, k) is a phase function obeying a standard homogeneity condition, and f is a given input. This is of interest, for such fundamental computations are connected with the problem of finding numerical solutions to wave equations and also frequently arise in many applications including reflection seismology, curvilinear tomography, and others. In two dimensions, when the input and output are sampled on N x N Cartesian grids, a direct evaluation requires O(N4) operations, which is often times prohibitively expensive. This paper introduces a novel algorithm running in O(N² log N) time, i.e., with near-optimal computational complexity, and whose overall structure follows that of the butterfly algorithm. Underlying this algorithm is a mathematical insight concerning the restriction of the kernel e²πɩΩ(x,k) to subsets of the time and frequency domains. Whenever these subsets obey a simple geometric condition, the restricted kernel is approximately low-rank; we propose constructing such low-rank approximations using a special interpolation scheme, which prefactors the oscillatory component, interpolates the remaining nonoscillatory part, and finally remodulates the outcome. A byproduct of this scheme is that the whole algorithm is highly efficient in terms of memory requirement. Numerical results demonstrate the performance and illustrate the empirical properties of this algorithm. [ABSTRACT FROM AUTHOR]

This paper describes two digital implementations of a new mathematical transform, namely, the second generation curvelet transform in two and three dimensions. The first digital transformation is based on unequally spaced fast Fourier transforms, while the second is based on the wrapping of specially selected Fourier samples. The two implementations essentially differ by the choice of spatial grid used to translate curvelets at each scale and angle. Both digital transformations return a table of digital curvelet coefficients indexed by a scale parameter, an orientation parameter, and a spatial location parameter. And both implementations are fast in the sense that they run in O(n2 log n) flops for n by n Cartesian arrays; in addition, they are also invertible, with rapid inversion algorithms of about the same complexity. Our digital transformations improve upon earlier implementations-based upon the first generation of curvelets-in the sense that they are conceptually simpler, faster, and far less redundant. The software CurveLab, which implements both transforms presented in this paper, is available at http://www.curvelet.org. [ABSTRACT FROM AUTHOR]

The computational singular perturbation (CSP) method of Lam and Goussis is an iterative method to reduce the dimensionality of systems of ordinary differential equations with multiple time scales. In [J. Nonlinear Sci., 14 (2004), pp. 59-91], the authors of this paper showed that each iteration of the CSP algorithm improves the approximation of the slow manifold by one order. In this paper, it is shown that the CSP method simultaneously approximates the tangent spaces to the fast fibers along which solutions relax to the slow manifold. Again, each iteration adds one order of accuracy. In some studies, the output of the CSP algorithm is postprocessed by linearly projecting initial data onto the slow manifold along these approximate tangent spaces. These projections, in turn, also become successively more accurate. [ABSTRACT FROM AUTHOR]

Biochemical processes in living cells are comprised of reactions with vastly varying speeds and molecular counts of the reactant species. Classical deterministic or stochastic approaches to modeling often fail to exploit this multiscale nature of the reaction systems. In this paper, we propose a jump-diffusion approximation to these types of multiscale systems that couples the two traditional modeling approaches. An error bound of the proposed approximation is derived and used to partition the reactions into two sets, where one set is modeled by continuous stochastic differential equations and the other by discrete state processes. The methodology leads to a very efficient dynamic partitioning algorithm which has been implemented for several multiscale reaction systems. The gain in computational efficiency is evident in all these examples, which include a realistically sized model of a signal transduction cascade coupled to a gene expression dynamics. [ABSTRACT FROM AUTHOR]

This paper presents an efficient multiscale butterfly algorithm for computing Fourier integral operators (FIOs) of the form (Lf)(x) = ∫...(x,ξ)e2πiΦ(x,ξ), where f(ξ)dξ, where Φ(x,ξ) is a phase function, a(x,ξ) is an amplitude function, and f (x) is a given input. The frequency domain is hierarchically decomposed into a union of Cartesian coronas. The integral kernel a(x,ξ)e2πiΦ(x,ξ) in each corona satisfies a special low-rank property that enables the application of a butterfly algorithm on the Cartesian phase-space grid. This leads to an algorithm with quasi-linear operation complexity and linear memory complexity. Different from previous butterfly methods for the FIOs, this new approach is simple and reduces the computational cost by avoiding extra coordinate transformations. Numerical examples in two and three dimensions are pr ovided to demonstrate the practical advantages of the new algorithm. [ABSTRACT FROM AUTHOR]

The paper introduces the butterfly factorization as a data-sparse approximation for the matrices that satisfy a complementary low-rank property. The factorization can be constructed efficiently if either fast algorithms for applying the matrix and its adjoint are available or the entries of the matrix can be sampled individually. For an N x N matrix, the resulting factorization is a product of O(log N) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied rapidly in O(N log N) operations. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we investigate theoretically the behavior of Meyer's image cartoon + texture decomposition model. Our main result is a new theorem which shows that, by combining the decomposition model and a well-chosen Littlewood--Paley filter, it is possible to extract almost perfectly a certain class of textures. This theorem leads us to the construction of a parameterless multiscale texture separation algorithm. Finally, we propose extending this algorithm into a directional multiscale texture separation algorithm by designing a directional Littlewood--Paley filter bank. Several experiments show the efficiency of the proposed method on both synthetic and real images. [ABSTRACT FROM AUTHOR]

To develop better image change detection algorithms, new models able to capture spatiotemporal regularities and geometries present in an image pair are needed. In this paper, we propose a multiscale formulation for modeling semilocal interimage interactions and detecting local or regional changes in an image pair. By introducing dissimilarity measures to compare patches and binary local decisions, we design collaborative decision rules that use the total number of detections obtained from the neighboring pixels for different patch sizes. We study the statistical properties of the nonparametric detection approach that guarantees small probabilities of false alarms. Experimental results on several applications demonstrate that the detection algorithm (with no optical flow computation) performs well at detecting occlusions and meaningful changes for a variety of illumination conditions and signal-to-noise ratios. The number of control parameters of the algorithm is small, and the adjustment is intuitive in most cases. [ABSTRACT FROM AUTHOR]

This paper is on the construction of energy-minimizing coarse spaces that obey certain functional constraints and can thus be used, for example, to build robust coarse spaces for elliptic problems with large variations in the coefficients. In practice they are built by patching together solutions to appropriate local saddle point or eigenvalue problems. We develop an abstract framework for such constructions, akin to an abstract Bramble--Hilbert-type lemma, and then apply it in the design of coarse spaces for discretizations of PDEs with highly varying coefficients. The stability and approximation bounds of the constructed interpolant are in the weighted L2 norm and are independent of the variations in the coefficients. Such spaces can be used, for example, in two-level overlapping Schwarz algorithms for elliptic PDEs with large coefficient jumps generally not resolved by a standard coarse grid or for numerical upscaling purposes. Some numerical illustration is provided. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Tomographic reconstruction from noisy projections do not yield adequate results. Mathematically, this tomographic reconstruction represents an ill-posed problem due to information missing caused by the presence of noise. Maximum a posteriori (MAP) or Bayesian reconstruction methods offer possibilities to improve the image quality as compared with analytical methods in particular by introducing a prior to guide the reconstruction and regularize the noise. With an aim to achieve robust utilization of continuity/connectivity information and overcome the heuristic weight update for other nonlocal prior methods, this paper proposes a novel patch similarity based mixture (PSM) prior model for tomographic reconstruction. This prior is defined by a weighted Gaussian distance between neighborhood intensities. The weight quantifies the similarity between local neighborhoods and is computed using a maximization entropy constraint. This prior is then introduced within a joint image/weight MAP computed tomography reconstruction algorithm. Several acceleration trials including Compute Unified Device Architecture (CUDA) parallelization is applied to alleviate the intensive patch distance computation involved in the joint algorithm. The method was tested with both synthetic phantoms and clinical computed tomography data and compared in accuracy with five other reconstruction algorithms which are filtered back-projection and Bayesian-based. Reconstruction results show that the proposed reconstructions are able to produce high-quality images with ensured iteration convergence. [ABSTRACT FROM AUTHOR]

Motivated by consensus control of networked systems with communication latency and randomly switching topologies, this paper studies stochastic approximation (SA) algorithms for systems with time delays and randomly switching dynamics. To accommodate realistic time delay systems, our formulation of the discrete-time systems does not impose bounds on delays when the sampling intervals become small. The switching dynamics are modeled as a finite-state Markov chain. The transition probability matrix of the Markov chain contains a small parameter, termed the transition frequency parameter, while the SA algorithm defines its updating speed by another small parameter called the adaptation stepsize. The interplay of the two parameters introduces multiscale system dynamics, whose interaction with time delay further complicates system analysis. Using weak convergence methods, convergence of the algorithm is obtained. The limit behavior of the scaled estimation errors is also analyzed. It is shown that, depending on relative scales between the transition frequency and adaptation stepsize, the SA algorithms demonstrate fundamentally different asymptotic behaviors. Such behaviors are rigorously characterized and illustrated by simulation. [ABSTRACT FROM AUTHOR]

Split Bergman methods introduced in [T. Goldstein and S. Osher, SIAM J. Imaging Sci., 2 (2009), pp. 323-343] have been demonstrated to be efficient tools for solving total variation norm minimization problems, which arise from partial differential equation based image restoration such as image denoising and magnetic resonance imaging reconstruction from sparse samples. In this paper, we prove the convergence of the split Bregman iterations, where the number of inner iterations is fixed to be one. Furthermore, we show that these split Bregman iterations can be used to solve minimization problems arising from the analysis baaed approach for image restoration in the literature. We apply these split Bregman iterations to the analysis based image restoration approach whose analysis operator is derived from tight framelets constructed in [A. Ron and Z. Shen, J. Funct. Anal., 148 (1997), pp. 408-447]. This gives a set of new frame based image restoration algorithms that cover several topics in image restorations, such as image denoising, deblurring, inpainting, and cartoon-texture image decomposition. Several numerical simulation results are provided. [ABSTRACT FROM AUTHOR]

This paper is concerned with the evaluation of the partial Fourier transform ux = Σ|k|

A variational approach to the estimation of generators for Markov jump processes from discretely sampled data is discussed and generalized. In this approach, one first calculates the spectrum of the discrete maximum likelihood estimator for the transition matrix consistent with the discrete data. Then the generator that best matches the spectrum is determined by solving a convex quadratic minimization problem with linear constraints (quadratic program). Here, we discuss the method in detail and position it in the context of maximum likelihood inference of generators from discretely sampled data. Furthermore, we show how the approach can be generalized to estimation from data sampled at nonconstant time intervals. Finally, we discuss numerical aspects of the algorithm for estimation of processes with high-dimensional state spaces. Numerical examples are presented throughout the paper. [ABSTRACT FROM AUTHOR]

Homology has long been accepted as an important computational tool for quantifying complex structures. In many applications these structures arise as nodal domains of real-valued functions and are therefore amenable only to a numerical study based on suitable discretizations. Such an approach immediately raises the question of how accurately the resulting homology can be computed. In this paper we present an algorithm for correctly computing the homology of one- and two-dimensional nodal domains. The approach relies on constructing an appropriate cubical approximation for the nodal domain based on the behavior of the defining function at the vertices of a fixed grid. Betti numbers for these cubical sets are readily computable using [T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology, Springer-Verlag, New York, 2004; W. Kalies, M. Mrozek, and P. Pilarczyk, Computational Homology Project, http://chomp.rutgers.edu/ (2006)]. Here, we present a technique to verify that the cubical representation is homeomorphic to the nodal domain and therefore preserves homology. To illustrate this approach we consider examples from three classes of nodal domains, including the time-dependent patterns generated by the Cahn-Hilliard model for spinodal decomposition. We use these results to examine the probability of correct homology computations given specific grid sizes as related to the analytic estimates presented in [S. Day et al., Electron. Res. Announc. Amer. Math. Soc., 13 (2007), pp. 60-73; K. Mischaikow and T. Wanner, Ann. Appl. Probab., 17 (2007), pp. 980-1018; K. Mischaikow and T. Wanner, submitted; P. Niyogi, S. Smale, and S. Weinberger, Discrete Comput. Geom., 39 (2008), pp. 419-441]. [ABSTRACT FROM AUTHOR]

In this paper we extend nonlocal smoothing techniques for image regularization in [G. Gilboa and S. Osher, Multiscale Model. Simul., 6 (2007), pp. 595-630] to surface regularization, with surfaces represented by level set functions. We test our algorithm on both phantom and observed surfaces, including city terrain and cortical surfaces. [ABSTRACT FROM AUTHOR]

This paper introduces an adaptive mesh and algorithm refinement method for fluctuating hydrodynamics. This particle-continuum hybrid simulates the dynamics of a compressible fluid with thermal fluctuations. The particle algorithm is direct simulation Monte Carlo (DSMC), a molecular-level scheme based on the Boltzmann equation. The continuum algorithm is based on the Landau-Lifshitz Navier-Stokes (LLNS) equations, which incorporate thermal fluctuations into macroscopic hydrodynamics by using stochastic fluxes. It uses a recently developed solver for the LLNS equations based on third-order Runge-Kutta. We present numerical tests of systems in and out of equilibrium, including time-dependent systems, and demonstrate dynamic adaptive refinement by the computation of a moving shock wave. Mean system behavior and second moment statistics of our simulations match theoretical values and benchmarks well. We find that particular attention should be paid to the spectrum of the flux at the interface between the particle and continuum methods, specifically for the nonhydrodynamic (kinetic) time scales. [ABSTRACT FROM AUTHOR]

This paper proposes a fast multilevel method using primal relaxations for the total variation image denoising and analyzes its convergence. The basic primal relaxation is known to get stuck at a nonstationary point (nearly a local minimum) of the minimization, whose solution is known to be "nonsmooth" in the space of functions with bounded variation. Our idea is to use coarse level corrections, overcoming the deadlock in a basic primal relaxation scheme and achieving much improvement over relaxation. Moreover, to reach a global minimizer, further refinement of the multilevel method is needed, and we propose a nonregular coarse level based on a patch-detection idea (relating to hemivariateness) to correct and improve the standard multilevel method. Both algorithmic and analytical results together with numerical experiments on both one- and two-dimensional images are presented. [ABSTRACT FROM AUTHOR]

The projection multilevel method can be an efficient solver for systems of nonlinear partial differential equations that, for certain classes of nonlinearities (including least-squares formulations of the Navier--Stokes equations), requires no linearization anywhere in the algorithm. This paper provides an abstract framework and establishes optimal $V$-cycle convergence theory for this method. [ABSTRACT FROM AUTHOR]

The goal of this paper is to reconstruct a collection of small inclusions inside a homogeneous object by applying a heat flux and measuring the induced temperature on its boundary. Taking advantage of the smallness of the inclusions, we design efficient noniterative algorithms for locating the inclusions from boundary measurements of the temperature. We illustrate the feasibility and the viability of our algorithms by numerical examples. [ABSTRACT FROM AUTHOR]

The search for efficient image denoising methods is still a valid challenge at the crossing of functional analysis and statistics. In spite of the sophistication of the recently proposed methods, most algorithms have not yet attained a desirable level of applicability. All show an outstanding performance when the image model corresponds to the algorithm assumptions but fail in general and create artifacts or remove image fine structures. The main focus of this paper is, first, to define a general mathematical and experimental methodology to compare and classify classical image denoising algorithms and, second, to propose a nonlocal means (NL-means) algorithm addressing the preservation of structure in a digital image. The mathematical analysis is based on the analysis of the "method noise," defined as the difference between a digital image and its denoised version. The NL-means algorithm is proven to be asymptotically optimal under a generic statistical image model. The denoising performance of all considered methods are compared in four ways; mathematical: asymptotic order of magnitude of the method noise under regularity assumptions; perceptual-mathematical: the algorithms artifacts and their explanation as a violation of the image model; quantitative experimental: by tables of L2 distances of the denoised version to the original image. The most powerful evaluation method seems, however, to be the visualization of the method noise on natural images. The more this method noise looks like a real white noise, the better the method. [ABSTRACT FROM AUTHOR]

In this paper a MUSIC (standing for multiple signal classification) algorithm for locating small inclusions buried in a half-space from the scattering amplitude at a fixed frequency is developed. The underlying application area which motivated this work is the imaging of antipersonnel mines from electromagnetic data, formulated as an inverse scattering problem for the Helmholtz equation. The algorithm makes use of an asymptotic expansion of the scattering amplitude. A derivation of the leading-order term in this asymptotic expansion and its application for designing a MUSIC type of algorithm are presented. The viability of this algorithm is documented by a variety of numerical results. [ABSTRACT FROM AUTHOR]

Molecular dynamics (MD) is widely used in simulations of biomolecular systems such as DNA and proteins, systems which are multiscale in nature. However, current time stepping integrators are not able to address the time scale problems. Multiscale integrators, in which the presence of "fast" modes does not affect the time integration of "slow" modes, are pressingly needed in light of the fast growing biological data generated from the many genome sequencing projects. In this paper, we present a new multiple time stepping (MTS) multiscale integrator with stochasticity built in for constant temperature molecular dynamics simulations, called the targeted mollified impulse method (TM). TM combines the mollified impulse method, which is a stabler version of Verlet-I/r-RESPA (reversible REference System Propagator Algorithm), and a self-consistent dissipative leapfrog integrator commonly used in dissipative particle dynamics. TM introduces the Langevin coupling in a targeted manner to stabilize the MTS integrator such that the total linear momentum is conserved and less randomness in slower modes is imposed. Numerical experiments of simple model problems provide evidence that TM samples from the canonical ensemble. Possible applications include kinetics calculations such as conformational transition rates, computation of structural quantities from a canonical ensemble, and approximation of dynamical quantities from a canonical ensemble. We present results for the last two by showing that both the radial distribution functions and the self-diffusion coefficient are correctly computed from the simulations of flexible TIP3P waters using TM with outermost time step of 16 fs and innermost time step of 2 fs. Compared to leapfrog with time step of 1 fs, the implementation of TM achieves a six-fold computational speedup, whereas Verlet-I/r-RESPA with outer time step of 4 fs and inner time step of 1 fs achieves only a three-fold speedup. We also show how to... [ABSTRACT FROM AUTHOR]

In this paper we study a variational approach for filling in regions of missing data in two-dimensionaland three-dimensionaldigitalimages. Applications of this technique include the restoration of old photographs and removal of superimposed text like dates, subtitles, or publicity, or the zooming of images. The approach presented here, initially introduced in [IEEE Trans. Image Pr cess.,10 (2001), pp. 1200-1211] is based on a joint interpolation of the image gray levels and gradient/isophotes directions, smoothly extending the isophote lines into the holes of missing data. The process underlying this approach can be considered as an interpretation of the Gestaltist's principle of good continuation. We study the existence of minimizers of our functional and its approximation by minima of smoother functionals. Then we present the numerical algorithm used to minimize it and display some numerical experiments. [ABSTRACT FROM AUTHOR]

Generalized polarization tensors (GPTs)are employed for the derivation of full asymptotic expansions of the perturbations in the steady-state voltage potentials that are due to the presence of dielectric inhomogeneities of small diameter. In this paper we investigate some important properties of these GPTs such as symmetry, positivity, and their relations to the Dirichlet-to-Neumann map and weighted volume. It is expected that these results will find important applications not only for developing efficient algorithms for identifying dielectric inhomogeneities of small diameter but as well for optimizing properties of dilute composite materials. [ABSTRACT FROM AUTHOR]

One of the aims of computer vision in the past 30 years has been to recognize shapes by numerical algorithms. Now, what are the geometric features on which shape recognition can be based? In this paper, we review the mathematical arguments leading to a unique definition of planar shape elements. This definition is derived from the invariance requirement to not less than five classes of perturbations, namely noise, affine distortion, contrast changes, occlusion, and background. This leads to a single possibility: shape elements as the normalized, affine smoothed pieces of level lines of the image. As a main possible application, we show the existence of a generic image comparison technique able to find all shape elements common to two images. [ABSTRACT FROM AUTHOR]