用稀疏矩阵乘二次形式矩阵的算法

我正在优化很大程度上依赖于自定义矩阵库的代码（它不会从项目中排除，因为它无处不在，这并不好，但这是事实。 ..）许多计算10〜20行和列的矩阵做，很多的计算包括二次形式像用稀疏矩阵乘二次形式矩阵的算法

C = A*B*A'

我意识到，往往是稀疏的，我想利用这个事实。所以我正在寻找一种能够处理这种情况的算法。数值稳定性很重要。有什么我可以使用的吗？由于“我们的”简单的O（n^3）乘法方法比特征3执行速度快，所以我不知道是否有任何我应该考虑的缺陷？

目标平台，因为我需要数值稳定性和矩阵不是很大，我猜Strassen的算法以及Coppersmith-Winograd算法不是我所期待的。相反，它只是一种方式的二次型乘法，可以让我轻松地检查A中的零。

感谢您的任何建议！

来源

2011-12-15 Philipp

我只是想知道是谁投了这个“关”吗？我觉得这个问题完全有效并且与编程有关。 – nacho4d 2011-12-15 09:27:37

我不确定你会从小型矩阵中利用稀疏性获得很多好处。 – 2011-12-15 10:57:22

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

来源

2011-12-15 09:00:42

有许多方法可以用比稠密矩阵更稠密的方式实现稀疏矩阵。我做到这一点是如下的一种方法：

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0]

变为非零元素

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*;

所以矩阵现在有O（n）的空间复杂度的代替邻的线性阵列（对于A * B，其中A和B是矩阵，您只需遍历每个数组以匹配元素（即a-> row == b-> col & & a-> col == b->行），并可能添加几个（内部产品）。这个算法的复杂度是O（n^2），而不是O（n^3）。这是因为您可以跳过采用可能导致零的内部产品的轻微操作。

来源

2012-01-09 22:02:40 Ataraxia

检出Highly Parallel Sparse Matrix-Matrix Multiplication algorothm

来源

2012-03-01 06:28:18

用稀疏矩阵乘二次形式矩阵的算法

回答

相关问题