Задать вопрос:





Статьи

Статьи>> ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ФОРМИРОВАНИЯ ГЛОБАЛЬНОЙ МАТРИЦЫ ДЛЯ КОМПЛЕКСА КОНЕЧНО-ЭЛЕМЕНТНОГО АНАЛИЗА

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ФОРМИРОВАНИЯ ГЛОБАЛЬНОЙ МАТРИЦЫ ДЛЯ КОМПЛЕКСА КОНЕЧНО-ЭЛЕМЕНТНОГО АНАЛИЗА

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

Введение. Круг задач, решаемых в настоящее время с помощью систем конечно-элементного анализа, охватывает почти все сферы инженерных расчетов и постоянно расширяется. В настоящее время метод конечных элементов применяется как для расчетов напряженно-деформированного состояния, нестационарных тепловых и гидравлических процессов, так и для решения многих других актуальных научно-технических задач [1]. Большинство этих задач требуют высокой точности расчетов при сложной геометрии анализируемых объектов. Такие расчеты требуют значительных временных затрат, даже на современных компьютерах для целого ряда задач требуется нескольких часов счета, в связи с чем проблема повышения временной эффективности систем конечно-элементного анализа является актуальной и экономически целесообразной. Решение этой проблемы связано с выделением наиболее трудоемких этапов при решении прикладных задач уетоаом конечных элементов (МКЭ), и улучшению их временной эффективности на основе рациональных алгоритмических решений.

Важнейшим и одним из самых трудоемких этапов решения прикладных задач методом конечных элементов является этап формирования глобальной матрицы системы линейных алгебраических уравнений (СЛАУ). Временные затраты на этапы формирования матрицы и решения СЛАУ во многом определяют время решения задачи с помощью МКЭ в целом.

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

Данная особенность СЛАУ МКЭ определяет способ хранения коэффициентов СЛАУ в оперативной памяти ЭВМ в форме «ключ — не нулевое значение коэффициента», где ключом является индекс не нулевого коэффициента в строке матрицы. Такая форма представления матрицы позволяет избежать затрат памяти на хранение нулевых элементов. Значительная размерность СЛАУ в МКЭ для реальных задач делает данный способ хранения матрицы безальтернативным. Именно большая размерность глобальной матрицы и относительно сложный алгоритм формирования ее элементов приводят к значительным временным затратам на этом этапе в МКЭ и обусловливают необходимость поиска рациональных алгоритмических решений.

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

Проведенные эксперименты показывают, что на операции поиска нужной позиции в структуре хранения глобальной матрицы при использовании классического алгоритма формирования СЛАУ может потребоваться до 50 % времени, уходящего на этап формирования СЛАУ в целом. При этом можно утверждать, что к настоящему времени ресурс оптимизации алгоритмов поиска по ключу, применительно к матрице СЛАУ в МКЭ, в значительной степени исчерпан.

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

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

В настоящей статье авторы предлагают применить метод композиции алгоритмов для повышения временной эффективности решения задачи ключевого поиска при формировании глобальной матрицы СЛАУ. В качестве базового предлагается использовать классический алгоритм бинарного поиска [4]. Идея предлагаемой композиции состоит в том, что для определенного порога длины массива ключей, достигнутого алгоритмом бинарного поиска, более оптимальным по времени будет использование алгоритма последовательного поиска элементов в текущем фрагменте этого массива.

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

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

Введем следующие обозначения: n — длина исходного массива ключей; k—число шагов половинного деления, выполняемых в алгоритме бинарного поиска; а — количество элементарных операций языка реализации на одно половинное деление массива; ta — среднее время на одну обобщенную операцию в алгоритме бинарного поиска; b — количество элементарных операций языка реализации на один шаг последовательного поиска ключа; tb — среднее время на одну обобщенную операцию в алгоритме последовательного поиска;

Будем предполагать, что при последовательном поиске ключа количество сравнений в среднем, необходимых для получения результата, равно половине длины обрабатываемого массива ключей.

Учитывая, что после k шагов алгоритма бинарного поиска мы получим в среднем фрагмент массива ключей длиной n/2k, и вводя обозначениеT(n,k) для среднего времени выполнения композиционного алгоритма поиска, получаем оценку среднего времени в виде:

T(n,k)=atak+1/2*btb*n/2k. (1)

СПриравнивая нулю частную производную по k для выражения (1) и логарифмируя полученное выражение по основанию 2, определим оптимальное среднее значение k, минимизирующее функцию T(n,k), обозначив его через k :

k*=log2n+log2(btb/ata)+log2(ln2)-1. (2)

На основании формулы (2) можно определить пороговую среднюю длину фрагмента массива ключей /*, ниже которой рационально использовать алгоритм последовательного поиска:

l*=n/2k*=2atalog2e/btb=2,8853*ata/btb

Значение отношения определяется языком программирования, но слабо зависит от аппаратной среды реализации. В экспериментальном исследовании для задачи поиска элемента в структуре хранения разреженной глобальной матрицы в языке реализации C++ авторами было получено среднее значение этого отношения равное 2,94. Таким образом, для выбранного языка программирования значение l* = 8,4827 , но поскольку пороговая длина фрагмента массива представляет собой целое число, оптимальная пороговая длина lr равна 8 или 9.

Принятие решения по переключению на алгоритм последовательного поиска может приниматься не только на основании значения l* , но и на основании значения k* . Отметим, что значение k* в формуле (2) дает среднее значение числа шагов половинного деления и является действительным, но для принятия решения в программной реализации это число k* должно быть целым: kr = [k*], или kr = [k*]+1, что. приводит к выбору пороговой длины в более широком диапазоне. Поскольку функция логарифма растет достаточно медленно, а возможный диапазон изменения количества не нулевых элементов в строке глобальной матрицы не велик, то значение kr может быть фиксировано. Например, в диапазоне длин от 32 до 56 значение kr = 2 .

Проведенные на основе формулы (2) более детальные исследования и программные эксперименты показывают, что с учетом целочисленности kr, минимум функции T(n,k) достигается при таких значениях k , которым соответствует значение 1r в диапазоне 8 < 1r< 14. Экспериментальные результаты по определению рациональной пороговой границы для композиционного алгоритма поиска приведены на рисунке. Приведенные данные соответствуют реальной разреженной глобальной матрице с количеством ненулевых элементов в строке равным 45. Язык реализации — C++, процессор — Р IV 1,5 ГГц, значение tcp — среднее время поиска элемента в структуре разреженной матрицы в наносекундах при заданной пороговой длине переключения 1r на алгоритм последовательного поиска

На основе полученных теоретических результатов и программных экспериментов был разработан комбинированный алгоритм поиска элемента в структуре хранения разреженной глобальной матрицы для системы конечно-элементного анализа «Термоупругость — 3D» [5]. Пороговое значение 1r для переключения на алгоритм последовательного поиска выбиралось из условия: 1r < 14 . Полученные в результате экспериментальных исследований данные позволяют говорить о снижении в среднем времени счета для тепловых нестационарных задач в системе «Термоупругость — 3D» на 20 — 30 мин при общем расчетном времени порядка 3 — 5 ч.

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

Для системы «Термоупругость — 3D» авторами был разработан новый алгоритм формирования глобальной матрицы СЛАУ, который получил на звание алгоритма прохода по строкам. Основная идея нового алгоритма состоит в том, чтобы формировать значения коэффициентов глобальной матрицы, переходя по очереди от одного коэффициента строки к следующему за ним. Таким образом, в этом алгоритме исключается необходимость поиска нужной позиции в строке, как это происходит в классическом алгоритме.

Зависимость среднего времени поиска от пороговой длины

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

Для задач с одной степенью свободы каждый элемент матрицы связей позволяет рассчитать значения одного соответствующего ему коэффициента глобальной матрицы. Каждый элемент матрицы связей представляет собой массив, элементы которого, в свою очередь, содержат геометрические характеристики и характеристики физических параметров материалов КЭ, по которым может быть рассчитан вклад данного КЭ в соответствующий коэффициент глобальной матрицы. Таким образом, расчет значения коэффициента матрицы СЛАУ предполагает обращение к соответствующему элементу матрицы связей и последовательный расчет вкладов каждого КЭ, связанных с текущим коэффициентом глобальной матрицы.

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

В итоге объем дополнительных данных, необходимых для реализации нового алгоритма для различных типов задач, приблизительно кратен 5 — 6-ти объемам матрицы СЛАУ в классическом алгоритме. Однако при этом за счет исключения процесса поиска нужных позиций в строке глобальной матрицы достигается сокращение времени формирования СЛАУ на 30 — 35 % по сравнению с классическим алгоритмом.

Ресурсо-адаптивный алгоритм формирования глобальной матрицы. Выбор между классическим алгоритмом формирования СЛАУ и новым алгоритмом прохода по строкам, по сути, представляет собой достаточно стандартный для разработчиков программного обеспечения выбор между трудоемкостью вычислений и объемом оперативной памяти, необходимых для решения некоторой задачи. Компромисс между временной эффективностью и дополнительной памятью может быть оценен на основе комплексного критерия качества алгоритма [6]. Отметим, что использование современной объектно-ориентированной технологии программирования предоставляет возможность достаточно гибкого управления соотношением между трудоемкостью вычислений и объемом дополнительной оперативной памяти [7].

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

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

Адаптация к реальному компьютеру и рассчитываемой задаче может быть реализована следующим образом: количество строк т, для которых глобальная матрица формируется алгоритмом прохода по строкам с использованием дополнительной памяти, динамически определяется программной системой на основе анализа исходных данных задачи и информации о характеристиках той ЭВМ, с помощью которой будет проводиться этот расчет. Создание такого комбинированного адаптивного алгоритма предоставит пользователю возможность с максимальной эффективностью использовать то аппаратное обеспечение, которое находится в его распоряжении.

Заключение. Таким образом, в данной работе для повышения временной эффективности этапа формирования глобальной матрицы для системы конечно-элементного анализа «Термоупругость — 3D» предложены следующие алгоритмические решения:

композиционный алгоритм решения задачи ключевого поиска для классического алгоритма формирования глобальной матрицы;

новый, эффективный по времени, алгоритм прохода по строкам для формирования глобальной матрицы;

ресурсо-адаптивный алгоритм формирования матрицы на основе классического алгоритма и алгоритма прохода по строкам.

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

Список литературы

  1. Назаров Д. Обзор современных пакетов КЭ анализа. САПР и Графика. 2000. № 2.
  2. Стренг Г., Фикс Дж. . Теория метода конечных элементов. М.: Мир, 1977.
  3. Кнут Д.Э. . Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2002.
  4. Александров А.Е., Катков Р.Э. . Параметрическая оптимизация технических объектов на основе базовоговарианта с использованием программной системы «Термоупругость — 3D». Информационные технологии. 2002. № 9.
  5. Ульянов М.В. Комплексный критерий оценки качества алгоритмов. Программное и информационное обеспечение систем различного назначения на базе ПЭВМ: Межвузовский сборник научных трудов. Вып. 5.М., 2002.
  6. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на C++, 2-е изд.Пер. с англ. М.: «Издательство Бином». СПб.: «Невский диалект», 1999.
  7. Зенкевич О. Метод конечных элементов в технике.М.: Мир, 1975.

А.Е. Александров, А.А. Востриков, М.В. Ульянов
Справочник. Инженерный журнал. №10, 2004, с. 32-36

Статьи партнеров