Haizhao Yang
National University of Singapore

Title: O(N log N) algorithms for matrix multiplications from highly oscillatory phenomena

Abstract: One of the key problems in scientific computing is the acceleration of matrix computation for large problem sizes. This talk introduces several O(N log N) algorithms for dense matrix multiplications from highly oscillatory phenomena, e.g, evaluating oscillatory integral transform, performing special function transforms, solving boundary integral equations in the high-frequency regime, etc. Based on recent advances of randomized numerical linear algebra and matrix recovery, we propose efficient algorithms to approximate dense matrix-vector multiplication via fast non-uniform Fourier transforms and sparse matrix factorizations (e.g., butterfly factorizations and its combination with other hierarchical matrices).

Host: Kui Ren