我正在开发一个需要处理非常大的矩阵的 Java 应用程序。例如将两个 1000 万 * 1000 万矩阵相乘！当然，Java 堆甚至没有足够的空间来存储这些矩阵之一。我应该怎么办？我是否应该使用数据库来存储我的矩阵并将每个需要的部分都带入内存并一个接一个地相乘？
问问题
8052 次
9 回答
8
首先，一个 1000 万 x 1000 万的矩阵简直是巨大的。假设每个单元加倍并且没有过度存储，这些东西中的每一个都将是 800 TB。只需从主内存中读取每个单元格（如果它以某种方式神奇地适合那里，这显然不会发生），需要几天的时间。从任何一种合理的 SAN（我们将其放在 10GbE 上）执行此操作更可能需要几个月的时间。并且没有矩阵乘法具有 O(n) 复杂度 - 正常的方法是 O(n^3)。所以……你不是用内存映射文件、通用数据库或任何类似的东西来做这件事的。
执行此类操作的代码将在缓存效率上生死攸关，其中“缓存”包括充分利用主内存、本地磁盘驱动器。由于任何拥有超过一个 800 TB 矩阵的存储接口都必然是某种 SAN，因此您几乎肯定会涉及到多个服务器读取和处理它的不同部分。
有许多众所周知的方法可以并行化矩阵乘法（本质上是将各种大小的子矩阵相乘，然后组合结果），并通过围绕空间填充曲线组织数据来改变布局，以便访问模式具有合理的缓存局部性行/列排列。您肯定会想看看经典的LAPACK接口和设计、英特尔的 MKL、GotoBLAS作为针对特定现代硬件调整的 BLAS 功能的实现，然后您可能会冒险进入未开发的领域:-)
于 2009-03-18T04:38:56.260 回答
3
如果简单地执行矩阵乘法的复杂性是 O(n^3)，但确实存在更有效的算法。无论如何，对于一个 1000 万 * 1000 万的矩阵，这将需要很长时间，并且您可能会面临相同的堆问题，但具有递归性。
如果您对复杂的数学感兴趣，您可能会在本文中找到可以帮助您的工具。
于 2009-03-16T12:53:00.153 回答
2
于 2009-03-16T12:44:31.343 回答
2
由于这是一个如此庞大的计算，我认为您将在存储问题的同时遇到性能问题。所以我会考虑并行化这个问题，并让多个机器/核心来处理数据子集。
幸运的是，矩阵乘法解决方案会自然分解。但我会关注某种形式的网格或分布式计算解决方案。
于 2009-03-16T12:56:03.233 回答
2
使用适用于您的数据的任何稀疏矩阵算法。（假设您没有 2.4 PB 的磁盘空间来保存 3 个 10^8 平方非稀疏双精度矩阵，更不用说内存数据库的那么多 RAM - Blue Gene/Q 'only' 有1.6 PB。）
于 2009-03-16T12:58:03.837 回答
1
好吧，如果您被迫使用 Java 并且无法编写将其作为本机方法处理的代码（也就是说，通过告诉 Java 调用一些 C 代码），那么最有效的做法是使用简单的二进制文件。在这种情况下，我会远离数据库，因为它们比直接文件访问慢，而且您不需要它们提供的功能。
于 2009-03-16T12:46:52.600 回答
1
看看hadoop。
于 2009-03-16T12:54:02.193 回答
0
看看 CGL-MapReduce http://www.cs.indiana.edu/~jekanaya/cglmr.html#Matrix_Multiplication
于 2009-03-16T15:24:38.290 回答