Interpolative butterfly factorization


Journal Article

© 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.

Full Text

Duke Authors

Cited Authors

  • Li, Y; Yang, H

Published Date

  • January 1, 2017

Published In

Volume / Issue

  • 39 / 2

Start / End Page

  • A503 - A531

Electronic International Standard Serial Number (EISSN)

  • 1095-7197

International Standard Serial Number (ISSN)

  • 1064-8275

Digital Object Identifier (DOI)

  • 10.1137/16M1074941

Citation Source

  • Scopus