Новый разреженный прямой решатель

(sparse direct solver) в системе ИСПА.

Александр Николаевич Мухин

Александр Александрович Мухин

 

 

Программа ИСПА широко применяется для расчета пространственных конечно-элементных (КЭ) моделей на статику, динамику, устойчивость и т. д. Такие расчеты связаны с большим временем решения систем линейных алгебраических уравнений с симметричной разреженной матрицей. Учитывая тенденцию неуклонного роста размерности задач (количество МКЭ уравнений достигает 2 000 000 - 3  000 000 и более), а также тот факт, что при поиске оптимального конструкторского решения приходится проводить многовариантные расчеты, возникает потребность в высокоэффективных методах решения систем линейных уравнений.

Также отметим, что высокоэффективные методы решения систем линейных уравнений необходимо разрабатывать учитывая неуклонный рост возможностей вычислительной техники. В последние годы вырос объем оперативной памяти и увеличилось количество вычислительных ядер процессора. Поэтому необходимо разрабатывать методы решения произвольной матрицы с возможностью задействования всех вычислительных возможностей компьютера.  Также необходимо создавать 64-х разрядные версии программ способных использовать оперативную память больше чем 4 Гб.

В данной статье рассмотрим новый разреженный метод факторизации матриц, реализованный в системе ИСПА и проведем сравнение с профильным методом факторизации.

Напомним, что факторизацией называется процедура приведения заданной матрицы K к треугольному виду. Так как в МКЭ анализе матрица K - симметричная, то целесообразно применять разложение K=LDLT, где L - нижняя треугольная матрица, D - диагональ факторизованной матрицы. Можно использовать разложение Холецкого K=LLT, но в этом случае матрица K должна быть положительно определенной. В расчетной практике  матрица K не всегда является положительно определенной.

Важным моментом при создании эффективного прямого метода решения линейных уравнений является оптимизация исходной матрицы. Оптимизация состоит в перестановке строк и столбцов матрицы K с целью уменьшения количества операций сложения и умножения в процессе решения. Это можно достичь двумя способами.

Первый – уменьшить ширину профиля исходной матрицы. По сути, это уменьшение ширины ленты транспонированной матрицы K. Для этой цели в ИСПА применяется обратный алгоритм Катхилла-Макки. Практика показывает, что при профильной оптимизации матрицы быстро решаются конструкции вытянутые в одном направлении. В этом случае получается небольшой профиль.

Второй - уменьшить количество заполнений, возникающих при факторизации матрицы. Под заполнениями понимаются ненулевые элементы, возникающие в матрице при ее факторизации на позициях нулевых элементов исходной матрицы. Количество заполнений существенно зависит от того, в каком порядке расставить уравнения.

В ИСПА применяется оптимизация методом вложенных сечений совместно с алгоритмом минимальной степени.

Метод вложенных сечений рассекает исходную конструкцию на две подконструкции, с как можно меньшим (по количеству уравнений) разделителем. То есть конструкция разделяется на три части. Затем для каждой из подконструкций процедура вложенных сечений повторяется снова и т.д. Далее процедура вложенных сечений запускается для каждого разделителя. В результате получается последовательность вложенных подсистем. Размер подсистемы ограничен некоторым количеством уравнений, например, 100 уравнений..

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

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

Может возникнуть закономерный вопрос. Зачем создавать свою программу решения разреженных линейных уравнений? Почему не взять стандартную библиотеку, например, от компании Интел?  В ИСПА это сделано по двум основным причинам.  Первая причина –необходимо, чтобы библиотека поставлялась в исходных кодах на языке С. Это необходимо для переноса процессора ИСПА под другую операционную систему. Такой эффективной библиотеки мы не нашли. Вторая причина и наверно самая главная – разреженный решатель должен повторять все функциональные возможности профильного решателя. А профильный решатель в процессе факторизации матрицы подкрепляет линейно-зависимые уравнения. То есть удаляет из исходной матрицы уравнения, что равносильно закреплению соответствующей степени свободы, и определяет реакцию, возникающую при закреплении степени свободы. В частности это позволяет решать не закрепленные статически-определимым образам конструкции. Эти подкрепленные реакции потом не войдут в пробу равновесия конструкции и проба равновесия в случае незакрепленной конструкции не сойдется. Расчет пробы равновесия - это тоже особенность процессора ИСПА. С ее помощью пользователь может оценить точность проведенного расчета, например, погрешность факторизации матрицы. И эти возможности должен поддерживать не только профильный, но и разрешенный решатель.

Также новый разреженный решатель поддерживает работу с 200 правыми частями, что для больших моделей потребует использовать динамическую виртуальную память. По этим основным причинам в ИСПА создан свой разреженный решатель, написанный на чистом языке С, что опять же важно для перехода под другую операционную систему.

Существует две версии ИСПА для WIDOWS. 32-х разрядная использует 4 Гб оперативной памяти, 64-х разрядная использует всю оперативную память компьютера, если оперативной памяти не хватает, то включается механизм виртуально-страничной памяти, то есть размер решаемой матрицы ограничен размером жесткого диска.

Профильный метод для решения любой задачи требует 300 Мб оперативной памяти. Связано это с тем, что в ИСПА реализован блочный профильный решатель. Размер блоков подобран таким образом, чтобы оптимально задействовать кэш процессора.  Если размер блоков увеличить, то время решения увеличивается примерно, а 2 раза.

 

Рассмотрим  модель представленную на рис. 1 модель  содержит 120 797 узлов и 137 489 элементов (673 409 уравнений). Решение будем проводить на компьютере с процессором Intel I7 – 935, 12 Гб оперативной памяти. Операционная система WINDOWS 7 (64 разряда). Решение будем проводить на 32-х разрядной версии. Модель состоит из 3-х 4-х узловых оболочек и 2-х узловых стержневых элементов.  Шарнирные соединения записаны уравнениями. 

 

Рис 1.

 

В дальнейшем решение будем проводить на 4 ядрах.

Профильный метод решения  – 47 минут. Разреженный метод – 44 сек.

 Еще раз проговорим, что чем больше минимальных разделителей найдет оптимизатор, тем быстрее будет решена полученная разреженная матрица. Очевидно, что в моделях из оболочек разделители будут меньше, чем в моделях из объемных элементов. Также время решения зависит от количества узлов в КЭ. Чем больше узлов в элементе, тем больше заполняемость матрицы и больше время решения. Поэтому рассмотрим модель из 10-ти узловых тетраэдров (рис. 2).

 

Рис 2.

 

Модель  содержит 243 591 узлов и 124 220 элементов (729 045 уравнения).  Профильный метод решения – 1 час 10 минут. Разреженный метод – 2 мин. 11  сек.

 

Теперь опять рассмотрим  модель представленную на рис. 3 модель  содержит 200 317 узлов и 219 219 элементов (1 147 890 уравнения).  Решение также будем проводить на 32-х разрядной версии.  Данная модель состоит из 3-х 4-х узловых оболочек.

 

Рис 3.

 

Разреженный метод–2 минут 30 сек. Профильный метод решения – 7 часов. Разреженный метод решает быстрее в 168 раз.

 

Теперь рассмотрим модель, которая содержит 2  579 080 уравнений (рис. 4). Решение уже будем проводить на 64-х разрядной версии. Для решения этой модели разреженный решатель требуется 16 Гб оперативной памяти, поэтому программа автоматически задействует виртуально-страничную память.

 

Рис 4.

 

Профильный метод решения – 4 часа 20 минут. Разреженный метод – 11 мин 49 сек.

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

 

В данной статье мы рассмотрели только вопросы связанные с факторизацией матрицы. Факторизованная матрица в дальнейшем используется при определении собственных форм и при расчете начальной потери устойчивости, что приводит к очень большому ускорению алгоритма Ланцоша. Но этому будет посвящена отдельная статья. 

 

З.Ы.

Автором идеи и реализации разреженного алгоритма в системе ИСПА является Мухин А.А. Все вопросы можно задать по адресу ispa@umail.ru

 

Июнь 2011 г.