Алгоритмы выполнения операций с большими целочисленными матрицами с числовой устойчивостью
Я ищу библиотеку, которая выполняет матричные операции над большими разреженными матрицами без ущерба для числовой стабильности. Матрицы будут 1000+ на 1000+, а значения матрицы будут в диапазоне от 0 до 1000. Я буду выполнять алгоритм расчета индекса (en.wikipedia.org/wiki/Index_calculus_algorithm), поэтому я буду генерировать (разреженные) векторы строк матрица серийно. Поскольку я разрабатываю каждую строку, мне нужно будет проверить линейную независимость. Как только я заполню свою матрицу требуемым количеством линейно независимых векторов, мне нужно будет преобразовать матрицу в уменьшенную форму ряда строк.
Теперь проблема в том, что моя реализация использует гауссово исключение для определения линейной независимости (обеспечение формы эшелона строк после того, как все мои векторы строк найдены). Однако, учитывая плотность и размер матрицы, это означает, что записи в каждой новой строке со временем экспоненциально увеличиваются, так как для выполнения отмены необходимо найти lcm ведущих записей. Нахождение приведенной формы матрицы еще больше усугубляет проблему.
Поэтому у меня вопрос: есть ли алгоритм или, еще лучше, реализация, которая может тестировать линейную независимость и решать форму сокращенного эшелона строк, сохраняя при этом записи как можно меньшими? Эффективный тест на линейную независимость особенно важен, поскольку в алгоритме исчисления индексов он выполняется гораздо чаще.
Заранее спасибо!
1 ответ
Обычно, если вы работаете с большими матрицами, люди используют LAPACK: эта библиотека содержит все основные матричные процедуры и поддерживает множество различных типов матриц (sparse, ...). Вы можете использовать эту библиотеку для реализации вашего алгоритма, я думаю, что это поможет вам