Решение большой (n> 1000000) линейной системы уравнений - PullRequest
Новая
       116

Решение большой (n> 1000000) линейной системы уравнений

2 голосов
/ 13 февраля 2020

Я достиг своего предела по следующей проблеме:

Как часть моего кода FEA (в MATLAB) мне нужно найти x, x = A \ b . И A , и b имеют разреженную, сложную матрицу двойной точности и вектор соответственно. Размер A равен (n, n), а b равен (n, 1), где n равно 850000 и может увеличиваться до 2000000. Кроме того, A является симметричным c и в основном диагональным.

enter image description here

В моем распоряжении два кластера HP C, один с 5,7 ТБ ОЗУ и другой с 1,5 ТБ (но более быстрые ядра). Технически говоря, я могу решить систему как есть, и просто ждать примерно 15 дней. Однако мне нужно выполнить решение системы уравнений до 10х за симуляции. Поэтому 15 дней - неприемлемое количество времени.

Я пробовал итерационные методы, однако они не дали тех же результатов, что и оператор backsla sh. Также в некоторых случаях конвергенция не была получена.

Я преобразовал часть x = A \ b в формат mexa64, чтобы потенциально сократить время. Тем не менее, я боюсь, что это все еще займет дни.

Любые предложения о том, как решить эту проблему? Существуют ли коммерческие коды, которые могут сделать это быстрее / эффективнее? И как коммерческие пакеты FEA решают эту проблему, когда модель имеет более 1 миллиона узлов?

Любая помощь очень ценится! Заранее спасибо.

1 Ответ

0 голосов
/ 14 февраля 2020

Вычисление разреженной матрицы само по себе является большой областью. Единственное, что вы можете сделать, это получить в нем больше спецификации c и использовать более настраиваемое решение, так как Matlab не позволяет вам этого делать, посмотреть его исходный код и посмотреть, сможете ли вы что-нибудь улучшить. Как я знаю, в основном есть два метода решения разреженной линейной системы: прямой и итеративный. Для каждого типа существует множество алгоритмов. Например, Cholesky Decomposition имеет очень хорошую производительность и низкое использование памяти, но работает только на матрицах SPD (симметрия c Positive Definite). другими методами являются LU, LDL, QR et c. Каждый из них соответствует определенным c типам матриц для решения.

Matlab также использует один из этих методов за кулисами (не уверен, но я где-то читал, что он использовал SuiteSparse-код под оператором A/b) , В зависимости от типа вашей матрицы (будь то Symmetric Positive Definite или Non-symetric et c.) Вам нужно выбрать одну схему (я имею в виду итеративную или прямую). Я думаю, что методы Direct лучше подходят для такой большой системы (из-за ошибок округления). Также существуют решатели на основе графических процессоров, доступные как для прямых, так и для итеративных методов и с высокой степенью распараллеливания, но, возможно, они не подходят для вашей большой проблемы, когда размер факторизованной матрицы превышает 8 ГБ.

Шаги, которые вы должны сделать:

  • Определите тип вашей матрицы (SPD, Symmetri c или общий).
  • Выберите лучший прямой метод для вашей матрицы.
  • Найдите бесплатный или коммерческий пакет, который может справиться с такой факторизацией (примеры Eigen, Intel MKL, SuitSpare) и оптимизированный код также поддерживает параллельные вычисления.
  • Сделайте вашу руку немного грязной, напишите очень маленькую программу, которая принимает матрицу A и вектор b из файла и найдите x, используя один из этих пакетов, например, с кодом C ++ (они готовы использовать примеры кодов).

Также имейте в виду, что каждый метод и пакет могут изменить порядок матрицы перед началом вычисления, и выбор хорошего порядка может сильно повлиять на скорость или даже увеличить acy.

Эта ссылка также должна быть интересной:

Не инвертировать эту матрицу

Также две книги о разреженных матрицах:

  • Технология разреженных матриц Серхио Писсанецкого
  • Прямые методы для разреженных линейных систем - Тимоти А. Дэвис
...