language-agnostic - BLAS 如何结合矩阵链乘法优化

Question

BLAS(基本线性代数子程序)提供了许多其他编程语言，比如我使用的 Matlab，以及快速例程来执行矩阵乘法等操作。

然而，当将多个矩阵相乘时，有一个最佳顺序来“括号”矩阵。取自 wikipedia article :

For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations

A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

本文继续讨论求解此乘法最佳顺序的方法。我的问题是，BLAS 中是否使用了这些优化程序中的任何一个？如果没有，如果我在 Matlab 等程序中明确定义矩阵乘法的顺序并适当使用括号，我可以获得更好的速度吗？

Answer 1

可以找到 BLAS 的规范定义 here并且不包括具有多个矩阵的调用。因此，我不希望遵循该定义的任何实现提供您提到的链接优化。很难给出明确的答案，因为BLAS在过去的30年里已经被做死，所以有many implementations谁知道呢，也许有些无聊的博士生决定在某个时候这样做:)

话虽如此，有些实现是 similar but not compatible with BLAS喜欢 Eigen它使用表达式模板 (...) 等功能智能地删除临时文件并在适当的时候启用延迟评估。这是有希望的，但它是否适用于矩阵链接我真的不知道。我怀疑不是，因为它没有包含在他们的 benchmark 中。 .

最重要的是，找到答案的最可靠方法是自己尝试一下。您可以很容易地检查您选择的语言/实现:只需尝试您在问题中的示例，但最好使用更大的尺寸，例如所有维度乘以 100。