FAST MATRIX VECTOR MULTIPLICATION VIA INTERPOLATIVE DECOMPOSITION BUTTERFLY FACTORIZATION

Abstract

In scientific computing, rapidly evaluating dense matrix-vector multiplication is one of the most important tasks. This thesis is to design and apply interpolative decomposition butterfly factorization (IDBF), a data-sparse representation of complementary low-rank matrices, to different kinds of application scenarios with a nearly optimal computational cost. We divide this thesis into two parts. Part I concentrates on the design of multidimensional IDBF together with a phase recovery technique that is crucially important in many application domains of IDBF. Part II is dedicated to developing a fast algorithm for the spherical harmonic transform via IDBF.