Как разреженные системы Ax = b решаются на практике?

Question

Пусть A - разреженная матрица nxn, представленная последовательностью из m наборов вида (i, j, a) --- с индексами i, j (между 0 и n-1) и значением a в нижележащем поле Ф.

Какие алгоритмы используются на практике для решения линейных систем уравнений вида Ax = b? Пожалуйста, опишите их, не просто ссылку где-нибудь.

Примечания:

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

Answer 1

Основными двумя алгоритмами, которые я использовал и распараллелил, являются алгоритм Видемана и алгоритм Ланцоша (и их блочные варианты для вычислений GF (2)), оба из которых являются лучше, чем структурированное гауссово исключение.

Бумага LaMacchia-Odlyzo (для алгоритма Ланцоша) расскажет вам, что вам нужно знать. Алгоритмы включают многократное умножение вашей разреженной матрицы на последовательность векторов. Чтобы сделать это эффективно, вам нужно использовать правильную структуру данных (связанный список), чтобы матрица-вектор умножала время пропорционально количеству ненулевых значений в матрице (т.е. разреженности).

Параллелизация этих алгоритмов тривиальна, но оптимизация будет зависеть от архитектуры вашей системы. Распараллеливание умножения матрицы на вектор выполняется путем разбиения матрицы на блоки строк (каждый процессор получает один блок), каждый блок строк умножается на вектор отдельно. Затем вы объединяете результаты, чтобы получить новый вектор.

Я много занимался этими типами вычислений. Первоначальным авторам, которые нарушили факторизацию RSA-129 , потребовалось 6 недель с использованием структурированного исключения Гаусса на 16384 процессорах MasPar. На той же машине я работал с Арьеном Ленстра (одним из авторов), чтобы решить матрицу за 4 дня с блоком Видемана и 1 день с блоком Ланцоша. К сожалению, я так и не опубликовал результат!