Browsing by Author "Yang, Haizhao"

Now showing 1 - 9 of 9

Open 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.
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.
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.
Open Access
Preconditioning Orbital Minimization Method for Planewave Discretization
(Multiscale Modeling & Simulation) Lu, Jianfeng; Yang, Haizhao
Open 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.
Open 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.
Open 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.
Open Access
Synchrosqueezed wave packet transforms and diffeomorphism based spectral analysis for 1D general mode decompositions
(Applied and Computational Harmonic Analysis, 2015-01-01) Yang, Haizhao
© 2014 Elsevier Inc.Abstract This paper develops new theory and algorithms for 1D general mode decompositions. First, we introduce the 1D synchrosqueezed wave packet transform and prove that it is able to estimate instantaneous information of well-separated modes from their superposition accurately. The synchrosqueezed wave packet transform has a better resolution than the synchrosqueezed wavelet transform in the time-frequency domain for separating high frequency modes. Second, we present a new approach based on diffeomorphisms for the spectral analysis of general shape functions. These two methods lead to a framework for general mode decompositions under a weak well-separation condition and a well-different condition. Numerical examples of synthetic and real data are provided to demonstrate the fruitful applications of these methods.
Open Access
Treecode-based generalized Born method
(The Journal of Chemical Physics, 2011) Xu, Zhenli; Cheng, Xiaolin; Yang, Haizhao
We have developed a treecode-based O(Nlog N) algorithm for the generalized Born (GB) implicit solvation model. Our treecode-based GB (tGB) is based on the GBr6 [J. Phys. Chem. B 111, 3055 (2007)], an analytical GB method with a pairwise descreening approximation for the R6 volume integral expression. The algorithm is composed of a cutoff scheme for the effective Born radii calculation, and a treecode implementation of the GB charge–charge pair interactions. Test results demonstrate that the tGB algorithm can reproduce the vdW surface based Poisson solvation energy with an average relative error less than 0.6% while providing an almost linear-scaling calculation for a representative set of 25 proteins with different sizes (from 2815 atoms to 65456 atoms). For a typical system of 10k atoms, the tGB calculation is three times faster than the direct summation as implemented in the original GBr6 model. Thus, our tGB method provides an efficient way for performing implicit solvent GB simulations of larger biomolecular systems at longer time scales.