algorithm - 在具有两个元素的领域中利用 SIMD 实现 Peterson 和 Monico 的 Lanczos 算法

Question

（这个问题可能与“无软件推荐”规则调情；我理解为什么它可能会被关闭）。

在他们的论文F_2 Lanczos revisited中，Peterson 和 Monico 给出了 Lanczos 算法的一个版本，用于在 Z/2Z 上找到线性映射的内核的子空间。如果我粗略地阅读了他们的论文是正确的（无论是与否显然不是 SO 的问题），那么所提出的算法需要多次迭代，这些迭代与所用机器的字长成反比。作者使用 64 位字长实现了他们的概念验证算法。

是否存在该算法的公开可用实现，该算法利用宽 SIMD 字（可能显着）加速？

Answer 1

现有的实现将是软件推荐。一个更有趣的问题是“是否可以使用 SIMD 让这个算法运行得更快？” 从我的论文中看，听起来 SIMD 正是他们所描述的（“我们将把一个 64 位机器字 x 分成八个子字......其中每个......都是一个 8 位字”）所以如果作者的实现在某处公开可用，答案是“是”，因为他们已经在使用它。如果这个算法是用 C/C++ 或类似的东西编写的，即使没有手动指定如何拆分寄存器（可以通过查看程序集来验证），优化编译器也可能会很好地使用 SIMD 对其进行矢量化。