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 位字”)所以如果作者的实现在某处公开可用，答案是"is"，因为他们已经在使用它。如果此算法是用 C/C++ 或类似语言编写的，优化编译器可能会很好地使用 SIMD 对其进行矢量化，即使无需手动指定如何拆分寄存器(可以通过查看程序集来验证)。在不手动拆分寄存器的情况下用高级语言实现可以说是更可取的，因为这样编译器就可以针对任何目标机器的字长对其进行优化。