# Browsing by Subject "math.NA"

Now showing 1 - 20 of 34

###### Results Per Page

###### Sort Options

Item Open Access A convergent method for linear half-space kinetic equations(2017-04-23) Li, Q; Lu, J; Sun, WWe give a unified proof for the well-posedness of a class of linear half-space equations with general incoming data and construct a Galerkin method to numerically resolve this type of equations in a systematic way. Our main strategy in both analysis and numerics includes three steps: adding damping terms to the original half-space equation, using an inf-sup argument and even-odd decomposition to establish the well-posedness of the damped equation, and then recovering solutions to the original half-space equation. The proposed numerical methods for the damped equation is shown to be quasi-optimal and the numerical error of approximations to the original equation is controlled by that of the damped equation. This efficient solution to the half-space problem is useful for kinetic-fluid coupling simulations.Item Open Access A Diabatic Surface Hopping Algorithm based on Time Dependent Perturbation Theory and Semiclassical Analysis(2017-11-30) Fang, D; Lu, JSurface 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 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.Item Open Access A Hybrid Global-local Numerical Method for Multiscale PDEs(2017-04-23) Huang, Y; Lu, Jianfeng; Ming, PWe present a new hybrid numerical method for multiscale partial differential equations, which simultaneously captures both the global macroscopic information and resolves the local microscopic events. The convergence of the proposed method is proved for problems with bounded and measurable coefficient, while the rate of convergence is established for problems with rapidly oscillating periodic or almost-periodic coefficients. Numerical results are reported to show the efficiency and accuracy of the proposed method.Item Open Access A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic EquationsLu, Jianfeng; Lu, Yulong; Wang, MinThis paper concerns the a priori generalization analysis of the Deep Ritz Method (DRM) [W. E and B. Yu, 2017], a popular neural-network-based method for solving high dimensional partial differential equations. We derive the generalization error bounds of two-layer neural networks in the framework of the DRM for solving two prototype elliptic PDEs: Poisson equation and static Schr\"odinger equation on the $d$-dimensional unit hypercube. Specifically, we prove that the convergence rates of generalization errors are independent of the dimension $d$, under the a priori assumption that the exact solutions of the PDEs lie in a suitable low-complexity space called spectral Barron space. Moreover, we give sufficient conditions on the forcing term and the potential function which guarantee that the solutions are spectral Barron functions. We achieve this by developing a new solution theory for the PDEs on the spectral Barron space, which can be viewed as an analog of the classical Sobolev regularity theory for PDEs.Item Open Access A quasinonlocal coupling method for nonlocal and local diffusion models(2017-04-23) Du, Q; Li, XH; Lu, J; Tian, XIn this paper, we extend the idea of "geometric reconstruction" to couple a nonlocal diffusion model directly with the classical local diffusion in one dimensional space. This new coupling framework removes interfacial inconsistency, ensures the flux balance, and satisfies energy conservation as well as the maximum principle, whereas none of existing coupling methods for nonlocal-to-local coupling satisfies all of these properties. We establish the well-posedness and provide the stability analysis of the coupling method. We investigate the difference to the local limiting problem in terms of the nonlocal interaction range. Furthermore, we propose a first order finite difference numerical discretization and perform several numerical tests to confirm the theoretical findings. In particular, we show that the resulting numerical result is free of artifacts near the boundary of the domain where a classical local boundary condition is used, together with a coupled fully nonlocal model in the interior of the domain.Item Open Access A Surface Hopping Gaussian Beam Method for High-Dimensional Transport Systems(2017-04-23) Cai, Z; Lu, JWe propose a surface hopping Gaussian beam method to numerically solve a class of high frequency linear transport systems in high spatial dimensions, based on asymptotic analysis. The stochastic surface hopping is combined with Gaussian beam method to deal with the multiple characteristic directions of the transport system in high dimensions. The Monte Carlo nature of the proposed algorithm makes it easy for parallel implementations. We validate the performance of the algorithms for applications on the quantum-classical Liouville equations.Item Open Access Accelerated sampling by infinite swapping of path integral molecular dynamics with surface hopping(2017-11-30) Lu, Jianfeng; Zhou, ZhennanTo accelerate the thermal equilibrium sampling of multi-level quantum systems, the infinite swapping limit of a recently proposed multi-level ring polymer representation is investigated. In the infinite swapping limiting, the ring polymer evolves according to an averaged Hamiltonian with respect to all possible surface index configurations of the ring polymer. A multiscale integrator for the infinite swapping limit is also proposed to enable practical sampling based on the limiting dynamics, avoiding the enumeration of all possible surface index configurations, which grows exponentially with respect to the number of beads in the ring polymer. Numerical results demonstrate the huge improvement of sampling efficiency of the infinite swapping compared with the direct simulation of path integral molecular dynamics with surface hopping.Item Open Access An asymptotic preserving method for transport equations with oscillatory scattering coefficients(2017-04-26) Li, Q; Lu, JWe design a numerical scheme for transport equations with oscillatory periodic scattering coefficients. The scheme is asymptotic preserving in the diffusion limit as Knudsen number goes to zero. It also captures the homogenization limit as the length scale of the scattering coefficient goes to zero. The proposed method is based on the construction of multiscale finite element basis and a Galerkin projection based on the even-odd decomposition. The method is analyzed in the asymptotic regime, as well as validated numerically.Item Open Access Analysis of the divide-and-conquer method for electronic structure calculations(2017-04-26) Chen, J; Lu, JWe study the accuracy of the divide-and-conquer method for electronic structure calculations. The analysis is conducted for a prototypical subdomain problem in the method. We prove that the pointwise difference between electron densities of the global system and the subsystem decays exponentially as a function of the distance away from the boundary of the subsystem, under the gap assumption of both the global system and the subsystem. We show that gap assumption is crucial for the accuracy of the divide-and-conquer method by numerical examples. In particular, we show examples with the loss of accuracy when the gap assumption of the subsystem is invalid.Item Open Access Bold Diagrammatic Monte Carlo in the Lens of Stochastic Iterative Methods(2017-11-30) Li, Yingzhou; Lu, JianfengThis work aims at understanding of bold diagrammatic Monte Carlo (BDMC) methods for stochastic summation of Feynman diagrams from the angle of stochastic iterative methods. The convergence enhancement trick of the BDMC is investigated from the analysis of condition number and convergence of the stochastic iterative methods. Numerical experiments are carried out for model systems to compare the BDMC with related stochastic iterative approaches.Item Open Access Butterfly-Net: Optimal Function Representation Based on Convolutional Neural NetworksLi, Y; Cheng, X; Lu, JDeep networks, especially Convolutional Neural Networks (CNNs), have been successfully applied in various areas of machine learning as well as to challenging problems in other scientific and engineering fields. This paper introduces Butterfly-Net, a low-complexity CNN with structured hard-coded weights and sparse across-channel connections, which aims at an optimal hierarchical function representation of the input signal. Theoretical analysis of the approximation power of Butterfly-Net to the Fourier representation of input data shows that the error decays exponentially as the depth increases. Due to the ability of Butterfly-Net to approximate Fourier and local Fourier transforms, the result can be used for approximation upper bound for CNNs in a large class of problems. The analysis results are validated in numerical experiments on the approximation of a 1D Fourier kernel and of solving a 2D Poisson's equation.Item Open Access Complexity of randomized algorithms for underdamped Langevin dynamicsCao, Y; Lu, J; Wang, LWe establish an information complexity lower bound of randomized algorithms for simulating underdamped Langevin dynamics. More specifically, we prove that the worst $L^2$ strong error is of order $\Omega(\sqrt{d}\, N^{-3/2})$, for solving a family of $d$-dimensional underdamped Langevin dynamics, by any randomized algorithm with only $N$ queries to $\nabla U$, the driving Brownian motion and its weighted integration, respectively. The lower bound we establish matches the upper bound for the randomized midpoint method recently proposed by Shen and Lee [NIPS 2019], in terms of both parameters $N$ and $d$.Item Open Access Complexity of zigzag sampling algorithm for strongly log-concave distributionsLu, Jianfeng; Wang, LihanWe study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\varepsilon$ error in chi-square divergence with a computational cost equivalent to $O\bigl(\kappa^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$ gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ under a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.Item Open Access Cubic scaling algorithms for RPA correlation using interpolative separable density fitting(2017-04-23) Lu, J; Thicke, KWe present a new cubic scaling algorithm for the calculation of the RPA correlation energy. Our scheme splits up the dependence between the occupied and virtual orbitals in $\chi^0$ by use of Cauchy's integral formula. This introduces an additional integral to be carried out, for which we provide a geometrically convergent quadrature rule. Our scheme also uses the newly developed Interpolative Separable Density Fitting algorithm to further reduce the computational cost in a way analogous to that of the Resolution of Identity method.Item Open Access Detecting localized eigenstates of linear operators(2017-11-30) Lu, J; Steinerberger, SWe describe a way of detecting the location of localized eigenvectors of a linear system $Ax = \lambda x$ for eigenvalues $\lambda$ with $|\lambda|$ comparatively large. We define the family of functions $f_{\alpha}: \left\{1.2. \dots, n\right\} \rightarrow \mathbb{R}_{}$ $$ f_{\alpha}(k) = \log \left( \| A^{\alpha} e_k \|_{\ell^2} \right),$$ where $\alpha \geq 0$ is a parameter and $e_k = (0,0,\dots, 0,1,0, \dots, 0)$ is the $k-$th standard basis vector. We prove that eigenvectors associated to eigenvalues with large absolute value localize around local maxima of $f_{\alpha}$: the metastable states in the power iteration method (slowing down its convergence) can be used to predict localization. We present a fast randomized algorithm and discuss different examples: a random band matrix, discretizations of the local operator $-\Delta + V$ and the nonlocal operator $(-\Delta)^{3/4} + V$.Item Open Access Efficient construction of tensor ring representations from sampling(2017-11-30) Khoo, Y; Lu, J; Ying, LIn this note 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 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 less parameters than tensor-train format and also better respects the structure of the original function.Item Open Access Existence and computation of generalized Wannier functions for non-periodic systems in two dimensions and higherLu, Jianfeng; Stubbs, Kevin D; Watson, Alexander BExponentially-localized Wannier functions (ELWFs) are a basis of the Fermi projection of a material consisting of functions which decay exponentially fast away from their maxima. When the material is insulating and crystalline, conditions which guarantee existence of ELWFs in dimensions one, two, and three are well-known, and methods for constructing the ELWFs numerically are well-developed. We consider the case where the material is insulating but not necessarily crystalline, where much less is known. In one spatial dimension, Kivelson and Nenciu-Nenciu have proved ELWFs can be constructed as the eigenfunctions of a self-adjoint operator acting on the Fermi projection. In this work, we identify an assumption under which we can generalize the Kivelson-Nenciu-Nenciu result to two dimensions and higher. Under this assumption, we prove that ELWFs can be constructed as the eigenfunctions of a sequence of self-adjoint operators acting on the Fermi projection. We conjecture that the assumption we make is equivalent to vanishing of topological obstructions to the existence of ELWFs in the special case where the material is crystalline. We numerically verify that our construction yields ELWFs in various cases where our assumption holds and provide numerical evidence for our conjecture.Item Open Access Fast algorithm for periodic density fitting for Bloch waves(2017-04-23) Lu, Jianfeng; Ying, LexingWe propose an efficient algorithm for density fitting of Bloch waves for Hamiltonian operators with periodic potential. The algorithm is based on column selection and random Fourier projection of the orbital functions. The computational cost of the algorithm scales as $\mathcal{O}\bigl(N_{\text{grid}} N^2 + N_{\text{grid}} NK \log (NK)\bigr)$, where $N_{\text{grid}}$ is number of spatial grid points, $K$ is the number of sampling $k$-points in first Brillouin zone, and $N$ is the number of bands under consideration. We validate the algorithm by numerical examples in both two and three dimensions.Item Open Access Frozen Gaussian approximation for high frequency wave propagation in periodic media(2017-04-26) Lu, J; Yang, XPropagation of high-frequency wave in periodic media is a challenging problem due to the existence of multiscale characterized by short wavelength, small lattice constant and large physical domain size. Conventional computational methods lead to extremely expensive costs, especially in high dimensions. In this paper, based on Bloch decomposition and asymptotic analysis in the phase space, we derive the frozen Gaussian approximation for high-frequency wave propagation in periodic media and establish its converge to the true solution. The formulation leads to efficient numerical algorithms, which are presented in a companion paper [Delgadillo, Lu and Yang, arXiv:1509.05552].Item Open Access Frozen Gaussian approximation with surface hopping for mixed quantum-classical dynamics: A mathematical justification of fewest switches surface hopping algorithms(2017-04-23) Lu, J; Zhou, ZWe develop a surface hopping algorithm based on frozen Gaussian approximation for semiclassical matrix Schr\"odinger equations, in the spirit of Tully's fewest switches surface hopping method. The algorithm is asymptotically derived from the Schr\"odinger equation with rigorous approximation error analysis. The resulting algorithm can be viewed as a path integral stochastic representation of the semiclassical matrix Schr\"odinger equations. Our results provide mathematical understanding to and shed new light on the important class of surface hopping methods in theoretical and computational chemistry.