Содержание к диссертации
Введение
Глава 1. Метод граничных элементов в пространственных контактных задачах механики твердых тел 13
1.1. Основные положения теории упругости, необходимые для построения различных моделей механики твердых тел 13
1.1.1. Условные обозначения 13
1.1.2. Сосредоточенные силы в упругом теле 14
1.1.3. Тензор перемещения Грина 14
1.1.4. Тензор влияния Кельвина 15
1.1.5. Решение Миндлина 16
1.2. Контактная задача для заглубленного в упругое полупространство абсолютно жесткого штампа произвольной формы 18
1.2.1. Постановка задачи 18
1.2.2. Граничные интегральные уравнения 19
1.2.3. Численное решение 21
1.2.4. Упругое полупространство с условиями понижения порового давления 25
1.3. Программные средства для решения контактных задач теории
упругости методом граничных элементов 28
1.3.1. Преимущество метода граничных элементов для решения контактных задач на ЭВМ 28
1.3.2. Основные этапы решения контактных задач 29
1.3.3. Проблема расширяемости и модификации существующих программ 30
1.4. Эффективная дискретизация поверхностей при численном решении пространственных контактных задач 32
1.4.1. Основные требования к гранично-элементной дискретизации контактных поверхностей 32
1.4.2. Гранично-элементное представление контактных поверхностей сложной формы 33
1.4.3. Дискретизация осесимметричных поверхностей 34
1.4.4. Дискретизация плоских граничных макроэлементов 37
1.5. Выводы 39
Глава 2. Методы автоматической гранично-элементной дискретизации 42
2.1. Гранично-элементные сетки на поверхности конструкций осесимметричного и блочного типа 42
2.1.1. Гранично-элементные сетки на осесимметричных конструкциях 42
2.1.2. Гранично-элементные сетки на конструкциях блочного типа 49
2.2. Методы интерактивного построения гранично-элементной сетки 58
2.2.1. Пространственное перемещение вершин 58
2.2.2. Добавление новых вершин и граней 60
2.2.3. Удаление вершин и граней 61
2.2.4. Проверка граничной поверхности на правильность 62
2.2.5. Объединение граней 64
2.2.6. Дискретизация граней 65
2.2.7. Пример интерактивного построения поверхности сложной формы.. 66
2.3. Построение гранично-элементной сетки методом композиций 66
2.3.1. Проверка гранично-элементных сеток на замкнутость 69
2.3.2. Приведение гранично-элементной сетки к замкнутому виду 70
2.3.3. Метод композиций 71
2.3.4. Нумерация граничных элементов 75
2.3.5. Алгоритм метода композиций 77
2.4. Хеш-таблицы для быстрого поиска в алгоритмах построения гранично-элементной сетки 78
2.4.1. Хеш-таблица для узлов 79
2.4.2. Хеш-таблица для граничных элементов 81
2.5. Выводы 84
Глава 3. Визуальная среда построения пространственных гранично- элементных сеток и решения контактных задач 85
3.1. Программная модель визуальной среды SBEM-Contact 85
3.1.1. Структура программы 85
3.1.2. Библиотека типов 89
3.1.3. Утилиты 90
3.2. Утилиты геометрического построения гранично-элементной сетки 93
3.2.1. Утилиты генерации гранично-элементной сетки на осесимметричных и блочных конструкциях 93
3.2.2. Утилита построения пространственных гранично-элементных сеток методом композиций 94
3.2.3. Утилиты корректировки гранично-элементной сетки 95
3.3. Утилита решения пространственных контактных задач для абсолютно жесткого штампа заглубленного в упругое полупространство 97
3.3.1. Форма ввода 97
3.3.2. Отображение контактных напряжений на поверхности цветом 98
3.4. Проблемы решения системы линейных алгебраических уравнений
больших размеров 100
3.4.1. Параллельные вычислительные системы 102
3.4.2. Алгоритм решения линейно-алгебраических систем больших размеров на кластерах 106
3.5. Выводы 108
Заключение по
Список использованных источников
- Сосредоточенные силы в упругом теле
- Основные требования к гранично-элементной дискретизации контактных поверхностей
- Гранично-элементные сетки на осесимметричных конструкциях
- Утилиты геометрического построения гранично-элементной сетки
Введение к работе
Актуальность темы. Инженеры, ученые и специалисты в области физических наук в настоящее время широко используют численный эксперимент, основанный на приближенном решении уравнений, описывающих физическую задачу. Такой подход к решению физических задач получил широкое развитие с появлением мощных вычислительных машин, которые могли решать инженерные задачи, требующие хранения большого количества данных и проведения значительного объема вычислений.
Одним из первых приближенных методов был метод конечных разностей, в котором разрешающие уравнения задачи аппроксимировались с помощью локальных разложений неизвестных функций в ряды, как правило, в усеченные ряды Тейлора [25, 109]. Метод конечных элементов привлек к себе внимание исследователей тем свойством, что сплошная среда разбивается на ряд элементов, которые можно рассматривать как конкретные ее части. При этом этот метод может основываться как на вариационных принципах, так и на более общих выражениях метода взвешенных невязок. Диапазон задач, решаемых данным методом весьма широк, и включает в себя вопросы расчета конструкций, течения жидкости и другие виды задач [28, 60]. Другим важным направлением методов приближенного анализа было развитие смешанных принципов (вариационные методы), когда физические задачи можно выражать и решать самыми различными способами в соответствии с видом используемых аппроксимаций уравнений. Эти аппроксимации имеют основополагающее значение при машинной реализации различных численных методов [31, 84]. Методы интегральных уравнений по началу рассматривались как некий тип аналитического метода, несвязанный непосредственно с приближенными методами. Благодаря работам Н. И. Мусхелишвили, С. Г. Михлина, В. Д. Купрадзе [73, 84, 86] и др. эти методы стали использоваться главным образом в механике жидкости и задачах общей теории потенциала.
В начале 1970-х гг. последние достижения в формулировке конечных элементов начали обнаруживать их связь с формулировкой граничных интегральных уравнений и привели к появлению обобщенных криволинейных элементов. В 1970 году К. Бреббия исследовал связь различных приближенных методов с граничными интегральными уравнениями и впервые применил термин «Метод граничных элементов» [28]. Развитие сравнительно нового направления, основанного на гранично-интегральных уравнениях [5, 16, 66], позволяет решать современные проблемы физико-математического моделирования. В настоящее время наблюдается интенсивное развитие метода граничных элементов и применение его для приближенных решений различных задач в области теории потенциала, теплопроводности, теории упругости, механики жидкости, вязкопла-стичности и т. п. [1-11, 16, 28, 33-42, 122-129].
Решение физических задач методом граничных элементов в общем случае сводится к трем основным этапам: подготовка данных к расчетам {препроцессор), численное решение физических задач {процессор) и вывод результатов расчета в виде иллюстраций и таблиц {постпроцессор). Разбиение численной реализации решения на три этапа обусловлено тем, что каждый из указанных этапов может рассматриваться и решаться отдельно, заостряя внимание лишь на характере начальных и полученных результатов. Иными словами, средства реализации гранично-элементных сеток могут быть получены без конкретного представления о численной реализации решения контактной задачи, или наоборот - разрабатывать гранично-элементные методики решений, не заостряя внимание на алгоритмах и методах получения гранично-элементной сетки.
Вместе с тем в настоящее время актуальными остаются вопросы реализации алгоритмов метода граничных элементов в виде комплексов проблемно-ориентированных программ для проведения вычислительных экспериментов. Отсутствуют соответствующие гранично-элементные алгоритмы и программные средства. Все существующие программы (COSMOS, ЛИРА, FEM_MODELS, SCAD, ANSYS, Z_SOIL, PLAXIS и др.) основаны на конечно-
7 элементном методе [20]. До сих пор остается актуальной задача построения пространственной гранично-элементной сетки сложной формы. Иногда для геометрического моделирования и дискретизации пространственных поверхностей используют существующие программные средства (AutoCAD, CREDO, SCAD и др.) [17, 18, 58, 61, 66]. Но это не решает проблемы, так как задача построения гранично-элементной сетки с желаемыми качествами по-прежнему требует соответствующих навыков и тщательного труда (например, необходимо отслеживать соблюдение единого правила обхода узлов, а также отсутствие пересечений и перекрытий элементов) [61, 93, 94]. Кроме того, для реализации методов поиска наилучших (оптимальных) решений возникает существенная необходимость в алгоритмах генерации гранично-элементной сетки с меньшими затратами счетного времени [5]. Все это обуславливает актуальность темы исследования.
Диссертация выполнена на кафедре программирования и информационных технологий Воронежского государственного университета в соответствии с планом госбюджетных научно-исследовательских работ по теме: «Разработка и совершенствование алгоритмов, моделей и средств решения контактных задач теории упругости и строительной механики методом граничных элементов».
Цель и задачи исследования. Разработка эффективных методов и алгоритмов автоматической гранично-элементной дискретизации пространственных поверхностей сложной формы, обеспечивающих качественную подготовку данных к расчету.
Для достижения поставленной цели сформулированы следующие задачи исследования:
Рассмотреть существующие методы пространственной гранично-элементной дискретизации, применяемые в решении физических задач.
Разработать методы и алгоритмы построения пространственной гранично-элементной сетки для поверхностей сложной формы.
Разработать и реализовать эффективные программные средства для пространственной гранично-элементной дискретизации (препроцессор).
Произвести апробацию полученных результатов на примере решения пространственных контактных задач для абсолютно жестких штампов заглубленных в упругое однородное полупространство.
Методы исследования. При выполнении диссертационной работы применялись: дискретная математика и теория множеств, теория графов, численные методы интегрирования, алгебра матриц, аналитическая геометрия, современные методы и технологии программирования (Delphi, ООП, COM, OpenGL).
Научная новизна работы: В диссертационной работе получены следующие результаты, характеризующиеся научной новизной:
Разработан метод композиций для геометрических объектов, характерной новизной которого является сведение композиции к логическим операциям над двоичными кодами. Это позволяет быстро найти любое решение с любым количеством геометрических объектов.
Разработан алгоритм построения пространственной гранично-элементной сетки методом композиций геометрических объектов, гранично-элементное разбиение которых тривиально или уже известно. В отличие от метода фрагментальной дискретизации в новом методе не требуется аналитического представления поверхности.
Разработаны методы хеширования узлов и граничных элементов для сокращения времени выполнения алгоритмов построения пространственных гранично-элементных сеток. Хеширование узлов и граничных элементов является дополнительным улучшением реализации существующих или разрабатываемых методов гранично-элементной дискретизации.
Разработано программное средство (SBEM-Contact) предназначенное для автоматической подготовки данных к проведению вычислительного эксперимента (гранично-элементная дискретизация). Реализация SBEM-Contact основывалась на технологии СОМ, что предоставляет возможность расши-
9 рения и модификации программного продукта путем разработки и реализации новых методов гранично-элементной дискретизации без перекомпиляции и изменений всей программы, что не применяется в большинстве программ. На защиту выносятся.
Метод композиций для построения гранично-элементных сеток на конструкциях сложной формы путем объединения, вычитания и/или пересечения геометрических объектов, поверхность которых аппроксимирована ансамблем граничных элементов.
Методы интерактивного построения поверхностей состоящих из набора плоских многоугольников путем добавления, удаления или пространственного перемещения вершин и дискретизации полученной поверхности на граничные элементы.
Методы хеширования узлов и граничных элементов для сокращения времени выполнения алгоритмов построения пространственных гранично-элементных сеток.
Программное средство построения пространственной гранично-элементной сетки и решения контактных задач (SBEM-Contact) на основе компонентно-объектной модели, что предоставляет возможность расширения программного средства при расширении диапазона решаемых задач путем реализации и подключения новых утилит без перекомпиляции и изменений всей программы.
Научная новизна работы: В диссертационной работе получены следующие результаты, характеризующиеся научной новизной:
Разработан метод композиций для геометрических объектов, характерной
новизной которого является сведение композиции к логическим операциям
над двоичными кодами. Это позволяет быстро найти любое решение с лю
бым количеством геометрических объектов.
Разработан алгоритм построения пространственной гранично-элементной сетки методом композиций геометрических объектов, гранично-элементное разбиение которых тривиально или уже известно. В отличие от метода фрагментальной дискретизации в новом методе не требуется аналитического представления поверхности.
Разработаны методы хеширования узлов и граничных элементов для сокращения времени выполнения алгоритмов построения пространственных гранично-элементных сеток. Хеширование узлов и граничных элементов является дополнительным улучшением реализации существующих или разрабатываемых методов гранично-элементной дискретизации.
Разработано программное средство (SBEM-Contact) предназначенное для автоматической подготовки данных к проведению вычислительного эксперимента (гранично-элементная дискретизация). Реализация SBEM-Contact основывалась на технологии СОМ, что предоставляет возможность расширения и модификации программного продукта путем разработки и реализации новых методов гранично-элементной дискретизации без перекомпиляции и изменений всей программы, что не применяется в большинстве программ.
Практическая значимость. Результаты работы могут быть использованы для повышения эффективности работы существующих и разработке новых систем моделирования процесса вычислительного эксперимента основанного на методе граничных элементов. Полученные простые и эффективные алгоритмы построения пространственной гранично-элементной сетки обладают свойством минимальных затрат счетного времени, что позволяет использовать их в решении задач поиска наилучшей (оптимальной) геометрической формы рассчитываемой поверхности. Разработанное программное средство построения пространственной гранично-элементной сетки и решения контактных задач (SBEM-Contact) можно рекомендовать проектным или научно-
исследовательским организациям в качестве препроцессора для вычислительных экспериментов.
Аппробация работы. Основные результаты работы доложены на всероссийской конференции «Прикладная геометрия, построение расчетных сеток и высокопроизводительные вычисления» (г. Москва, ВЦ РАН, 2004 г.), международной научной конференции «Образование, наука, производство и управление в XXI веке» (С. Оскол, СОТИ, 2004 г.), конференции международной школы-семинара «Современные проблемы механики и прикладной математики» (г. Воронеж, 2005 г.), международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (г. Воронеж, 2005 г.), научных конференциях профессорско-преподавательского состава и научных работников ВГУ, 2001 - 2005 гг.
Публикации. По теме диссертационной работы опубликовано 16 работ, в том числе 15 статей и патент Государственного фонда алгоритмов и программ РФ.
Структура и объем работы. Диссертационная работа изложена на 151 стра-ницах, включает 5 таблиц, 39 рисунков, 4 определения и 5 утверждений с доказательствами. Состоит из введения, трех глав, заключения, списка литературы из 129 наименований и 8 приложений.
Краткое содержание работы. Первая глава посвящается основным положениям и фундаментальным методам решений контактных задач пространственной теории упругости. Также здесь проводится аналитический обзор существующих методов построения пространственных гранично-элементных сеток и программных средств, предназначенных для решения пространственных контактных задач.
Во второй главе приведены алгоритмы генерации гранично-элементной
сетки на поверхностях стандартного типа (осесимметричных и блочных), а
> <- * также методы построения сеток на поверхностях сложной формы: метод ком-
позиций и корректировки гранично-элементной сетки в интерактивном режиме.
12 Для сокращения времени выполнения разработанных алгоритмов предлагаются хеш-таблицы для узлов и гранично-элементных сеток.
Реализация программной модели визуальной среды SBEM-Contact и соответствующих утилит приводится в третьей главе.
В приложении 1-5 приведены основные листинги программного кода SBEM-Contact: библиотека типов, пример реализации файловой утилиты, функция вычисления нормали и хеш-таблицы, используемые при реализации алгоритмов геометрического построения пространственной гранично-элементной сетки.
В приложении 6 представлены примеры общего статического анализа для заглубленного в упругое полупространство абсолютно жесткого штампа, испытывающего действие пространственной системы нагрузок, где полученные контактные напряжения представлены на поверхности штампа в виде переходящего цветового спектра.
Автор выражает глубокую благодарность научному руководителю доценту Тюкачеву Н.А.
Сосредоточенные силы в упругом теле
Основные требования к гранично-элементной дискретизации контактных поверхностей При решении контактных задач теории упругости одним из самых сложных проблем является построение гранично-элементной сетки на поверхности контактного взаимодействия жесткого штампа с грунтом (упругим основанием). Разработчики программных средств, направленных на решение поставленной задачи, пытаются преодолеть три основные проблемы: 1) учет необходимых требований для гранично-элементной сетки в решаемой задаче; 2) реализация дискретизации как можно большего количества типов поверхностей; 3) оптимизация алгоритмов с целью уменьшения затрат счетного времени и памяти ЭВМ.
При разработке и реализации алгоритмов аппроксимации поверхности граничными элементами следует учесть важные требования, от которых зависит точность численного решения. Например, для решения рассматриваемых в данной работе контактных задач необходимы следующие условия [5, 28]:
1) граничная область контакта жесткого штампа с упругим полупространством аппроксимируется ансамблем плоских треугольных и четырехугольных элементов, которые не пересекаются и не перекрываются;
2) граничные элементы полностью покрывают аппроксимируемую область и сопряжены друг с другом ребрами и вершинами (узлами сетки);
3) строгое соблюдение правила обхода узлов граничных элементов: против часовой стрелки, при наблюдении со стороны грунта;
4) Центры масс граничных элементов, являющихся узлами коллокации, должны находиться внутри области граничного элемента и, по возможности, располагаться равномерно по всей контактной поверхности. Из перечисленных основных требований к гранично-элементной сетке видно, что не каждый алгоритм геометрического построения поверхности применим для решения поставленной задачи. Также многие стандартные программные продукты (AutoCAD, CREDO и др.) не применимы для генерации гранично-элементной сетки, так как в них учитываются многие требования для гранично-элементной аппроксимации [61, 93, 94].
При решении пространственных контактных задач теории упругости контактная поверхность аппроксимируется набором плоских граничных элементов, как правило, четырехугольных или треугольных. В общем случае разбиение предполагается смешанным, то есть с одновременным присутствием треугольных и четырехугольных граничных элементов. Необходимым условием к разбиению поверхности на граничные элементы является отсутствие пересечений и перекрытий, желательно, чтобы узлы гранично-элементной сетки были вершинами смежных граничных элементов. Локальная нумерация узлов на каждом элементе берется против часовой стрелки при наблюдении со стороны внешней к контактной поверхности нормали (то есть со стороны грунта).
Для всех типов поверхностей принята фрагментальная дискретизация, что соответствует предварительному разбиению контактной поверхности на граничные макроэлементы [5]. В качестве граничных макроэлементов принимаются поверхностные фрагменты, имеющие простейшую топологию. Как правило, это плоские треугольники и четырехугольники, части цилиндрических, конических и сферических поверхностей. В отдельных случаях используются граничные макроэлементы, уравнения поверхности которых могут быть заданы детерминировано.
Граничные макроэлементы разбиваются на отдельные граничные элементы с автоматической генерацией координат и узлов. Разбиение производится регулярно и не обязательно равномерно. Степень неравномерности разбиения в от 34 дельном граничном макроэлементе по различным направлениям задается параметрически и, по возможности, учитывает предполагаемый характер изменения контактных напряжений. Важным аспектом фрагментальной дискретизации является согласование по числу граничных элементов на линиях сопряжения сложных граничных макроэлементов. Это необходимо для улучшения численного решения и удобства при обработке и интерпретации полученных результатов.
Основные требования к гранично-элементной дискретизации контактных поверхностей
В строительстве одной из ответственных работ, требующих больших материальных затрат, является проектирование и расчет оснований и фундаментов. От фундамента зависит производственные, эксплуатационные и расчетно-конструктивные параметры здания или архитектурного сооружения [5, 21, 53, 78]. Чтобы получить экономичное решение при минимальных коэффициентах запаса требуется тщательные инженерно-изыскательские работы и решение ряда сложных задач геотехники и строительной механики, в том числе и контактных задач. Сложность последних заключается в повышении точности расчетов, что требует особых численно-аналитических подходов.
В промышленном и гражданском строительстве наиболее часто используются фундаментные конструкции осесимметричного и блочного типа. Поверхности данного типа можно легко представить в виде наборов простых гладких поверхностных фрагментов, которые легко аппроксимировать набором граничных элементов, используя интерполяционные формулы (1.19) - (1.23).
Гранично-элементные сетки на осесимметричных конструкциях
Осесимметричные фундаментные конструкции, применяемые в строительстве, можно представить в виде набора конических и сферических элементов, соединенных друг с другом круговыми основаниями (рис. 2.1). Каждый элемент задается четырьмя параметрами: тип боковой поверхности (прямой или сферический), высота, радиусы первого и второго основания.
Оптимальный алгоритм аппроксимации поверхности вращения, заданной соответствующими элементами состоит из трех этапов: 1) вычисляется количество граничных элементов и узлов сетки для выделения области памяти соответствующего размера; 2) по интерполяционным формулам (1.19) вычисляются узлы гранично-элементной сетки; 3) в соответствии с индексацией узлов задаются граничные элементы.
Для вычисления общего количества узлов и граничных элементов необходимо рассмотреть параметры дискретизации боковой поверхности и основания каждого элемента отдельно. Пусть заданы следующие параметры аппроксимации поверхности вращения: N - число элементов поверхности; Д,(,), i?2 - радиус первого и второго основания /-го элемента; Н{1) - высота /-го элемента; п - число меридиональных сечений; т{,) - число сечений высоты /-го элемента; q\l\ q - число сечений радиуса первого и второго основания /-го элемен
Предполагается, что радиусы оснований на стыках элементов отличны от нуля (иначе нарушается целостность фигуры). Следовательно, при Rf Ф Л,(,+1) (/ = 1, N -1) образуются кольца и, соответственно, требуется исключить не лежащие на поверхности узлы сетки, полученные в результате дискретизации элементов. Следует заметить, что в полученных формулах исключаются повторный подсчет узлов на границах фрагментов, что объясняет уменьшение на единицу числа разбиений последнего основания.
Общее число узлов гранично-элементной сетки получается в результате суммы количества узлов на всех фрагментах аппроксимируемой поверхности: N 1=1 Используя аналогичные рассуждения можно получить формулы для числа граничных элементов: = .««, 5=sign( ).rf .i, S?J = signC ).q .ri, S{l=n -ceil і = 1,(ЛГ-1); П2-Єі 1=1 Следует заметить, что число граничных элементов связано с числом узлов: S=S+n-2 Из анализа, проведенного в п. 1 Л, следует, что при аппроксимации поверх ности вращения образуется 2п треугольных и (S - 2п) четырехугольных эле ментов, где п - число меридиональных сечений, S - общее число граничных элементов.
Координаты узлов гранично-элементной сетки на основаниях в местах соединения элементов (на стыках) вычисляются по формулам аппроксимации круговых элементов
Гранично-элементные сетки на осесимметричных конструкциях
Сложность удаления вершины заключается в том, что если у удаляемой вершины имеется четыре или более соседних вершин не лежащих в одной плоскости, то это приводит к неоднозначности в создании новых граней, а значит - к различным вариантам результата удаления. Поэтому разработано не само удаление, а отсечение части многогранника, выделенного четырьмя смежными вершинами (далее называемые фиксированными). Это позволяет не только сохранить единственность решения и удалить намеченную вершину за конечное число шагов, но и предусмотреть удаление граней и ребер.
Без ограничения общности считается, что существует такая грань, которой принадлежат три фиксированных вершины. Данная грань позволяет определить ориентацию добавляемых граней (рис. 2.8). Это следует из геометрической структуры граничной поверхности [76].
Например, для удаления вершины 0 связанной с вершинами 1, 2, 3, 4 необходимо вырезать фрагменты [0, 3, 4] и [0, 2, 3] (рис. 2.10, а), а затем удалить полностью (рис. 2.10, б). рис. 2.10. Выполнение процедуры удаления узла 0 (штриховкой отмечены добавляемые фрагменты): а) отсечение фрагментов; б) удаление полностью 2.2.4. Проверка граничной поверхности на правильность Предложенные алгоритмы исключают возможность перекрытий и нарушение правила обхода узлов (ориентация граней), если корректируемая поверхность изначально имела правильную структуру, но на каждом шаге построения требуется проверять связность поверхности и отсутствие пересечений граней.
Определение 2.1. Поверхность Q называется связной, если для любых двух точек M,N eQ. существует непрерывная кривая, соединяющая данные точки и полностью принадлежавшая Q.
Так как любые две точки любой грани рассматриваемой поверхности можно соединить кривой, то для критерия связности достаточно рассмотреть вершины и ребра.
Утверждение 2.1. Поверхность Q, состоящая из набора плоских многоугольников, является связной тогда и только тогда, когда для любых двух вершин данной поверхности, существует цепочка ребер, соединяющая их.
Доказательство.
1) Требуется доказать, что если поверхность Q. является связной, то любые две вершины, можно соединить цепочкой ребер.
Пусть заданы любые две вершины. Требуется найти соответствующую цепочку ребер, соединяющую их. По определению связности данные вершины можно соединить кривой р, принадлежащей Q. Тогда кривая р будет пересекать или проходить по ребрам граней поверхности Q. Без ограничения общности определения связности точки пересечений ребер в гранях можно соединить кривой, проходящей по ребрам. В таком случае можно построить кривую, проходящую по ребрам поверхности Q, которая и будет искомой цепочкой. Так как данные две вершины любые, Утверждение доказана.
2) Требуется доказать, что если любые две вершины можно соединить це почкой ребер, то поверхность Q связная.
Так как грани поверхности Q тоже являются связными, то любые точки данной грани можно соединить с вершинами, которые, по условию, можно соединить цепочкой ребер. Следовательно, для любой точки поверхности Q можно построить непрерывную кривую, соединяющую данные точки, тогда Q является связной по определению, что и требовалось доказать.
Алгоритм определения связности граничной поверхности основан на представлении граничной поверхности в виде графа [22], где вершины поверхности являются узлами, а ребра - дугами. Очевидно, что если для одной вершины можно найти путь, проходящий по ребрам, до всех вершин, то можно найти соответствующий путь между любыми вершинами (например, проходящий через данную точку).
Утилиты геометрического построения гранично-элементной сетки
Кластерные технологии стали логическим продолжением развития идей, заложенных в архитектуре МРР систем. Если процессорный модуль в МРР системе представляет собой законченную вычислительную систему, то кластер использует в качестве таких вычислительных узлов обычные серийно выпускаемые компьютеры. Появление высокоскоростного сетевого оборудования и специального программного обеспечения, такого как система MPI [59, 87], реализующего механизм передачи сообщений над стандартными сетевыми протоколами, сделали кластерные технологии общедоступными. Сегодня не составляет большого труда создать небольшую кластерную систему, объединив вычислительные мощности компьютеров отдельной лаборатории или учебного класса. При этом не накладывается никаких ограничений на состав и архитектуру узлов: каждый из узлов может функционировать под управлением своей собственной операционной системы (Linux, FreeBSD, Solaris, Tru64 Unix, Windows NT) [30, 47]. Когда узлы кластера неоднородны, говорят о гетероген ных кластерах [24, 83]. Другим важным прорывом в разработке параллельных систем кластерной архитектуры послужило появление мировой сети Internet, так как это дало возможность соединять вычислительные узлы, находящиеся на больших расстояниях [47], т. е. разрабатывать единую параллельную вычислительную систему между научно-исследовательскими подразделениями. Однако, скорость передачи данных по сети Internet весьма невысока и компьютеры обычных пользователей (а таких, как правило, большинство в подобных проектах), не работают 24 часа в сутки, что накладывает некоторые очень серьёзные ограничения архитектуре распределённых вычислений. Таким образом, модель вычислений должна учитывать низкую скорость передачи данных между вычислительными узлами, а также их непостоянную доступность. Очевидно, задача, которую пытаются решить, должна обладать определёнными свойствами (например, слабой связанностью).
В заключение следует отметить, что судя по материалам сервера http://Parallel.ru, к ноябрю 2003 года количество кластеров в списке ТОР500 (мировой рейтинг суперкомпьютеров - http://www.top500.org/), составляет 208, а в июне 2003 составляло всего лишь 149. Более того, судя по этой же ноябрьской редакции, на третье место вырвался кластер Virginia Polytechnic Institute and State University, состоящий из 2200 процессоров Apple G5 2.0 GHz. Основной причиной этой тенденции является сравнительно небольшая стоимость кластерных систем. Как уже было сказано ранее, это объясняется прежде всего тем, что кластеры собирают из стандартных аппаратных компонентов (в том числе из персональных компьютеров), а это, в свою очередь, позволяет применять совместимое программное обеспечение [24, 83]. 3.4.2. Алгоритм решения линейно-алгебраических систем больших размеров на кластерах Для решения систем линейно-алгебраических уравнений, занимаемых объем памяти (3.3) менее 1 гигабайта, применялся обычный персональный компьютер IBM AT с процессором Intel Pentium III 733 МГц наращиванием опера тивной памяти до нужного размера. Решение систем максимальных размеров (более 1 Гб) вызвало некоторые трудности, так как в данном случае нет возможности полностью загрузить в оперативную память матрицу системы.
Для последних случаев наиболее эффективно применять блочную технологию решения больших алгебраических задач [46], предложенную академиком В. В. Воеводиным в середине 60-х годов прошлого столетия. Предложенный подход к решению поставленной задачи заключается в следующем. Матрица линейно-алгебраических уравнений вводится в оперативную память не сразу, а последовательно по одной строке, каждая из которых подвергается преобразованиям метода Гаусса (вычитание предыдущих строк). Таким образом, после к-го шага полученную строку будет целесообразнее хранить в массиве размерностью (п-к + \) (к = \,п) и, соответственно, для проведения (А: + 1)-го шага необходимо vv -л і к-(2п-к + \) . , т 2_u{n-i) + n + \ = — - + Л + 1, к = \,п. =о 2 элементов для хранения треугольной матрицы. В итоге для данного метода необходимо оперативной памяти почти в два раза меньше, чем для хранения исходной матрицы. Если размерность матрицы уравнений такова, что превышает допустимые нормы даже в преобразованном виде, то ее необходимо разбить на блоки, которые последовательно загружаются в память компьютера для соответствующих преобразований метода Гаусса [46].
Предложенный метод очень эффективно использовать для кластеров, так как архитектура таких компьютеров состоит из независимых блоков (узлов) со своей оперативной памятью и процессором. Пусть кластер состоит из п узлов и в оперативной памяти А го узла может храниться тк строк матрицы линейно-алгебраических уравнений (к = 0,п-\). На каждом этапе итерации основной узел (нулевой) будет последовательно загружать в оперативную память строки матрицы уравнений с последующей обработкой метода Гаусса. Если / тк, где к - номер кластера, і - номер строки, то обработанная строка передается кла стеру с номером (к +1), иначе - сохраняется в данном кластере. Соответственно, обратный ход метода Гаусса начинается с (п -1) -го кластера, посылая всем кластерам полученные решения необходимые для корректной работы алгоритма. В данном алгоритме предполагается, что матрицу уравнений можно загрузить в память узлов кластера полностью, в противном случае, как и для обычных компьютеров, необходимо использовать блочную технологию решения больших алгебраических задач [46]. Чтобы минимизировать передачу данных между узлами целесообразно разделить строки матрицы так, чтобы число строк в данном узле было не больше, чем в предыдущем (т0 т1 ... тпА).Если узлы кластера будут одинаковыми по мощности, то строки матрицы необходимо разделить на почти равные части для более-менее синхронной работы независимых процессов. 3.5. Выводы
