Fetching the paper…

Reading the bibliography…

2020

Butterfly factorization via randomized matrix-vector multiplications

Liu, Yang, Xing, Xin, Guo, Han et al.

Original
PDF
Post on X

Understand

This paper presents an adaptive randomized algorithm for computing the butterfly factorization of a $m\times n$ matrix with $m\approx n$ provided that both the matrix and its transpose can be rapidly applied to arbitrary vectors.

The resulting factorization is composed of $O(\log n)$ sparse factors, each containing $O(n)$ nonzero entries.
The factorization can be attained using $O(n^{3/2}\log n)$ computation and $O(n\log n)$ memory resources.
The proposed algorithm applies to matrices with strong and weak admissibility conditions arising from surface integral equation solvers with a rigorous error bound, and is implemented in parallel.

Butterfly factorization via randomized matrix-vector multiplications · Around

Built on

L. Hörmander
1971
Earlier work this paper cites.
R. W. Hockney
1994
Earlier work this paper cites.
E. Michielssen and A. Boag
1994
Earlier work this paper cites.
E. Michielssen and A. Boag
1996
Earlier work this paper cites.
L. Grasedyck and W. Hackbusch
2003
Earlier work this paper cites.
P. G. Martinsson and V. Rokhlin
2005
Earlier work this paper cites.
S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals
2007
Earlier work this paper cites.
E. Liberty, F. Woolfe, P.-G. Martinsson, V. Rokhlin, and M. Tygert
2007
Earlier work this paper cites.
E. Candès, L. Demanet, and L. Ying
2009
Earlier work this paper cites.

Similar

Special Issue on Continuous Wavelet Transform in Memory of Jean Morlet, Part I
M. O’Neil, F. Woolfe, and V. Rokhlin · 2010
Cited alongside, same era.
M. Tygert
2010
Cited alongside, same era.
N. Halko, P. Martinsson, and J. Tropp
2011
Cited alongside, same era.
J. M. Tamayo, A. Heldring, and J. M. Rius
2011
Cited alongside, same era.
H. Guo, J. Hu, and E. Michielssen
2013
Cited alongside, same era.
J. Poulson, L. Demanet, N. Maxwell, and L. Ying
2014
Cited alongside, same era.
S. Hao, P. Martinsson, and P. Young
2015
Cited alongside, same era.

Then

Y. Li, H. Yang, and L. Ying
2015
Later among the works it cites.
H. Guo, Y. Liu, J. Hu, and E. Michielssen
2017
Later among the works it cites.
Y. Li and H. Yang
2017
Later among the works it cites.
Y. Li, H. Yang, and L. Ying
2017
Later among the works it cites.
Y. Liu, H. Guo, and E. Michielssen
2017
Later among the works it cites.
E. Rebrova, G. Chávez, Y. Liu, P. Ghysels, and X. S. Li
2018
Later among the works it cites.
C. Gorman, G. Chávez, P. Ghysels, T. Mary, F.-H. Rouet, and X. S. Li
2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Y. Li, H. Yang, E. R. Martin, K. L. Ho, and L. Ying

2015

Cited alongside, same era.

Y. Liu and H. Yang

2020

Closest in time.