设 A 为 n x n 稀疏矩阵，由 (i,j,a) 形式的 m 个元组序列表示 --- 索引 i,j(介于 0 和 n-1 之间)，a 为值 a在底层字段 F 中。
在实践中，使用什么算法来求解 Ax = b 形式的线性方程组？请描述它们，不要只是链接到某个地方。
注释:
- 我对有限域的精确解以及使用浮点表示的实数或复数的精确解和有界误差解感兴趣。我认为有理数的精确或有界解也很有趣。
- 我对可并行解决方案特别感兴趣。
- A 不是固定的，即对于同一个 A，您不会得到不同的 b。
最佳答案
我使用和并行化的主要两种算法是 Wiedemann algorithm和 Lanczos algorithm (及其用于 GF(2) 计算的 block 变体)，两者都优于结构化高斯消除。
LaMacchia-Odlyzo 论文(Lanczos 算法的论文)将告诉您需要了解的内容。这些算法涉及将稀疏矩阵重复乘以向量序列。为了有效地做到这一点，您需要使用 right data structure (链表)使矩阵向量相乘时间与矩阵中非零值的数量成正比(即稀疏性)。
这些算法的并行化很简单，但优化将取决于系统的架构。矩阵向量乘法的并行化是通过将矩阵分成行 block (每个处理器得到一个 block )来完成的，每个行 block 分别乘以向量。然后将结果组合起来得到新的向量。
我已经广泛地完成了这些类型的计算。打破RSA-129 factorisation的原作者在 16,384 个处理器 MasPar 上使用结构化高斯消去法花了 6 周时间。在同一台机器上，我与 Arjen Lenstra(作者之一)合作，使用 Wiedemann block 在 4 天内求解矩阵，使用 Lanczos block 在 1 天内求解矩阵。不幸的是，我从未发表过结果!
关于algorithm - 稀疏 Ax = b 系统在实践中是如何解决的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52182988/