Что такое быстрый простой решатель для большой матрицы Лапласа?
Мне нужно решить некоторые большие (N ~ 1e6) матрицы Лапласа, которые возникают при изучении резисторных сетей. Остальная часть сетевого анализа выполняется с помощью графика повышения, и я хотел бы остаться в C ++, если это возможно. Я знаю, что есть много и много матричных библиотек C ++, но никто, кажется, не является явным лидером по скорости или удобству использования. Кроме того, многие вопросы по этому вопросу, здесь и в других местах, по-видимому, быстро превращаются в списки белья, которые имеют ограниченную полезность. В попытке помочь себе и другим, я постараюсь сделать вопрос лаконичным и ответственным:
Какая библиотека лучше всего справляется со следующими требованиями?
- Тип матрицы: симметричная диагональная доминанта / лапласиан
- Размер: очень большой (N ~ 1e6), динамическое изменение размера не требуется
- Sparsity: Extreme (максимум 5 ненулевых членов в строке / столбце)
- Необходимые операции: найти x в A * x = b и умножить mat / vec
- Язык: C ++ (хорошо)
- Приоритет: скорость и простота кодирования. Я действительно предпочел бы избежать необходимости изучать совершенно новую инфраструктуру для этой одной проблемы или вручную писать слишком много вспомогательного кода.
Дополнительная любовь к ответам с минимальным рабочим примером …
Решение
Если вы хотите написать свой собственный решатель, с точки зрения простоты, трудно победить Гаусса-Зейделя итерация. Шаг обновления занимает одну строку, и его можно легко распараллелить. Последовательное перенапряжение (SOR) только немного сложнее и сходится гораздо быстрее.
Сопряженный градиент также прост в коде и должен сходиться гораздо быстрее, чем другие итерационные методы. Важно отметить, что вам не нужно формировать полную матрицу A, достаточно просто вычислить матричные векторные произведения A * b. Как только это сработает, вы можете снова улучшить коэффициент сходимости, добавив предварительный кондиционер, такой как SSOR (Symmetric SOR).
Вероятно, самый быстрый метод решения, который разумно написать сам, — это решатель на основе Фурье. По сути, это включает в себя БПФ с правой стороны, умножение каждого значения на функцию его координаты и взятие обратного БПФ. Вы можете использовать библиотеку FFT, как FFTW, или сверните свое собственное.
Хорошая ссылка на все это Первый курс по численному анализу дифференциальных уравнений Арье Изерлес.
Другие решения
Eigen довольно хорош в использовании и является одной из самых быстрых библиотек, которые я знаю:
Есть много связанных постов, вы могли бы посмотреть.
Я бы порекомендовал C ++ и Boost :: ublas, которые используются в UMFPACK и UBLAS разреженная матрица BOOST