Алгоритмы для больших разреженных целочисленных матриц

Я ищу библиотеку, которая выполняет матричные операции над большими разреженными матрицами без ущерба для числовой стабильности. Матрицы будут 1000+ на 1000+, а значения матрицы будут между 0 и 1000. Я буду выполнять алгоритм исчисления индекса, поэтому буду генерировать (разреженные) векторы строк матрицы поочередно. Поскольку я разрабатываю каждую строку, мне нужно будет проверить линейную независимость. Как только я заполню свою матрицу требуемым количеством линейно независимых векторов, мне нужно будет преобразовать матрицу в уменьшенную форму ряда строк.

Проблема сейчас в том, что моя реализация использует гауссово исключение для определения линейной независимости (обеспечение формы эшелона строк после того, как все мои векторы строк найдены). Однако, учитывая плотность и размер матрицы, это означает, что записи в каждой новой строке со временем экспоненциально увеличиваются, поскольку для выполнения отмены необходимо найти lcm ведущих записей. Нахождение приведенной формы матрицы еще больше усугубляет проблему.

Поэтому у меня вопрос: есть ли алгоритм или, еще лучше, реализация, которая может проверить линейную независимость и решить форму сокращенного эшелона строк, сохраняя при этом записи как можно меньшими? Эффективный тест на линейную независимость особенно важен, поскольку в алгоритме исчисления индексов он выполняется гораздо чаще.

Вы можете работать по модулю нескольких больших простых чисел, чтобы получить результаты по модулю этих простых чисел, а затем проверить, есть ли рациональные числа с небольшим количеством цифр, удовлетворяющих этим сравнениям. Если да, вы можете проверить умножение матрицы на вектор, является ли найденное приближение точным. Это можно превратить в алгоритм точного решения.

Однако, если детерминант матрицы имеет размер порядка (что вполне возможно в вашем сценарии), вы, как правило, не найдете решений, для компонентов которых требуется менее нескольких тысяч цифр.$10^{1000}$

ссылки по теме:
http://cs.ucsb.edu/~koc/docs/j21.pdf
http://dl.acm.org/citation.cfm?id=355767
http://dl.acm.org/citation. CFM? ID = 355765