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

На правах рукописи

Новиков Александр Константинович

ПАРАЛЛЕЛЬНАЯ Ь-ВЕРСИЯ МКЭ В РЕШЕНИИ ДВУМЕРНЫХ ЗАДАЧ ТЕОРИИ УПРУГОСТИ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2004

Работа выполнена в Институте прикладной механики Уральского отделения РАН (г.Ижевск).

Научный руководитель доктор физико-математических наук,

профессор Альес Михаил Юрьевич Официальные оппоненты: доктор физико-математических наук,

профессор Тишкин Владимир Федорович кандидат физико-математических наук, Мартыненко Сергей Иванович

Ведущая организация Институт механики сплошных сред УрО РАН,

г. Пермь.

Защита диссертации состоится « сЮ »шк в /д. 00 на заседании диссертационного совета К 002.058.01 при Институте математического моделирования РАН по адресу: 125047, Москва, Миусская пл., 4а.

С диссертацией можно ознакомиться в библиотеке Института математического моделирования РАН.

Автореферат разослан « ¿7 » ^■¿^¿Рб^ТсР 2004г.

Ученый секретарь

диссертационного совета К 002.058.01, к.ф.-м.н.

Похилко В.И.

ÜS2/81С

Общая характеристика работы

Актуальность темы. В настоящее время развиваются конечно-элементные, конечно-разностные, конечно-объемные методы с уточнением сеточной аппроксимации. Используемые в этих методах расчетные сетки с шагом, зависящим от градиентов решения или от геометрии области, принято называть адаптивными. Адаптивные сетки широко применяются при математическом моделировании различных физических процессов. Построению и перестроению адаптивных сеток посвящены работы А.Ф. Сидорова и его учеников, работы Г.П. Прокопова, H.H. Янен-ко, В.Ф. Тишкина, С.А. Иваненко, В.Д. Лисейкина, A.M. Сорокина, В.А. Гаранжи, П.А. Войновича, В.Н. Аптукова, А.И. Садырина и многих других ученых, в том числе и зарубежных. В этих работах рассматривается адаптация сетки к решению и расчетной области, но применение параллельных алгоритмов для построения и перестроения .сетки только начинает развиваться.

При моделировании реальных физических процессов вычислительные затраты сеточных методов даже с адаптивными расчетными сетками остаются значительными. Сократить время вычислений за счет их параллельного выполнения позволило бы применение многопроцессорных ЭВМ. Разработки параллельных алгоритмов для решения задач математической физики ведутся в многих институтах Академии наук (ИММ РАН, ИАН РАН, ИПМ им. М.В. Келдыша РАН, ВЦ РАН, ИММ УрО РАН, ИМСС УрО РАН, ИВМ и МГ СО РАН). Это работы О.М. Бе-лоцерковского, Б.Н. Четверушкина, A.B. Забродина, Ю.А. Кузнецова и их учеников.

Сочетание адаптивного перестроения сетки и параллельных вычислений позволило бы совместить преимущества этих подходов. Поэтому стала актуальной задача разработки параллельного алгоритма метода конечных элементов с адаптивным перестроением сетки (параллельной h-версии МКЭ).

Целями данной работы являются:

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

2. Разработка алгоритмов параллельного перестроения треугольной конечно-элементной сетки.

3. Сравнение алгоритмов перестроения сетки.

4. Исследование критериев адаптации сетки.

5. Численное исследование эффективности алгоритма при решении

двумерных задач теории упругости.

Научная новизна.

1. Разработан новый алгоритм адаптивного МКЭ с перестроением сетки, который включает параллельные алгоритмы: формирования и решения сеточной СЛАУ, апостериорной оценки погрешности, перестроения сетки делением конечных элементов и балансировки вычислительной нагрузки. Исследована его эффективность и структура вычислительных затрат при моделировании напряженно-деформированного состояния в конструкциях с концентраторами напряжений.

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

3. Предложены новые параллельные алгоритмы решения систем сеточных уравнений на основе элементной схемы метода сопряженных градиентов (МСГ) с сокращением числа обменов на каждой итерации и совмещением обменов и вычислений.

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

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

Теоретическая и практическая ценность. Теоретическая ценность состоит в том, что были разработаны: параллельный алгоритм /г-версии МКЭ с апостериорной оценкой погрешности; алгоритмы параллельного построения и перестроения треугольной конечно-элементной сетки; параллельного решения сеточных СЛАУ на основе элементной схемы МСГ. Проведено сравнение эффективности алгоритмов перестроения сетки и влияния перестроения сетки на изменение величин углов в конечных элементах и шага сетки. Исследованы апостериорная оценка погрешности и ряд критериев адаптации.

Практической ценностью является то, что разработанное прикладное программное обеспечение (ППО) адаптивного МКЭ с уточнением по Н-оерсии может быть применено при решении плоских задач линейной теории упругости для различных конструкций, состоящих из неоднородных материалов, к конструкциям могут прикладываться как по-

верхностные, так и объемные силы. Отдельные части данного ППО (перестроение сетки, решение СЛАУ) могут быть применены при решении других задач математической физики с применением МКЭ. Программное обеспечение написано на языке программирования Си, с применением функций коммуникационной библиотеки MPI (Message Passing Interface), что обеспечиваем его переносимость на большинство многопроцессорных ЭВМ и вычислительных сетей.

Апробация работы. Результаты, представленные в работе, докладывались: на V Международном конгрессе по математическому моделированию в г. Дубна (2002г.); VIII Всероссийском съезде механиков в г. Пермь (2001г.); Международной конференции по вычислительной гидродинамике Parallel CFD в г. Москве (2003г.); 15-й Международной конференции по методам декомпозиции области в г. Берлине (2003г.); Всероссийских совещаниях по проблемам построения сеток в п. Абрау-Дюрсо (1996г.), в г. Пущиио (2000г.); Всероссийской конференции "Высокопроизводительные вычисления и их приложения", г. Черноголовка (2000г.); Всероссийской конференции "Актуальные проблемы прикладной математики и механики"в г. Екатеринбург (2003г.); на I, II конференциях "Применение математического моделирования для решения задач в науке и технике"в г. Ижевске (1996,1998гг.); Всероссийских молодежных школах-конференциях (по математическому моделированию, геометрии и алгебре, 1997г; "Итерационные методы решения линейных и нелинейных сеточных задач", 1999г; "Численные методы решения линейных и нелинейных краевых задач", 2001, 2003гг.) в г. Казани.

Публикации. Основные результаты опубликованы в двадцати четырех работах.

Благодарности. Диссертационная работа выполнена при финансовой поддержке РФФИ (гранты №№02-07-90265,03-07-90002, MAC №0307-06119) и УрО РАН (грант для научных проектов молодых ученых и аспирантов).

Структура и объем работы. Работа состоит из введения, четырех глав, восемнадцати параграфов (нумерация параграфов по главам), заключения, списка литературы и содержит 55 рисунков, 5 таблиц. Объем работы 117 страниц. Библиографический список включает 103 наименования.

Содержание работы

Во введении обоснована актуальность темы, сформулированы цели работы, изложено краткое содержание работы по главам.

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

Остановимся на примененной в работе апостериорной оценке погрешности конечно-элементного решения. Оценка была основана на построении сопряженного (или согласованного с перемещениями) поля напряжений и использовании его в качестве точного. Для оценки величины погрешности использовалась энергетическая норма решения (перемещений), которая для конечного элемента г вычислялась таким образом:

\\иг - = [[ (СП- - (1)

где <7{ - точные значения напряжений; сг'1 - конечно-элементные значения напряжений, постоянные по элементу; И - матрица упругих постоянных; (¿г - площадь КЭ.

Энергетическая норма абсолютной погрешности по всей расчетной области имела вид:

и

\\и-ч>Ч\ = 152\\щ-иЧГ}1/2, (2)

¿=1

здесь М - число элементов сетки; ||щ — и'-\\ - энергетическая норма погрешности в конечном элементе г.

Относительная погрешность определялась как отношение норм аб-

солютнои погрешности и точного решения:

77 =

и — и"

100%,

здесь ||и|| = /и. о-^В~1а'£с1сиг]1/2 . Вычисление сопряженных на-

пряжений требует реш'ения СЛАУ для каждой компоненты напряжения и преобладает в вычислительных затратах оценки погрешности (3).

Исходя из равнораспределения абсолютной погрешности по всей расчетной области, построен критерий выбора элементов для перестроения:

||Иг - и1.

/III2

>

■и — и'

Ь||2

(4)

1" " м

Достоверность оценок погрешности проверялась при численном решении задачи Ламэ. На рис.1 приведены зависимости абсолютной погрешности (2) от числа степеней свободы N для сопряженной аппроксимации и аналитического решения. На этой же задаче проведено срав-

11»-»А11

2.0Е-03 1.5Е-03 1.0Е-03 5.0Е-04 0.0Е+00

| 1

А— .......Сопряженная аппроксимация —Аналитическое решение

ч\

45

30

1 ^

-\- -Равнораспределение погрешности .......Интенсивность напряжений

3 4

ДО

Рис. 1. Абсолютная погрешность

2 3 4 5

до

Рис. 2. Критерии адаптации

нение критериев выбора перестраиваемых КЭ. На рис.2 приведены графики т]{1дН) для выбора перестраиваемых КЭ исходя из критерия (4) и интенсивности напряжений. При перестроении сетки в области максимальной интенсивности напряжений г}(1дИ) выходит на асимптоту т}(1дМ) = 7% (рис.2). Это связано с тем, что границы расчетной области не входят в область максимальной интенсивности напряжений. Уточнение решения при т](1дН) < 7% происходило за счет уточнения внешней границы расчетной области. В результате сравнения критериев для адаптивного перестроения сетки был выбран критерий (4).

Перестроение сетки в к-версии МКЭ состояло из двух шагов: уточняющего перестроения (КЭ делились для уточнения аппроксимации в данной подобласти) и согласующего перестроения (КЭ делились для обеспечения непрерывности аппроксимирующих функций между конечными элементами). На первом шаге этого алгоритма создавалось множество несогласованных КЭ. Число элементов в этом множестве изменялось при перестроении сетки и процесс перестроения прекращался, когда множество становилось пустым. В работе отмечено, что размер области, в которой происходило перестроение КЭ зависел не только от выбранного множества перестраиваемых КЭ, но и от геометрии треугольников (внутренние углы, площади). Основным методом перестроения сетки в работе являлась к-версия, но была рассмотрена и г-версия МКЭ (изменение координат узлов сетки) и их комбинации кг и г/г. Алгоритм г-версии был построен на основе равнораспределения весовой функции. При этом вес конечного элемента г ставился в зависимость от ||гц—и геометрических характеристик (площади и длины ребра). Проведенное сравнение уточнение с применением к- и г-версий МКЭ (на задаче о трещине) показало, что при равном числе узлов погрешность полученная с применением к-версии в 1.5 раза меньше чем при использовании г-версии.

Ьг-вврсип

гЬ-вврсия

Рис. 3. Сетки, перестроенные по к,г, кг,г к-версиям МКЭ

Рис. 4. Зависимость погрешности от шага сетки

При расчете на заданную точность h-версия требует почти в 3 раза меньше конечных элементов. На рис.3 показаны сетки, полученные при решении задачи о растяжении пластины с трещиной, с применением г-версии (1106 узлов, 2081 КЭ,77 = 13.29%), h-eepcuu (380 узлов, 708 КЭ,т? = 13.33%), hr-eepcuu (383 узла,714 КЭ,77 = 11.89%), гк-версии (308 узлов, 565 КЭ,т? = 13.59%). В r-версии шаг сетки h ограничен геометрией треугольного конечного элемента, поэтому ||u — г^Ц имеет асимптоту (рис.4). Существенное уменьшение шага сетки и погрешности в r-версии происходило на первых 12 шагах адаптивного МКЭ, что соответствовало одному или двум шагам в h-eepcuu. В качестве шага сетки принят радиус вписанной в КЭ окружности.

Во второй главе предложен параллельный алгоритм метода конечных элементов с адаптивным перестроением сетки:

1. Выполняем разделение и распределение сетки Т,, i = 0.

2. Методом конечных элементов решаем задачу на сетке .

3. Оцениваем погрешность решения т] по (3). Если погрешность не превышает допустимую, то вычисления прекращаем.

4. Исходя из критерия (4), выбираем область Т* € Ti (или несколько областей) уточнения решения.

5. Область Т* перестраиваем. Получаем сетку Tf+i.

6. Оцениваем отклонение вычислительной нагрузки от равнораспреде-ленной. Если отклонение превышает допустимое выполняем балансировку. В другом случае полагаем i = i +1 и переходим на шаг 2.

На шагах 1 и 6 выполняется соответственно статическая (разделение исходной сетки) и динамическая (перераспределение ранее распределенной и перестроенной сетки) балансировка вычислительной нагрузки. При балансировке сетка разделялась на число подобластей равное числу процессоров Р вычислительной системы. Подобласти пересекались только по узлам и ребрам конечных элементов. Как отмечено в работе статическая балансировка может быть заменена параллельным построением сетки. Применение в работе элементной схемы МСГ позволило свести задачу равномерной вычислительной нагрузки на процессоры вычислительной системы к распределению конечных элементов. Процесс балансировки состоял из двух шагов: вычисления разделения дуального графа сетки для КЭ и перераспределения конечных элементов по процессорам. При разделении сетки по конечным элементам некоторые узлы сетки принадлежали нескольким процессорам (для треугольных КЭ число процессоров зависит от величин углов в треугольниках, вершиной, которых является узел). В работе такие узлы названы общими, а узлы принадлежащие только одному процессору - внутренними.

Аналогично для ребер.

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

Другая модификация алгоритма решения СЛАУ состояла в вычислении скалярного произведения для вектора невязки через вектор невязки с предыдущей итерации МСГ, чем был исключен один из двух обменов "все - всем"на каждой итерации метода сопряженных градиентов. Исключение обмена потребовало введения дополнительных скалярных произведений. Тем не менее применение модификаций базового алгоритма МСГ уменьшило время вычислений на 15-20 %.

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

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

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

В завершении главы приведены: структура вычислительных затрат (рис.5), эффективность и ускорение (рис.6) алгоритма параллельной к-версии МКЭ. Из рис.5 видно, что наибольшие затраты приходятся на

Поростроонно сотки

3 5 7 9 11 13 Число процессоров

Рис. 5. Структура вычислительных затрат

Рис. 6. Эффективность алгоритма и ускорение

решение СЛАУ (78%) и оценку погрешности ( 19.65%). Следует отметить хорошую эффективность ( 88% ) и масштабируемость алгоритма (рис.6), близость фактического и теоретического ускорения.

Третья глава посвящена программной реализации предложенных алгоритмов. В главе приведены принятые в работе модели параллель-пых вычислений (модель обмена сообщениями), модель программирования (одна программа много данных) и показаны характеристики ЭВМ МКМД-архитектуры, на которых выполнялись вычисления (Paraclete, МВС-1000/16, Parsytec СС-8 и PowerXplorer), также показана структуры данных, примененная в работе для хранения сетки, матриц, векторов и т.д.; представлена организация межпроцессорных коммуникаций на основе библиотеки MPI (Message Passing Interface) и краткая характеристика интегрированного программного обеспечения.

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

координате. Смежные КЭ хранились, как смежные по ребру.

Программная реализация коммуникаций имела свои особенности. Некоторые обмены происходили внутри группы процессов для смежных подобластей. Для осуществления таких обменов были созданы графы связи подобластей сетки: по ребрам (при перестроении и перераспределении сетки), по узлам (при решении СЛАУ). Графы связи перестраивались после балансировки вычислительной нагрузки. Перераспределение сетки потребовало обменов неоднородными данными (функции MPI пересылки структур), а совмещение обменов и вычислений при при решении СЛАУ - асинхронных коммуникаций (функции MPI пересылки без блокировки). Каждая из особенностей иллюстрирована в работе фрагментом программы.

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

Деформирование цилиндра со сложной внутренней поверхностью. На внутреннюю поверхность цилиндра действует давление. Сложная геометрия поверхности вызывает концентрацию напряжений, которая определяет локальность перестроение сетки. После перестроения получается неравномерно распределенная сетка. В результате, на последнем шаге уточнения разность максимальной (31175 КЭ) и минимальной вычислительной нагрузки (7759 КЭ) превышала равномерную нагрузку (17011 КЭ на процессор) в 1.38 раза, что уменьшило эффективность всего алгоритма. Применение динамической балансировки вычислительной нагрузки привело к тому, что время счета до погрешности г/ = 0.81% (12 шагов перестроения, 128337 узлов, 255168 КЭ) уменьшилось в 1.65 раза и составило 379.15 секунд вместо 627.29 - без балансировки. Время счета приведено при Р = 15 для кластера Paraclete,

Рис. 7. Исходная сетка (307 узлов, 527 КЭ, г\ = 27.89%)

Рис. 8. Перестроенная сетка (3754 узлов, 72G5 КЭ, т] = 4.95%)

созданного в Институте прикладной механики УрО РАН.

На рис.7,8 показано распределение подобластей исходной и перестроенной (5 перестроений сетки с балансировкой вычислительной нагрузки) сетки по процессорам вычислительной системы. При перераспределении некоторые подобласти сетки разрывались (рис.8 подобласти 9 и 13). Разрыв подобластей не отражался на устойчивости-и эффективности алгоритма.

Плотина на неоднородном основании. Представлены несколько вариантов задачи: действие только гидростатического давления или силы тяжести, их совместное действие и несколько вариантов материалов среды. Рассмотрим вариант, когда действовали сила тяжести и гидро-

статическое давление воды. Материалы среды: бетонная плотина (I), бетонный фундамент (II), скальное основание (III) и нескальный грунт (IV) (рис.9). Модули Юнга для плотины и грунта отличались в 300 раз. Как видно на рис.10 перестроение сетки наиболее интенсивно происходило по линиям раздела материалов. Максимальные растягивающие напряжения возникали у основания плотины, а максимальное сжатие наблюдалось в точке пересечения фундамента, скального основания и грунта.

Выполнено сравнение адаптивного (по критерию (4)) и равномерного перестроения сетки (для перестроения выбирались все КЭ). Сравнение показало, что адаптивное перестроение (при г) = 5.27% требуется 4745 узлов, 9289 КЭ ) в h-eepcuu МКЭ существенно эффективнее равномерного (при ?? = 5.3% - 322440 узлов, 642295 КЭ). Данная погрешность достигнута после 9 шагов перестроения сетки. Время счета h-eepcuu МКЭ составило соответственно 15.9 секунд при адаптивном и 1724.17 - при равномерном перестроении (в 108 раз больше). Даже при адаптивном перестроении сетки решение данной задачи потребова-

Рис. 9. Исходная сетка (348 узлов, 599 КЭ, г] = 14.58%)

Рис. 10. Перестроенная сетка (34525 узлов, 68540 КЭ, rj = 3.07% )

ло значительных вычислительных затрат для достижения погрешности менее 1% (513058 узлов, 1024098 КЭ при т) = 0.89% и 23 шагах перестроения).

Растяжение пластины из композиционного материала. Пластина растягивалась в вертикальном направлении под действием равномерно распределенной нагрузки. Реальные включения (рис.11) были заменены включениями эллиптической формы. Модельная область содержала 97

Рис. 11. Микрошлиф материала Рис. 12. Исходная сетка

(3177 узлов, 6197 КЭ, г] = 9.85%)

включений (рис.12). Такой подход позволил смоделировать напряженно-деформированное состояние в пластине, с учетом размеров и ориентации включений. Построение такой модели и сетки стало возможным благодаря CAD/CAE системе FEStudio, созданной в ИПМ УрО РАН. На рис.13 приведена сетка после 5 шагов перестроения. Перестроение

fcf/i\i.'>. I^t1

ЩШ5

ша * " $

■'•О1"

. 1 " , ,

-031651 ■ 039103 " 074762 0.2131В 0.IWI ОНИ! 010310 0.015336 0010373

■стчп

Рис. 13. Перестроенная сетка (36950 узлои, 73598 КЭ, т? = 3.66%)

Рис. 14. Распределение ||иг — и';'||2 на перестроенной сетке

сетки наиболее интенсивно происходило около включений (рис.13), что хорошо согласовалось с распределением погрешности (рис.14). Максимальные напряжения возникали у включений вытянутых вертикально

или расположенных под небольшим углом к вертикали. Минимальные напряжения так же наблюдались в окрестности включений. Как видно из рис.15 уточнение решения сказывалось не только на максимальном и минимальном значении напряжений. После 13 шагов перестроения

Ал"тыт

%'з' чй' -к-'щ^Ъ'нШМЛ

. '¿.л'г. '4яЛшчг-я'-!

(ИИ 7

1656 г

] И91; 113251 ) 1158.6 9э:оа ¡ 83555 } С59 03 \ 492 3 315»

шмшшшт

'; а:'........

'-'V '"у*

г® 'Л.

'и-.** г.

- ¡л .'.г

II»»«

1647 9 14713 1594 7 11181 94149 784 9 58831 4117} 33514

а) б)

Рис. 15. Напряжения стаг на исходной (а) и перестроенной сетке (б).

сетки погрешность г/ = 0.95% (сетка из 808587 узлов и 1615843 КЭ).

Заключение содержит основные результаты и выводы но работе.

Заключение

1. Разработан алгоритм решения задач теории упругости на основе Н-версии МКЭ и параллельных вычислений, включающий: параллельную элементную схему метода сопряженных градиентов; апостериорную оценку погрешности и критерий адаптации; параллельное адаптивное перестроение треугольной конечно-элементных сетки; балансировку вычислительной нагрузки, в том числе для гетерогенных вычислительных систем.

2. Разработаны алгоритмы параллельного перестроения сетки, которые реализуют несколько способов деления треугольных КЭ и требуют менее 0.1% в вычислительных затратах алгоритма Н-версии МКЭ.

3. Созданы и численно исследованы параллельные алгоритмы метода сопряженных градиентов с сокращенной коммуникационной нагрузкой для СЛАУ, с расщепляющейся матрицей коэффициентов, которые позволили сократить время вычислений на 15 - 20% .

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

5. Проведены численные исследования напряженно-деформированного состояния: цилиндрической конструкции с внутренней границей., сложной формы нагруженной давлением; плотины на неоднородном основании под действием сил тяжести н гидростатического давления воды; композиционного материала с реальным распределением включений, имеющих разный размер и ориентацию в пространстве. Выполненные исследования показали, что предложенные оценка погрешности и критерий перестроения хорошо отражают особенности решений, вызванные: нерегулярностью границ деформируемого тела; локальным приложением нагрузки и неоднородностью материала. Исследована эффективность алгоритма и вклады во временные затраты его отдельных шагов при проведении расчетов на нескольких многопроцессорных вы-' числительных системах. Результаты исследований показали, что алгоритм, достаточно эффективен (88%), а наибольшие затраты времени счета приходятся на решение СЛАУ (до 78%) и вычисление оценки погрешности (20 - 30%).

Численные исследования показали, что временные затраты на решение по h-версии MIO существенно меньше, чем при решении на равномерной перестроенной сетке (до двух порядков). Так же следует отметить, что для рассмотренных задач с неоднородностью материала погрешность (3) в интервале 1 — 5% достигалась на сетках с числом конечных элементов 105 -106 .

Публикации по теме работы

1. Alies M.Yu., Kopyssov S.P., Novilcov A.K., Ustyuzhanin S.L. Estimation of influence of uouliiiear behaviour of SRJP at complex loadiug // Int. Coiif. ICOC93, St-Peterbiu-g 1993, - Izhevsk, 1996. - P. 280-294.

2. Альес М.Ю., Копысов С.П., Новиков A.K. Построение и отображение плоских конечно-элементных сеток на параллельной вычислительной системе //В сб.: Применение мат. моделирования для решения задач в науке и технике. Ижевск, 1996. - С. 118-126.

3. Альес М.Ю., Копысов С.П., Варнавский А.И., Новиков А.К. Построение диаграмм Вороного и триангуляции Делоне на плоскости и в пространстве. - Ижевск, 1996. - 39с. (Препринт УрО РАН, Ин-т. прикл. механики).

4. Альес М. 10., Копысов С.П., Новиков А.К., Устюжанин С.Л. Адаптивный конечно-элементный метод при решении задач деформирования зарядов // В сб. "Современные проблемы внутренней баллистики РДТТ". - Ижевск, 1996. - С. 218-227.

5. Новиков А.К., Копысов С.П., Альес М.Ю. Параллельное поэлементное формирование и решение конечно-элементных уравнений // Сб. "Современные проблемы мат. моделирования", Ростов-на-Дону, РГУ, 1997. - С. 107-109.

6. Альес М.Ю., Копысов С.П., Новиков А.К. Построение и адаптация конечно-элементной сетки при решении эллиптической задачи второго порядка // Мат. моделирование. - 1997. - Т.9. - №2. - С. 43-45.

7. Альес М.Ю., Копысов С.П., Новиков А.К. Параллельное построение плоских конечно-элементных сеток // Мат. моделирование. - 1998. -Т.10. №5.-С. 71-76.

8. Новиков А.К., Копысов С.П. Адаптивное перестроение сетки при решении задачи математического моделирования на параллельной ЭВМ // Материалы мол одеж. науч. школы-конф. по мат. моделированию, геометрии и алгебре (Казань, 4-11 дек. 1997 г.) - Казань, 1998. - С. 122128.

9. Альес М.Ю., Копысов С.П., Новиков А.К. Алгоритм и реализация параллельного перестроения сетки // Сб. трудов VIII Всерос. школы-семинара "Современные проблемы мат. моделирования", РГУ, Ростов-на-Дону, 1999. - С. 3-9.

10. Копысов С.П., Альес М. Ю., Новиков А.К., Устюжанин С. JT. Методы декомпозиции для решения задач деформирования с динамическим перестроением сеточных моделей // Тр. Всерос. науч. конф. "Высокопроизводительные вычисления и их приложения"30.10.-2.11.2000. г. Черноголовка, 2000. - С. 119-122.

11. Альес М.Ю., Копысов С.П., Новиков А.К. Параллельные схемы метода сопряженных градиентов // Тр. Мат. центра им. Н.И. Лобачевского. Т. 13 Казан, мат, о-во. Численные методы решения линейных и нелинейных краевых задач. Материалы Всерос. молодеж. науч. школы-конф. 19-23.11.2001, Казань. Изд. "ДАС", Казань, 2001. -С.126-132.

12. Альес М.Ю., Копысов С.П., Новиков А.К., Устюжанин С.Л. Параллельное уточнение в методе конечных элементов при решении задач деформирования // Аннот. докл. Восьмого Всерос. съезда по теорет. и прикл. механике 23-29 авг. 2001г., Пермь, ИМСС УрО РАН, Пермь, 2001. - С. 40.

13. Kopyssov S., Novikov A. Parallel Adaptive Mesh Refinement with Load Balancing for Finite Element Method // V. Malyshkin (Eds.): Parallel Computing Technologies 6th Int. Conf., PaCT 2001, Novosibirsk, Sep. 3-7, 2001, Proceedings. 2001. - P. 266-276.

14. Копысов С.П., Новиков А.К, Оценка погрешности и h-версия МКЭ для решения задач упругости // Сб. науч. тр. "Проблемы меха-

ники и материаловедения", ИПМ УрО РАН, Ижевск, 2001, Изд. ИПМ УрО РАН, Ижевск, 2001. - С. 106-114.

15. Копысов С.П., Новиков А.К. Параллельные алгоритмы адаптивного перестроения и разделения неструктурированных сеток // Мат. моделирование. - 2002. - Т.14. - № 9. - С. 91-96.

16. Kopyssov S.P, Novikov А.К. Parallel mesh refinement and load balancing in mathematical modeling of elasticity problems // V International Congress of Mathematical Modeling, September 30 - October 6, 2002, Dubna, Moscow Region. Book Absrtact. 2002. - P. 73.

17. Kopyssov S.P., Novikov A.K. Parallel element-by-element conjugate gradients method with decreased communications costs // Int. Summer School "Iterative Methods and Matrix Computations", Editor Gene H. Golub, Lev A. Krukier, 2-9 June 2002, Rostov-on-Don, 2002. - P. 450-454.

18. Копысов С.П., Новиков A.K., Михайлова Г.В. r-версия метода конечных элементов в задачах теории упругости // Материалы Меж-дунар. науч-техн. конф., посвящ. 50-летию ИжГТУ (19-22 фев. 2002г.) - Ч.З Моделирование техн. и социотехн. систем, Ижевск, Изд. ИжГТУ,

2002. - С. 97-107.

19. Копысов С.П., Новиков А.К. Сравнение г- и h-версий МКЭ на примере задач теории упругости // Актуальные проблемы прикл. математики и механики, 3-7 фев. 2003 г., Екатеринбург, 2003. - С. 44-45.

20. Копысов С.П., Новиков А.К. Анализ способов перестроения треугольных конечно-элементных сеток // Тр. Мат. центра им. Н.И. Лобачевского. Т.20 Казан, мат. о-во. Численные методы решения линейных и нелинейных краевых задач. Материалы второй Всерос. молодеж. науч. школы-конф. 27.06-1.07.2003, Казань. Изд. Казан, мат. о-ва, Казань,

2003. -С. 170-180.

21. Kopyssov S.P., Krasnopyorov I.V., Novikov А.К., Rychkov V.N. Object-oriented Software for Domain Decomposition Methods with Local Adaptive Refinement // Parallel Computational Fluid Dynamics, Elsevier,

2004. - P. 425-432.

22. Копысов С.П., Новиков А.К. Параллельное адаптивное перестроение треугольной конечно-элементной сетки // Прикл. геометрия, построение сеток и высокопроизводительные вычисления.

Под ред. Ю.Г. Евтушенко, М.К. Керимов, В.А. Гаранжа. - Т.1 - Москва, ВЦ РАН, 2004. - С. 167-178.

23. Kopyssov S.P., Krasnopyorov I.V., Novikov А.К., Rychkov V.N. Object-oriented Software for Domain Decomposition Methods with Local Adaptive Refinement // Parallel Computational Fluid Dynamics: Advanced numerical methods, software and applications / Chetverushkin, B.N. et. al.

(Eds.) - Elsevier, North-Holland, Amsterdam, 2004. - P.425-432.

24. Kopyssov S.P., Krasnopyorov I.V., Novikov À.K., Rychkov V.N. Parallel Distributed Object-oriented Framework for Domain Decomposition // Lecture Notes in Computational Science and Engineering: Domain Decomposition Methods in Science and Engineering / Kornhuber, R. et. al. (Eds.) - Springer, Berlin, 2004. - Vol.40. - P.605-614.

Издательство Института прикладной механики УрО РАН. 426067, г.Ижевск, ул. Т.Барамзиной, 34. Лицензия на издательскую деятельность ИД №04874 от 24.05.2001.

Подписано в печать Тираж

Заказ K'-Jvf . Формат 60 х 84/16 1/16. Бумага Xerox. Гарнитура Times. Печать офсетная. Усл. печ. л. 1,2.

РНБ Русский фонд

2007-4

Список обозначений

Введение

I. Метод конечных элементов с адаптивным перестроением сетки в решении задачи теории упругости 10 ,1.1. Математическая постановка задачи теории упругости.

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

1.2.1. Триангуляция расчетной области.

1.2.2. Формирование системы линейных алгебраических уравнений МКЭ.

1.2.3. Особенности задания граничных условий первого рода

1.3. Метод решения конечно-элементной СЛАУ.

1.3.1. Элементная схема метода сопряженных градиентов

1.3.2. Начальное приближение в методе сопряженных градиентов.

1.4. Оценки погрешности и выбор критерия адаптации.

1.4.1. Априорные оценки погрешности решения.

1.4.2. Апостериорные оценки погрешности

1.4.3. Критерии адаптивного перестроения сетки.

1.5. Перестроение конечно-элементной сетки.

1.5.1. h-версия МКЭ

1.5.2. Изменение шага сетки и углов в треугольниках

1.5.3. r-версия МКЭ.

1.5.4. Сравнение методов перестроения сетки.

II. Параллельный МКЭ с перестраиваемой сеткой

2.1. Статическая балансировка

2.2. Параллельное решение СЛАУ.

2.2.1. Сокращение числа обменов.

2.2.2. Схема с совмещением вычислений и обменов

2.2.3. Сравнение параллельных схем МСГ.

2.3. Параллельное адаптивное перестроение сетки

2.3.1. Нумерация сеточных объектов.

2.3.2. Алгоритм параллельного перестроения сетки

2.4. Динамическая балансировка вычислительной нагрузки.

2.5. Структура вычислительных затрат алгоритма при решении задач теории упругости

III. Программное обеспечение параллельной h-версии МКЭ

3.1. Архитектура вычислительной системы и модель параллельных вычислений.

3.2. Структура прикладного программного обеспечения.

3.3. Структуры данных для хранения сетки, матриц и векторов 82 '

3.4. Организация и программная реализация коммуникаций

3.4.1. Параллельное перестроение сетки

3.4.2. Перераспределение сетки.

3.4.3. Решение линейных алгебраических уравнений

3.5. Интегрированное программное обеспечение.

IV. Результаты численных исследований двумерных задач теории упругости на многопроцессорной ЭВМ '

4.1. Деформирование цилиндра со сложной внутренней поверхностью.

4.2. Плотина на неоднородном основании.

4.3. Растяжение пластины из композиционного материала.

В настоящее время активно развиваются конечно-разностные, конечно-элементные, конечно-объемные методы с уточнением сеточной аппроксимации. Используемые в этих методах расчетные сетки с шагом, зависящим от градиентов решения или от геометрии области, принято называть адаптивными. Адаптивные сетки широко применяются при математическом моделировании различных физических процессов [1-10]. Построению и перестроению адаптивных сеток посвящены работы А.Ф. Сидорова и его учеников, работы Г.П. Прокопова, Н.Н. Яненко, В.Ф. Тишкина, С.А. Иваненко, В.Д. Лисейкина, A.M. Сорокина, В.А. Гаранжи, П.А. Войновича, В.Н. Аптукова, А.И. Садырина и многих других ученых, в том числе и зарубежных.

Один из методов, в котором применяются адаптивные сетки, - это метод конечных элементов (МКЭ). Решение полученное в МКЭ является приближенным к точному [11]. Погрешность решения можно уменьшить с помощью процедур адаптивного перестроения, которые приводят к уменьшению шага сетки. Такими процедурами являются: деление конечных элементов на конечные элементы меньшего размера (h-версия), изменение координат узлов сетки (г-версия) и их комбинации hr-eepcuu МКЭ.

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

В задачах теории упругости, являющихся основой расчетов конструкций на прочность и жесткость, особенности решения вызваны:

1) неоднородностью конструкции (наличие отверстий,углов);

2) неоднородностью материала (включения других материалов, пористость, наличие "раковин");

3) неоднородностью нагрузки (сосредоточенные или локально распределенные нагрузки).

При моделировании реальных физических процессов вычислительные затраты сеточных методов даже с адаптивными расчетными сетками остаются значительными. Сократить время вычислений за счет их параллельного выполнения позволило бы применение многопроцессорных ЭВМ. Разработки параллельных алгоритмов для решения задач математической физики и линейной алгебры ведутся в многих институтах Академии наук (МММ РАН, ИАП РАН, ИПМ им. М.В. Келдыша РАН, ВЦ РАН, ИММ УрО РАН, ИМСС УрО РАН, ИВМ и МГ СО РАН). Это работы О.М. Белоцерковского, Б.Н. Четверушкина, А.В. Забродина, Ю.А. Кузнецова и их учеников [15-19].

Сочетание адаптивного перестроения сетки и параллельных вычислений позволило бы совместить преимущества этих подходов. Поэтому стала актуальной задачей разработка параллельного алгоритма метода конечных элементов с адаптивным перестроением сетки (параллельной h-eepcuu МКЭ).

Целями данной работы являются:

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

2. Разработка алгоритмов параллельного перестроения треугольной конечно-элементной сетки.

3. Сравнение алгоритмов перестроения сетки.

4. Исследование критериев адаптации сетки.

5. Численное исследование эффективности алгоритма при решении двумерных задач теории упругости.

Работа состоит из введения, четырех глав, восемнадцати параграфов (нумерация параграфов по главам), заключения, списка литературы и содержит 55 рисунков, 5 таблиц. Объем работы 117 страниц. Библиографический список включает 103 наименования.

Во введении обоснована актуальность темы, сформулированы цели работы, изложено краткое содержание работы по главам.

Первая глава содержит: постановку задачи теории упругости в перемещениях, конечно-элементную аппроксимацию уравнений теории упругости, алгоритм МКЭ с адаптивным перестроением сетки. Обосновывается выбор метода решения систем линейных алгебраических уравнений (элементной схемы метода сопряженных градиентов). Приводятся существующие априорные оценки погрешности МКЭ. Вводится апостериорная оценка погрешности и обосновывается выбор критерия перестроения сетки. На примере, имеющем аналитическое решение, показывается достоверность оценки погрешности. Приводится анализ способов перестроения неструктурированных сеток. Завершает главу сравнение способов перестроения сетки.

Во второй главе предлагается параллельный алгоритм метода конечных элементов с адаптивным перестроением сетки, включающий: параллельные алгоритмы метода сопряженных градиентов (МСГ) и перестроения сетки, а также балансировку вычислительной нагрузки. Вводятся параллельные алгоритмы МСГ. Обсуждаются особенности параллельного построения и перестроения расчетной сетки. Предлагаются алгоритмы параллельного построения и перестроения сетки. Обосновывается необходимость балансировки вычислительной нагрузки в параллельной реализации МКЭ с адаптивным перестроением сетки. В завершении главы приводится структура вычислительных затрат параллельной h-eepcuu МКЭ и эффективность распараллеливания.

Третья глава посвящена программной реализации алгоритмов. В этой главе показывается модель параллельных вычислений, примененная в работе, структура данных для представления расчетной сетки, конечно-элементных матриц и векторов; обсуждается организация межпроцессорных коммуникаций на основе библиотеки MPI (Message Passing Interface), обсуждение иллюстрируется фрагментами программ, приводится использованное программное обеспечение и характеристики вычислительной техники, на которой производились вычисления.

В четвертой главе параллельная h-версия МКЭ применяется при моделировании напряженно-деформированного состояния конструкций с концентраторами напряжений различной природы; приводятся результаты моделирования (изоповерхности напряжений, перемещений, деформированные конструкции).

Заключение содержит основные результаты и выводы по работе.

Результаты, представленные в работе, докладывались: на V Международном конгрессе по математическому моделированию в г. Дубна (2002г.); VIII Всероссийском съезде механиков в г. Пермь (2001г.); Международной конференции по вычислительной гидродинамике Parallel CFD в г. Москве (2003г.); 15-й Международной конференции по методам декомпозиции области в г. Берлине (2003г.); Всероссийских совещаниях по проблемам построения сеток в п. Абрау-Дюрсо (1996г.), в г. Пущино (2000г.); Всероссийской конференции "Высокопроизводительные вычисления и их приложения", г. Черноголовка (2000г.); Всероссийской конференции "Актуальные проблемы прикладной математики и механики "в г. Екатеринбург (2003г.); на I, II конференциях "Применение математического моделирования для решения задач в науке и технике"в г. Ижевске (1996, 1998гг.); Всероссийских молодежных школах-конференциях (по математическому моделированию, геометрии и алгебре, 1995г; "Итерационные методы решения линейных и нелинейных сеточных задач", 1999г; "Численные методы решения линейнрх и нелинейных краевых задач", 2001, 2003гг.) в г. Казани.

Основные результаты опубликованы в двадцати четырех работах.

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

Заключение

1. Разработан алгоритм решения задач теории упругости на основе h-eepcuu МКЭ и параллельных вычислений, включающий: параллельную элементную схему метода сопряженных градиентов; апостериорную оценку погрешности и критерий адаптации; параллельное адаптивное перестроение треугольной конечно-элементных сетки; балансировку вычислительной нагрузки, в том числе для гетерогенных вычислительных систем.

2. Разработаны алгоритмы параллельного перестроения сетки, которые реализуют несколько способов деления треугольных КЭ и требуют менее 0.1% в вычислительных затратах алгоритма h-eepcuu МКЭ.

• 3. Созданы и численно исследованы параллельные алгоритмы метода сопряженных градиентов с сокращенной коммуникационной нагрузкой для СЛАУ, с расщепляющейся матрицей коэффициентов, которые позволили сократить время вычислений на 15 — 20%.

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

5. Проведены численные исследования напряженно-деформированного состояния: цилиндрической конструкции с внутренней границей сложной формы нагруженной давлением; плотины на неоднородном основании под действием сил тяжести и гидростатического давления воды; композиционного материала с реальным распределением включений, имеющих разный размер и ориентацию в пространстве. Выполненные исследования показали, что предложенные оценка погрешности и критерий перестроения хорошо отражают особенности решений, вызванные: нерегулярностью границ деформируемого тела; локальным приложением нагрузки и неоднородностью материала. Исследована эффективность алгоритма и вклады во временные затраты его отдельных шагов при проведении расчетов на нескольких многопроцессорных вычислительных системах. Результаты исследований показали, что алгоритм достаточно эффективен (88%), а наибольшие затраты времени счета приходятся на решение СЛАУ (до. 78%) и вычисление оценки погрешности (20 — 30%).

Численные исследования показали, что временные затраты на решение по h-версии МКЭ существенно меньше, чем при решении на равномерной перестроенной сетке (до двух порядков). Так же следует отметить, что для рассмотренных задач с неоднородностью материала погрешность (1.38) в интервале 1 — 5% достигалась на сетках с числом конечных элементов 105-10G.

1. Serezhnikova T.I., Sidorov A.F. and Ushakova O.V. On one method of construction of optimal curvilinear grids and its applications // Sov. J. Numer. Anal, and Math. Modelling. 1989. - V. 4. - №. - P. 137-155.

2. Годунов С.К., Прокопов Г.П. О расчетах конформных отображений и построения разностных сеток // Журн. вычисл. математики и ма-тем. физики. 1967. - Т. 7. - №5. - С. 1031-1059.

3. Лисейкин В.Д. Обзор методов построения структурных адаптивных сеток // Журн. вычисл. математики и матем. физики. 1996. - Т. 36. - т. - С. 3-41.

4. Андрианов А.Н., Жохова А.В., Четверушкин Б.Н. Использование параллельных алгоритмов для расчетов газодинамических течений на нерегулярных сетках // В сб. Прикладная математика и информатика. М.: Изд. факультета ВМиК МГУ. 2000. - N4.

5. Похилко В.И., Тишкин В.Ф. Однородный алгоритм расчета разрывных решений на адаптивных сетках // Матем. моделирование. 1994. -Т. 6.-Ml. - С. 25-40.

6. Емельянов К.В. Применение оптимальных разностных сеток к решению задач с сингулярным возмущением // Журн. вычисл. математики и матем. физики. 1994. - Т. 34. - №6. - С. 936-943.

7. Дегтерев Л.М., Дроздов В.В. Адаптирующиеся к решению сетки в эллиптических задачах на плоскости // Дифференц. уравнения. -1984. Т. 20. - №7. - С. 1194-1203.

8. Аптуков В.Н., Фонарев А.В. Расчет упругопластических течений на нерегулярных треугольных сетках с перестройкой // Прикл. матем. и техн. физ. 1990. - Т. 6. - С. 109-115.

9. Садырин А.И. Применение треугольных сеток к решению динамических упругопластических задач // Всес. межвуз. сб. Прикл. пр'обл.прочн. и пластичности. Статика и динамика деформируемых систем.- Горький.: Горьк. ун-т. 1983.- С. 39-46.

10. Вабищевич П.Н., Салаева Т.В. Пространственно-адаптивные сетки с локальным сгущением для эллиптических задач // Вест. Москв. ун-та. Сер. 15, Вычисл.матем. и киберн. 1991. - №2. - С. 15-20.

11. Зенкевич О., Морган К. Конечные элементы и аппроксимация М.: Мир, 1986. - 318 с.

12. Стренг Г., Фикс Дж. Теория метода конечных элементов. М.: Мир, 1977. - 349 с.

13. Круглякова JI.B., Неледова А.В., Тишкин В.Ф., Филатов А.Ю. Неструктурированные адаптивные сетки для задач математической физики (обзор) // Матем. моделирование. 1998. - Т. 10. - №3.- С. 93-116.

14. Копысов С.П., Новиков А.К. Оценка погрешности и h-версия МКЭ для решения задач упругости // Сб. науч. тр. "Проблемы механики и материаловедения", ИПМ УрО РАН, Ижевск, 2001, Изд. ИПМ УрО РАН, Ижевск, 2001. С. 106-114.

15. Белоцерковский О.М. Математическое моделирование на суперкомпьютерах (опыт и тенденции)// Журн. вычисл. математики и матем. физики. 2000. - Т. 40. - № 8. - С. 1173-1188.

16. Четверушкин Б.Н. Кинетически-согласованные схемы в газовой динамике: новая модель вязкого газа, алгоритмы, параллельная реализация, приложения М.: Изд. МГУ, 1999. - 232с.

17. Четверушкин Б.Н. Кинетические схемы и высокопроизводительные многопроцессорные вычисления в газовой динамике // Вычислительные технологии. Новосибирск. Изд. СО РАН. - 2002. - Т. 7. - №6.

18. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MBC-100 // Proc. of the Int. Conf. on Parallel Computing Technologies (PaCT 95). Lecture Notes in Computer Science. 1995. -Vol. 964. - P. 342-356.

19. Оден Дж. Конечные элементы в нелинейной механике сплошных сред. М.: Мир, 1976. - 349 с.

20. Норри Д.,де Фриз Ж. Введение в метод конечных элементов. М.: Мир, 1981. - 304 с.

21. Thompson J.F., Warsi Z.U.A., Mastine C.Wayne. Numerical grid generation: Foundation and applications. New York etc.: North-Holland, 1985. - 483 p.

22. Хайруллина О.Б. Методы расчета блочных оптимальных сеток в двумерных многосвязных областях // Вопросы атомной науки и техники. Сер. Мат. моделир. физ. процессов. 1992. Вып. 1. С. 62-66.

23. Прокопов Г.П. Об организации сравнения алгоритмов и программ построения регулярных двумерных разностных сеток // Вопросы атомной науки и техники. Сер. Мат. моделир. физ. процессов. 1989. Вып. 3. С. 98-108.

24. Уманский С.Э. Алгоритм и программа триангуляции двумерной области произвольной формы // Проблемы прочности. 1978. - №6. -С. 83-87.

25. Гаранжа В.А. Построение, распутывание и оптимизация трехмерных гибридных расчетных сеток // Прикл. геометрия, построение сеток и высокопроизводительные вычисления. Под ред. Ю.Г. Евтушенко, М.К. Керимов, В.А. Гаранжа. М. ВЦ РАН, 2004.

26. Cavendish J.C. Automatic triangulation of arbitary planar domains for the finite element method // Int. J. Numer. Meth. Eng., 1978, V.8, №4, P. 679-696.

27. Дворников M.B., Тишкин В.Ф., Филатов А.Ю. Триангуляция произвольной многосвязной области со сложной границей. М., 1995.- 23 с. (Препринт РАН, Ин-т. мат. моделирования: 7).

28. Яненко Н.Н., Данаев Н.Т., Лисейкин В.Д. О вариационном методе построения сеток // Числ. методы механики сплош. среды. Новосибирск. 1977. - Т. 8. - т. - С. 157-163.

29. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. -М.: Мир, 1989, 478 с.

30. Кузнецов Ю.А. Построение динамических триангуляций Делоне // Вариационные методы в задачах численного анализа. АН СССР СО, ВЦ, 1991. - С.76-83.

31. Watson D.F. Computing the n-Dimensional Delaunay Tesselations with Application to Voronoi Polytopes //Comput. J. 1981. - V. 24. - K°-2. -P. 167-172.

32. Sloan S.W. A Fast Algorithm for Constructing Delannay Triangulations in the Plane//Adv. Eng. Soft. 1987. - V. 9. - №. - P. 34-55.

33. Комарницкий В.И. Основания аналитической геометрии на плоскости и в пространстве. М.: Гостехиздат, 1933, 263 с.

34. Альес М.Ю., Копысов С.П., Варнавский А.И., Новиков А.К. Построение диаграмм Вороного и триангуляции Делоне на плоскости и в пространстве. Ижевск, 1996. - 39с. (Препринт УрО РАН, Ин-т. при-кл. механики).

35. Жермен-Лакур П., Жорж П.Л., Пистр Ф., Безье П. Математика и САПР. В 2-х кн. Кн. 2 М.:Мир, 1989. - 264 с.

36. Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.410 с.

37. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.: Мир, 1984.- 333 с.

38. Сегерлинд Jl. Применение метода конечных элементов. М.: Мир, 1979. - 392 с.

39. Галлагер Р. Метод конечных элементов. Основы. М.: Мир, 1984.428 с.

40. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М.: Наука, 1987. 600 с.

41. Рябенький B.C. Введение в вычислительную математику. М.: Физ-матлит, 1994. - 336 с.

42. Амосов А.А., Дубинский Н.П., Копченова Г.М. Вычислительные методы для инженеров. М.:Высшая Школа, 1994. - 544 с.

43. Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989. -432 с.

44. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999. -548 с.•47. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984. - 320 с.

45. Хейгеман Л., Янг Д. Прикладные итерационные методы. М.: Мир, 1999. - 548 с.

46. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1989.- 608 с.

47. Кузнецов Ю.А. Метод сопряженных градиентов, его обобщения и применения //Вычислительные процессы и системы/ Под ред. Г.И. Марчука. М.: Наука, 1983. - С.264-300.

48. Фрид. И. Еще о градиентных итерационных методах в конечноэле-ментных исследованиях //Ракетная техника и космонавтика. 1969. - Т. 7. - т. - С. 213-215.

49. Сьярле Ф. Метод конечных элементов для эллиптических задач. -М.: Мир, 1980. 512 с.

50. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы М.: Наука, 1981. - 416 с.

51. Михлин С.Г. Некоторые вопросы теории погрешностей. JL: Изд.ЛГУ, 1988. - 334 с.

52. Г^епин С.И., Фролов М.Е. Об апостериорных оценках точности приближенных решений краевых задач для уравнений эллиптического типа // Журн. вычисл. математики и матем. физики. 2002. - Т. 42. - № 12. - С. 1774-1787.

53. Копысов С.П., Альес М.Ю., Устюжанин С.Л. Сравнение способов уточнения в методе конечных элементов //В сб.: Применение мат. моделирования для решения задач в науке и технике. Ижевск, 1996. -С. 222-228.

54. Работнов Ю.Н. Механика деформируемого твердого тела. М.: Наука, 1979. - 744 с.

55. Дарьин Н.А., Мажукин В.И. Об одном подходе к построению адаптивных разностных сеток //ДАН СССР. 1986. - Т. 298. - №1. - С. 64-68.

56. Похилко В.И., Тишкин В.Ф. Метод построения адаптивных неструктурированных сеток М., 1994. - 16 с. (Препринт РАН, Инст. матем. моделирования: 18).

57. Похилко В.И., Тишкин В.Ф. О построении адаптивных сеток путем дробления ячеек М., 1995. - 12 с. (Препринт РАН, Инст. матем. моделирования: 14).

58. Mitchell W.F. A comparison of adaptive refinement tecniques for elliptic problems //ACM Trans, on Math. Soft. 1989. - V. 15.- P. 326-347.

59. Войнович П.А., Шаров Д.М. Моделирование разрывных течений газа на неструктурированных сетках. 2. Нестационарная локальная адаптация сетки // Матем, моделирование. 1993. - Т.5. - N27. -С. 101-112.

60. Rivara М.С. Design and Data Structure of Fully Adaptive, Multigrid, Finite element Software //ACM Trans, on Math. Soft. 1984. - V. 10. -№3. - P. 242-264.

61. Копысов С.П., Новиков А.К. Анализ способов перестроения треугольных конечно-элементных сеток // Тр. Мат. центра им. Н.И.

62. Лобачевского. Т.20 Казан, мат. о-во. Численные методы решения линейных и нелинейных краевых задач. Материалы второй Всерос. мо-лодеж. науч. школы-конф. 27.06-1.07.2003, Казань. Изд. Казан, мат. о-ва, Казань, 2003. -С. 170-180.

63. Capon P. J., Jimack Р.К. On the adaptive finite element solution of partial differential equations using h-r-refinement //Tech. Rep. 96.13, School of Сотр. Studies, University of Leeds, 1996.

64. Malcolm A.J. Data-dependent criteria for nodal placement with fixed connectivity in triangular grids //Rep. 16/90, University of Reading,1990.

65. Мажукин В.И., Самарский А.А. и др. Метод динамической адаптации для нестационарных задач с большими градиентами //Матем. моделирование. 1993. - Т. 5. - №4. - С. 32-56.

66. Miller, et al. Moving Finite Elements, I,II. SIAM J. Numer. Anal.,1981, v.18, №6, p. 1019-1057.

67. Jimack P.K. An optimal finite element mesh for linear elastic structural analysis // Tech. Rep. 94.20, School of Computer Studies, University of Leeds, 1994.

68. Копысов С.П., Новиков А.К. Сравнение г- и h-версий МКЭ на примере задач теории упругости // Актуальные проблемы прикл. математики и механики, 3-7 фев. 2003 г., Екатеринбург, 2003. С. 44-45.

69. Альес М.Ю., Копысов С.П., Новиков А.К. Построение и адаптация конечно-элементной сетки при решении эллиптической задачи второго порядка // Матем. моделирование. 1997. - Т.9. - №2. - 43-45.

70. Альес М.Ю., Копысов С.П., Новиков А.К. Параллельное построение плоских конечно-элементных сеток // Матем. моделирование. -1998. Т.10. -№5. - С. 71-76.

71. Альес М.Ю., Копысов С.П., Новиков А.К. Построение и отображение плоских конечно-элементных сеток на параллельной вычислительной системе // В сб.: Применение матем. моделирования для решения задач в науке и технике. Ижевск, 1996. С. 118-126.

72. Альес М.Ю., Копысов С.П., Новиков А.К. Алгоритм и реализация параллельного перестроения сетки // Сб. трудов VIII Всерос. школы-семинара "Современные проблемы матем. моделирования", РГУ, Ростов-на-Дону, 1999. С. 3-9.

73. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. М.: Мир, 1978. - 844 с.

74. Копысов С.П. Методы декомпозиции и параллельные схемы метода конечных элементов. Ижевск, 1999. - 49 с. (Препринт УрО РАН, Инст. прикл. механики).

75. Gilbert J.R., Miller G.L., Teng S.-H. Geometric mesh partitioning // Tech. Rep. CSL-94-13. Xerox PARC. - 1994.

76. Hendrickson В., Leland R. A multilevel algorithm for partitioning graphs // Rep. SAND93-0074. Sandia National Lab., Albuquerque, NM.- 1993.

77. Pilkington J.R., Baden S.B. Partitioning with specefilling curves //CSE Tech. Rep. CS94-349, Dept. Сотр. Science and Eng., University of California, San Diego, CA. 1994.

78. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. М.: Мир, 1991. - 367с.

79. Barragy Е., Carey G.F., van de Geun R. Perfomance and Scalability of Finite Element Analysis for Distributed Parallel Computation. Journal of Parallel and Distributed Computing, 1994. 21, P. 202-212.

80. Новиков А.К., Копысов С.П., Альес М.Ю. Параллельное поэлементное формирование и решение конечно-элементных уравнений // Сб.

81. Современные проблемы матем. моделирования", Ростов-на-Дону,1. РГУ, 1997. С. 107-109.

82. Kopyssov S., Novikov A. Parallel Adaptive Mesh Refinement with Load Balancing for Finite Element Method // V. Malyshkin (Eds.): Parallel Computing Technologies 6th Int. Conf., PaCT 2001, Novosibirsk, Sep. 3-7, 2001, Proceedings. 2001. P. 266-276.

83. Oden J.T., Patra A., Feng Y. Parallel Domain Decomposition Solver for Adaptive hp Finite Element Methods // Tech. Rep. TICAM 94-11.-University of Texas at Austin. -1994. 39 p.

84. Копысов С.П., Новиков А.К. Параллельные алгоритмы адаптивного перестроения и разделения неструктурированных сеток // Матем. моделирование. 2002. - Т. 14. - №9. - С. 91-96.

85. Karypis G., Schloegel. К., Kumar V. ParMetis: Parallel Graph Partitioning and Sparse Matrix Ordering Library //Tech. Rep., Dept. of Сотр. Science, University of Minnesota, 1998.

86. Devine K., Hendrickson В., Boman E., etc. Zoltan: A Dynamic Load-Balancing Library for Parallel Applications. User's Guide //Tech. Rep. SAND99-1377, Sandia National Lab., Albuquerque, 1999.

87. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: Complete Reference. London: MIT Press, 1996. - 350 p.

88. Alies M.Yu., Kopyssov S.P., Ustushanin S.L., Novikov A.K. Estimation of influence of nonlinear behaviour of SRP at complex loading // Int.conf. on combustion (ICOC(93)) Moscow-St.-Petersburg, Russia 21-26 June 1993. r P. 280-294.

89. Альес M. Ю., Копысов С.П., Новиков А.К., Устюжанин СЛ. Адаптивный конечно-элементный метод при решении задач деформирования зарядов //В сб. "Современные проблемы внутренней баллистики РДТТ". Ижевск, 1996. - С. 218-227.

90. Основы строительной механики ракет /Балабух Л.И., Колесников К.С., Зарубин B.C. и др. М. : Высшая школа, 1969. - 496с.

91. Гидротехнические сооружения. Справочник проектировщика /Под общ. ред. В.П. Недриги. М.: Стройиздат, 1983. - 543 с.