数値安定性を犠牲にすることなく、大きな疎行列で行列演算を実行するライブラリを探しています。行列は 1000+ x 1000+ になり、行列の値は 0 から 1000 の間になります。指数計算アルゴリズム (en.wikipedia.org/wiki/Index_calculus_algorithm) を実行するので、次の (スパース) 行ベクトルを生成します。マトリックスを順番に。各行を作成するときに、線形独立性をテストする必要があります。必要な数の線形独立ベクトルで行列を埋めたら、行列を縮小された行階層形式に変換する必要があります。
ここでの問題は、私の実装がガウス消去法を使用して線形独立性を判断していることです (すべての行ベクトルが見つかったら、行のエシュロン形式を確保します)。ただし、マトリックスの密度とサイズを考慮すると、これは、キャンセルを実行するために先頭のエントリの lcm を見つける必要があるため、新しい各行のエントリが時間の経過とともに指数関数的に大きくなることを意味します。行列の簡約形式を見つけると、問題がさらに悪化します。
だから私の質問は、エントリをできるだけ小さく保ちながら、線形独立性をテストし、削減された行階層形式を解決できるアルゴリズム、またはより良い実装はありますか? 線形独立性の効率的なテストは、インデックス計算アルゴリズムで最も多く実行されるため、特に重要です。
前もって感謝します！