Browsing by Author "Ying, Lexing"

Filter results by typing the first few letters
Now showing 1 - 8 of 8
  • Thumbnail Image
    ItemOpen Access
    A fast algorithm for multilinear operators
    (Applied and Computational Harmonic Analysis, 2012) Yang, Haizhao; Ying, Lexing
    This paper introduces a fast algorithm for computing multilinear integrals which are defined through Fourier multipliers. The algorithm is based on generating a hierarchical decomposition of the summation domain into squares, constructing a low-rank approximation for the multiplier function within each square, and applying an FFT based fast convolution algorithm for the computation associated with each square. The resulting algorithm is accurate and has a linear complexity, up to logarithmic factors, with respect to the number of the unknowns in the input functions. Numerical results are presented to demonstrate the properties of this algorithm.
  • Thumbnail Image
    ItemOpen 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, ξ)e2π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, ξ)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 provided to demonstrate the practical advantages of the new algorithm.
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen Access
    Fast algorithm for periodic density fitting for Bloch waves
    (2017-04-23) Lu, Jianfeng; Ying, Lexing
    We 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.
  • Thumbnail Image
    ItemOpen Access
    Pole-based approximation of the Fermi-dirac function
    (Chinese Annals of Mathematics. Series B, 2009-12-01) Lin, Lin; Lu, Jianfeng; Ying, Lexing; E, Weinan
    Two approaches for the efficient rational approximation of the Fermi-Dirac function are discussed: one uses the contour integral representation and conformal mapping, and the other is based on a version of the multipole representation of the Fermi-Dirac function that uses only simple poles. Both representations have logarithmic computational complexity. They are of great interest for electronic structure calculations. © Editorial Office of CAM and Springer-Verlag Berlin Heidelberg 2009.
  • Thumbnail Image
    ItemOpen Access
    Quantitative Canvas Weave Analysis Using 2-D Synchrosqueezed Transforms: Application of time-frequency analysis to art investigation
    (Signal Processing Magazine, IEEE, 2015-07) Yang, Haizhao; Lu, Jianfeng; Brown, WP; Daubechies, I; Ying, Lexing
    Quantitative canvas weave analysis has many applications in art investigations of paintings, including dating, forensics, and canvas rollmate identification. Traditionally, canvas analysis is based on X-radiographs. Prior to serving as a painting canvas, a piece of fabric is coated with a priming agent; smoothing its surface makes this layer thicker between and thinner right on top of weave threads. These variations affect the X-ray absorption, making the weave pattern stand out in X-ray images of the finished painting. To characterize this pattern, it is customary to visually inspect small areas within the X-radiograph and count the number of horizontal and vertical weave threads; averages of these then estimate the overall canvas weave density. The tedium of this process typically limits its practice to just a few sample regions of the canvas. In addition, it does not capture more subtle information beyond weave density, such as thread angles or variations in the weave pattern. Signal processing techniques applied to art investigation are now increasingly used to develop computer-assisted canvas weave analysis tools.
  • Thumbnail Image
    ItemOpen Access
    Synchrosqueezed curvelet transform for two-dimensional mode decomposition
    (SIAM Journal on Mathematical Analysis, 2014-01-01) Yang, Haizhao; Ying, Lexing
    © 2014 Society for Industrial and Applied Mathematics.This paper introduces the synchrosqueezed curvelet transform as an optimal tool for two-dimensional mode decomposition of wavefronts or banded wave-like components. The synchrosqueezed curvelet transform consists of a generalized curvelet transform with application dependent geometric scaling parameters, and a synchrosqueezing technique for a sharpened phase space representation. In the case of a superposition of banded wave-like components with well-separated wave-vectors, it is proved that the synchrosqueezed curvelet transform is capable of recognizing each component and precisely estimating local wave-vectors. A discrete analogue of the continuous transform and several clustering models for decomposition are proposed in detail. Some numerical examples with synthetic and real data are provided to demonstrate the above properties of the proposed transform.
  • Thumbnail Image
    ItemOpen Access
    Synchrosqueezed wave packet transform for 2D mode decomposition
    (SIAM Journal on Imaging Sciences, 2013-10-22) Yang, Haizhao; Ying, Lexing
    This paper introduces the synchrosqueezed wave packet transform as a method for analyzing twodimensional images. This transform is a combination of wave packet transforms of a certain geometric scaling, a reallocation technique for sharpening phase space representations, and clustering algorithms for modal decomposition. For a function that is a superposition of several wave-like components with a highly oscillatory pattern satisfying certain separation conditions, we prove that the synchrosqueezed wave packet transform identifies these components and estimates their local wavevectors. A discrete version of this transform is discussed in detail, and numerical results are given to demonstrate the properties of the proposed transform. © 2013 Society for Industrial and Applied Mathematics.