Scholarlink

<p>Alternative basis matrix multiplication algorithms are the fastest matrix multiplication algorithms in practice to date. However, are they numerically stable? We obtain the first numerical error bound for alternative basis matrix multiplication algorithms. Particularly, we derive a novel fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs, and achieves an improved asymptotic error bound. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously optimized. We provide high-performance parallel implementations of our algorithms with benchmarks showing that our algorithm is on par with the best in class for speed, and the best in class of for stability. Finally, we show that diagonal scaling stability improvement techniques for fast matrix multiplication are as effective for alternative basis algorithms, both theoretically and empirically. These findings promote the use of alternative basis matrix multiplication algorithms in practical applications.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Alternative Basis matrix multiplication is fast and stable†

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月26日

查看全文
  • Oded Schwartz,
  • Sivan Toledo,
  • Noa Vaknin,
  • Gal Wiernik

摘要

Alternative basis matrix multiplication algorithms are the fastest matrix multiplication algorithms in practice to date. However, are they numerically stable? We obtain the first numerical error bound for alternative basis matrix multiplication algorithms. Particularly, we derive a novel fast matrix multiplication algorithm with a 2-by-2 base case that simultaneously attains the optimal leading coefficient for arithmetic costs, and achieves an improved asymptotic error bound. We further show that arithmetic costs and error bounds of alternative basis algorithms can be simultaneously optimized. We provide high-performance parallel implementations of our algorithms with benchmarks showing that our algorithm is on par with the best in class for speed, and the best in class of for stability. Finally, we show that diagonal scaling stability improvement techniques for fast matrix multiplication are as effective for alternative basis algorithms, both theoretically and empirically. These findings promote the use of alternative basis matrix multiplication algorithms in practical applications.