# Browsing by Author "Li, Yingzhou"

Now showing 1 - 3 of 3

###### Results Per Page

###### Sort Options

Item Open Access A multiscale butterfly algorithm for multidimensional fourier integral operators(Multiscale Modeling and Simulation, 2015-01-01) Li, Yingzhou; Yang, Haizhao; Ying, Lexing© 2015 Society for Industrial and Applied Mathematics.This paper presents an efficient multiscale butterfly algorithm for computing Fourier integral operators (FIOs) of the form (Lf)(x) =∫ ℝ da(x, ξ)e^{2πiΦ(x,ξ)}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, ξ)e^{2π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 provided to demonstrate the practical advantages of the new algorithm.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 factorization(Multiscale Modeling and Simulation, 2015-01-01) Li, Yingzhou; Yang, Haizhao; Martin, Eileen R; Ho, Kenneth L; Ying, Lexing© 2015 Society for Industrial and Applied Mathematics.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 × N matrix, the resulting factorization is a product of O(logN) sparse matrices, each with O(N) nonzero entries. Hence, it can be applied rapidly in O(N logN) operations. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.