Butterfly factorization


Journal Article

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

Full Text

Duke Authors

Cited Authors

  • Li, Y; Yang, H; Martin, ER; Ho, KL; Ying, L

Published Date

  • January 1, 2015

Published In

Volume / Issue

  • 13 / 2

Start / End Page

  • 714 - 732

Electronic International Standard Serial Number (EISSN)

  • 1540-3467

International Standard Serial Number (ISSN)

  • 1540-3459

Digital Object Identifier (DOI)

  • 10.1137/15M1007173

Citation Source

  • Scopus