Butterfly factorization

Loading...
Thumbnail Image

Date

2015-01-01

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

152
views
183
downloads

Citation Stats

Abstract

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

Department

Description

Provenance

Subjects

Citation

Published Version (Please cite this version)

10.1137/15M1007173

Publication Info

Li, Yingzhou, Haizhao Yang, Eileen R Martin, Kenneth L Ho and Lexing Ying (2015). Butterfly factorization. Multiscale Modeling and Simulation, 13(2). pp. 714–732. 10.1137/15M1007173 Retrieved from https://hdl.handle.net/10161/11654.

This is constructed from limited available data and may be imprecise. To cite this article, please review & use the official citation provided by the journal.


Unless otherwise indicated, scholarly articles published by Duke faculty members are made available here with a CC-BY-NC (Creative Commons Attribution Non-Commercial) license, as enabled by the Duke Open Access Policy. If you wish to use the materials in ways not already permitted under CC-BY-NC, please consult the copyright owner. Other materials are made available here through the author’s grant of a non-exclusive license to make their work openly accessible.