java处理大矩阵

断桥残雪断桥残雪 发布于 2015/03/15 08:15
阅读 972
收藏 0
请问如何用java快速处理较大矩阵的运算,比如维度为4000*4000的?矩阵相乘运算
加载中
0
battyman
battyman
这个矩阵很小吧?如果三个循环时间复杂度太高的话,用斯特拉森矩阵乘法,用分治策略将问题小化。但如果是上亿维度的矩阵呢,用MapReduce分到几台机器上算吧
0
Xsank
Xsank

Strassen算法仅仅比通用矩阵相乘算法好一点,因为通用矩阵相乘算法时间复杂度是 equation ,而Strassen算法复杂度只是 equation 。但随着n的变大,比如当n >> 100时,Strassen算法是比通用矩阵相乘算法变得更有效率。

根据wikipedia上的介绍,后来,Coppersmith–Winograd 算法把 N* N大小的矩阵乘法的时间复杂度降低到了: equation ,而2010年,Andrew Stothers再度把复杂度降低到了 equation ,一年后的2011年,Virginia Williams把复杂度最终定格为: equation

这真是个不好优化的问题~

0
Jeky
Jeky
如果是稀疏矩阵 可以搜索稀疏矩阵快速乘法 时间复杂度比O(n^2)大一点 具体得看稀疏程度
0
tonghuazhong
tonghuazhong
如果更大的话,用hadoop吧,有提供java api.
0
捏造的信仰
捏造的信仰
建议搜索 "java matrix calculation",我没做过这方面的功能但是我看搜索结果里面应该有很多有用的库。
返回顶部
顶部