基于稀疏矩阵的二次型矩阵乘法算法

Question

我正在优化代码,它严重依赖于定制的Matrix库(不会从项目中排除它,因为它无处不在.这不好,但它是一个事实......)许多计算是用10-的矩阵完成的20行和列,许多计算包括二次形式

 C = A*B*A'

我意识到A经常是稀疏的,我想利用这个事实.所以我正在寻找一种能够处理这种情况的算法.数值稳定性很重要.有什么我可以用的吗？(我没有写我们的图书馆所以我不知道我是否应该考虑到任何陷阱？)

由于"我们的"简单O(n ^ 3)乘法在目标平台上执行速度比本征3快,因为我需要数值稳定性且矩阵不是很大,我猜Strassen的算法以及Coppersmith-Winograd算法都不是我正在寻找什么.相反,它只是二次形式乘法,让我可以轻松地检查A中的零.

谢谢你的任何建议!

Answer 1

存在这篇论文，处理快速稀疏矩阵乘法。所开发的算法将稀疏矩阵分为两部分：密集和稀疏，并对其应用快速乘法算法。所以对我来说，它看起来并不取决于矩阵的大小，就像你在施特拉森中提到的那样，而是取决于它是稀疏的这一事实。