Publications [#328966] of Yingzhou Li

Papers Published

1. Li, Y; Yang, H, Interpolative butterfly factorization, Siam Journal on Scientific Computing, vol. 39 no. 2 (January, 2017), pp. A503-A531, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2021/04/15)

   Abstract:
   © 2017 Societ y for Industrial and Applied Mathematics. This paper introduces the interpolative butterfly factorization for nearly optimal implementation of several transforms in harmonic analysis, when their explicit formulas satisfy certain analytic properties and the matrix representations of these transforms satisfy a complementary low-rank property. A preliminary interpolative butterfly factorization is constructed based on interpolative low-rank approximations of the complementary low-rank matrix. A novel sweeping matrix compression technique further compresses the preliminary interpolative butterfly factorization via a sequence of structure-preserving low-rank approximations. The sweeping procedure propagates the low-rank property among neighboring matrix factors to compress dense submatrices in the preliminary butterfly factorization to obtain an optimal one in the butterfly scheme. For an N×N matrix, it takes O(N logN) operations and complexity to construct the factorization as a product of O(logN) 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 this algorithm.