Java 1.8矩阵乘法

Question

您是否认为使用Java 1.8中的新流接口能够实现稀疏矩阵操作？如果是，我们需要如何实现矩阵和操作。显然，我正在寻找它最终能够使用“自动”并行化。

- Riccardo Rigon

---

看起来应该是可能的。你实际上尝试过自己实现吗？ - Matt Ball

不，我没有，但是我在考虑在Scala中搜索类似的东西。 - Riccardo Rigon

这确实是一个有趣的问题（如果我有更多时间，我会尝试一下），但是可能有一些注意事项（就我所知，我不是专家）：1.有数十种可能的稀疏矩阵表示方法-哪种方法最好？2.“流式处理”的概念可能与必须进行乘法的严格访问模式不兼容，并且对于两个输入矩阵和结果矩阵都是不同的。3.稀疏GEMM的“并行”算法通常基于将其显式并行化到已知数量的处理器上... - Marco13

...并且依赖于使用流中的“未知”线程数的自动并行化，使得利用这些信息变得不可能。4. 为了避免Float和Double的（非）装箱，必须在原始流（float，double）上构建它。5. 性能很大程度上取决于缓存，这也无法通过流来影响。-尽管如此，我真的很想在这里看到一些方法，所以+1。 - Marco13

一旦您解决了账户问题，也许可以通过编辑原始问题来添加新信息。例如，如果您实际上更感兴趣的是“SparseMatrix*DenseVector”乘法，那就是另外一个故事了。 - Marco13

Answer 1

这可以明显地做到。下面是一个简单的SPMV（稀疏矩阵向量乘法）示例，其中稀疏矩阵用坐标 COO格式表示（这是最简单的稀疏格式之一）：

class COO {
    int x, y, value;
}

public static ArrayList<Integer> spmv(List<COO> values, ArrayList<Integer> v) {
    final ArrayList<Integer> result = new ArrayList<>(Collections.nCopies(v.size(), 0));
    values.stream().forEach(
            coo -> result.set(coo.x, result.get(coo.x) + coo.value * v.get(coo.y))
    );
    return result;
}

但我真诚地建议您使用预编码的东西，如果您不想花费未来3年的时间来理解稀疏矩阵操作的性能影响。这是一个相当大的研究/优化主题，需要考虑许多因素，例如（只是举几个例子）：

1. 调度/重新排序矩阵值以提高缓存性能
2. 为特定问题使用最佳存储格式（例如，请参见netlib上的此项调查）

有许多实现可以实现比手工实现高出数量级的性能改进。以下是其中一些，请查看：

1. Intel MKL Sparse BLAS

2. Nvidia's cuBLAS

如果这些绑定还不存在，我会自己写，不过像 la4j 这样的东西看起来非常有前途。

- paul-g