Efficient Block Approximate Matrix Multiplication

Chuhan Yang, Christopher Musco

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Randomized matrix algorithms have had significant recent impact on numerical linear algebra. One especially powerful class of methods are algorithms for approximate matrix multiplication based on sampling. Such methods typically sample individual matrix rows and columns using carefully chosen importance sampling probabilities. However, due to practical considerations like memory locality and the preservation of matrix structure, it is often preferable to sample contiguous blocks of rows and columns all together. Recently, (Wu, 2018) addressed this setting by developing an approximate matrix multiplication method based on block sampling. However, the method is inefficient, as it requires knowledge of optimal importance sampling probabilities that are expensive to compute. We address this issue by showing that the method of Wu can be accelerated through the use of a randomized implicit trace estimation method. Doing so allows us to provably reduce the cost of sampling to near-linear in the size of the matrices being multiplied, without impacting the accuracy of the final approximate matrix multiplication. Overall, this yields a fast practical algorithm, which we test on a number of synthetic and real-world data sets. We complement our algorithmic contribution with the first extensive empirical comparison of block algorithms for randomized matrix multiplication. Our method offers a significant runtime advantage over the method of (Wu, 2018) and also outperforms basic uniform sampling of blocks. However, we find another recent method of (Charalambides, 2021) which uses sub-optimal but efficiently computable sampling probabilities often (but not always) offers the best trade-off between speed and accuracy.

    Original languageEnglish (US)
    Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
    EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959772952
    StatePublished - Sep 2023
    Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
    Duration: Sep 4 2023Sep 6 2023

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    ISSN (Print)1868-8969


    Conference31st Annual European Symposium on Algorithms, ESA 2023


    • Approximate matrix multiplication
    • randomized numerical linear algebra
    • trace estimation

    ASJC Scopus subject areas

    • Software

    Cite this