Предполагая, что вы работаете с сеткой (поскольку вы упоминаете изображения — хотя это не гарантируется), что вас больше интересует скорость, чем точность (поскольку 5s кажется уже слишком медленным для 1 миллиона неизвестных), я вижу несколько вариантов.
Во-первых, забудьте о точных методах, таких как Холецкий (+переупорядочивание). Даже если они позволяют хранить факторизацию и повторно использовать ее для нескольких правых, вам, вероятно, придется хранить гигантские матрицы, которые кажутся неразрешимыми в вашем случае (надеюсь, вы переупорядочиваете строки/столбцы с обратным Катхиллом Макки или чем-то еще). в противном случае - это сильно разрежает факторизацию).
В зависимости от ваших граничных условий я бы сначала попробовал Matlab poisolv, который решает задачу Пуассона с использованием БПФ и возможных перепроекций, если вы хотите, чтобы граничные условия Дирихле были вместо периодических. Это очень быстро, но может не подходить для вашей проблемы (вы упоминаете наличие 25 nnz для матрицы Лапласа + идентичность: почему? - это матрица Лапласа высокого порядка, и в этом случае вас может больше интересовать точность, чем то, что я предполагаю или это на самом деле другая проблема, чем та, которую вы описываете?).
Затем вы можете попробовать многосеточные решатели, которые очень быстро работают с изображениями и гладкими задачами. Вы можете использовать простой метод релаксации для каждой итерации и каждого уровня мультисетки или использовать более сложные методы (например, предварительно обусловленный парный уровень сопряженного градиента). В качестве альтернативы вы можете выполнить более простой предварительно подготовленный сопряженный градиент (или даже SSOR) без многосеточной сетки, и если вас интересует только приблизительное решение, вы можете остановить итерации до полной сходимости.
Мои аргументы в пользу итеративных решателей:
- вы можете остановиться до сходимости, если вам нужна приблизительная задача
- вы по-прежнему можете повторно использовать другие результаты для инициализации вашего решения (например, если ваши разные прогоны соответствуют разным кадрам видео, то использование решения предыдущего кадра в качестве инициализации следующего имеет смысл).
Конечно, прямой решатель, для которого вы можете предварительно вычислить, сохранить и сохранить факторизацию, также имеет смысл (хотя я не понимаю вашего аргумента в пользу обновления ранга 1, если ваша матрица постоянна), поскольку остается сделать только обратную подстановку в время выполнения. Но, учитывая, что это игнорирует структуру проблемы (регулярная сетка, возможный интерес к результатам с ограниченной точностью и т. д.), я бы выбрал методы, разработанные для этих случаев, такие как методы, подобные Фурье, или многосеточные методы. Оба метода могут быть реализованы на графическом процессоре для получения более быстрых результатов (напомним, что графические процессоры скорее приспособлены для работы с изображениями/текстурами!).
Наконец, вы можете получить интересные ответы от scicomp.stackexchange, который больше ориентирован на численный анализ.
person
nbonneel
schedule
01.02.2013
