用于执行大整数矩阵运算w /数值稳定性的算法

我正在寻找一个库，可以在大的稀疏矩阵上执行矩阵运算而不牺牲数值稳定性。矩阵将1000+ 1000+和矩阵的值将介于0和1000之间。我将执行索引演算算法（en.wikipedia.org/wiki/Index_calculus_algorithm），所以我将生成（稀疏）行向量串联矩阵。在我开发每一行时，我需要测试线性独立性。一旦我用所需数量的线性无关向量填充我的矩阵，然后我需要将矩阵转换为缩减的行梯形式。用于执行大整数矩阵运算w /数值稳定性的算法

现在的问题是，我的实现使用高斯消元来确定线性独立性（一旦找到所有的行向量，确保行梯队形式）。但是，考虑到矩阵的密度和大小，这意味着每个新行中的条目随着时间成指数地增大，因为必须找到主要条目的lcm以便执行取消。发现矩阵的简化形式进一步加剧了这个问题。

所以我的问题是，是否有算法，或更好的实现，可以测试线性独立性和解决减少行梯形式，同时保持条目尽可能小？对于线性独立性的有效测试尤为重要，因为在指数演算算法中，它是最重要的。

在此先感谢！

来源

2012-10-21 jgonagle

你使用哪种语言？ – DaveyLaser

我认为你把[标签：密码]放在那里，因为线性独立性测试可能与密码分析有关？ –

@owlstead：不，这个问题与密码学无关。 –

通常，如果您使用大型矩阵，人们使用LAPACK：该库包含所有基本矩阵例程并支持许多不同的矩阵类型（稀疏，...）。你可以使用这个库来实现你的算法，我认为它会帮助你

来源

2012-10-23 14:05:47 ISTB

用于执行大整数矩阵运算w /数值稳定性的算法

回答

相关问题