Содержание к диссертации
Введение
1 Общий подход и критерии для решения задач большой размерности 12
2 Математические формулировки задач рассеяния 17
2.1 Общие положения 17
2.2 Рассеяние электромагнитных волн на диэлектрическом теле 18
2.3 Задачи акустического рассеяния 26
3 Численные алгоритмы решения задач рассеяния 28
3.1 Общие положения 28
3.2 Дискретизация интегральных уравнений 29
3.3 Итерационные алгоритмы 36
3.3.1 Метод простой итерации 36
3.3.2 Метод минимальных невязок 41
3.4 Алгоритмы быстрого преобразования Фурье, используемые при решении задач большой размерности 45
3.5 Быстрый алгоритм умножения теплицевои матрицы на произвольный вектор 47
4 Структура программного комплекса ВО
4.1 Основные определения 50
4.2 Требования к реализации Программного Комплекса 52
4.3 Средства реализации Программного Комплекса 53
4.4 Основные принципы. Объектная модель системы 54
4.5 Подсистема основных объектов ПК 55
4.5.1 Модуль работы с моделями системы 55
4.5.2 Модуль работы с материалами объектов 56
4.5.3 Инфраструктура подключаемых задач 57
4.6 Подсистема работы с математическими объектами 58
4.6.1 Комплексные числа 58
4.6.2 Модуль быстрого преобразования Фурье 60
4.6.3 Модуль операторной алгебры 62
4.6.4 Модуль умножения матрицы большой размерности на вектор 64
4.6.5 Модуль итераций .66
4.7 Реализация подключаемой физической задачи на примере рассеяния электромагнитных волн 68
4.8 Препроцессор 68
4.9 Процессор 69
4.10 Постпроцессор 70
4.11 Общая схема пользовательского интерфейса Программного Комплекса 71
4.12 Параллельные вычисления 72
4.12.1 Основные типы параллельных систем 72
4.12.2 Использование параллельных вычислений в ПК 73
4.13 Автоматизированное тестирование ПК 76
4.14 Результаты вычислений 77
Заключение 81
Список литературы 82
Приложения 89
- Общий подход и критерии для решения задач большой размерности
- Общие положения
- Дискретизация интегральных уравнений
- Требования к реализации Программного Комплекса
Введение к работе
Во многих фундаментальных и прикладных исследованиях большое значение имеют задачи рассеяния волновых полей различной физической природы на объектах сложной структуры. К таким прикладным областям, в частности, относятся: построение диэлектрических антенн; задачи физики плазмы - рассеяние электромагнитных волн на плазменных образованиях; задачи акустики - рассеяние звуковых волн на прозрачных телах; задачи квантовомеханического рассеяния на потенциалах. При этом потребности практики диктуют необходимость решения подобных задач в постановке, максимально приближенной к реальной. Это значит, что актуальными становятся задачи рассеяния волновых полей на трехмерных объектах сложной формы и с переменными параметрами. Естественно, что решение подобных задач возможно только с использованием современных численных методов и высокопроизводительных компьютеров. Целью настоящей работы является разработка и реализация программной системы для расчета характеристик рассеяния волн различной физической природы на сложных структурах.
Долгое время считалось, что наиболее адекватным математическим аппаратом для описания рассматриваемых задач рассеяния являются дифференциальные уравнения. Действительно, на основе дифференциальных постановок задач был получен ряд аналитических решений для простейших рассеивающих объектов. Однако при численном решении, которое необходимо при математическом моделировании реальных задач, дифференциальная постановка приводит к большим вычислительным затратам. Эти затраты обусловлены тем, что искомое решение должно удовлетворять условию излучения на бесконечности. Альтернативной математической постановкой рассматриваемых задач являются интегральные уравнения относительно искомого поля только в области рассеяния. При этом интегральные уравнения после дискретизации сводятся к системам линейных алгебраических уравнений [СЛАУ) значительно меньшей размерности N, чем в случае использования дифференциальной постановки. Однако матрица СЛАУ, в силу интегральной постановки, оказывается полностью заполненной, что приводит к практической невозможности использования прямых методов (метод Гаусса) для численного решения, особенно для трехмерных рассеивающих объектов. В последнее время ряд исследователей [32, 69, 79] обратили внимание на то, что ядра интегральных уравнений задач рассеяния зависят только от разности декартовых аргументов, что позволяет построить, при соответствующей дискретизации, эффективные итерационные алгоритмы решения соответствующих СЛАУ.
В диссертационной работе последовательно рассматриваются эффективные вычислительные алгоритмы для численного решения интегральных уравнений задач рассеяния: способы дискретизации интегральных уравнений; «быстрые» алгоритмы умножения матрицы СЛАУ на вектор, использующие быстрое дискретное преобразование Фурье (БПФ); быстросходящиеся итерационные методы. В работе рассматривается программная реализация вычислительных алгоритмов. Рассматривается пользовательский интерфейс, который позволяет создать требуемую задачу.
Общий подход и критерии для решения задач большой размерности
Подобные задачи возникают при численном решении многих функциональных задач, особенно в многомерных случаях. Например, при дискретизации дифференциальных или интегральных уравнений в трехмерных случаях могут возникать системы линейных алгебраических уравнений [СЛАУ] огромной размерности [больше миллиона неизвестных]. При этом такие СЛАУ являются далеко не экзотическими, а появляются в результате потребности в моделировании многих практически важных процессов, например в трехмерных задачах электромагнитного рассеяния. Сначала рассмотрим сложность решения подобных задач.
Мы будем использовать два основных параметра, которые характеризуют сложность вычислительного алгоритма - объем памяти М и число арифметических операций Т, которые требуются для реализации алгоритма. Выбор этих критериев ясен, поскольку они определяют требуемые вычислительные ресурсы [память и время] для решения поставленной задачи. При использовании многопроцессорных вычислительных систем следует использовать эффективный параметр ТЭфф, который связан с полным числом арифметических операций Т неравенством.
Здесь m - число процессоров, а С 1 - величина, зависящая от архитектуры многопроцессорной системы и особенностей распараллеливания алгоритма. Сначала оценим сложность вычислительных алгоритмов при решении дифференциальных задач. В этом случае матрица СЛАУ, получающаяся после дискретизации дифференциальных уравнений, оказывается очень сильно разреженной, т.е. количество ненулевых элементов матрицы N, где N - размерность СЛАУ. Для таких СЛАУ, как с использованием прямых, так и итерационных методов, разработаны вычислительные алгоритмы со следующей оценкой сложности.
Приведенные оценки показывают, что возможно численное решение дифференциальных уравнений, которые сводятся к СЛАУ большой размерности. С помощью указанных алгоритмов решено множество практически важных задач.
Многие актуальные задачи из самых разных областей, в том числе волновые задачи рассеяния, описываются многомерными, например объемными, интегральными уравнениями в ограниченных областях. Долгое время инженеры-вычислители считали бесперспективным численное решение подобных задач. Действительно, в этих случаях матрица СЛАУ, получающаяся после дискретизации интегрального уравнения, оказывается плотной и в общем случае для ее хранения требуется N2 ячеек памяти, а количество арифметических операций при реализации прямого метода Гаусса N3. Совершенно ясно, что использование стандартных программных систем приводит к нереальным вычислительным затратам, поскольку размерность СЛАУ очень большая. При этом использование высокопроизводительных вычислительных систем принципиально ситуацию изменить не может, поскольку, при более точном моделировании задач, размерность N будет очень сильно возрастать. Для численного решения указанных СЛАУ рассмотрим итерационные методы. Умножение матрицы СЛАУ на вектор является наиболее трудоемкой операцией в итерационных методах. Поэтому количество таких умножений в процессе реализации алгоритма будем называть числом итераций. Тогда величину 7, можно оценить формулой Где L - число итераций, а ТА - число арифметических операций, которое требуется для умножения матрицы СЛАУ на произвольный вектор.
Важная проблема численного решения многомерных интегральных уравнений - минимизация числа итераций L. Поскольку размерность рассматриваемых СЛАУ огромная, необходимо использовать такие итерационные методы, сходимость которых зависит только от физических характеристик задачи и не зависит [точнее очень слабо зависит] от способа дискретизации интегрального уравнения. Другими словами, при уменьшении шага сетки, например для повышения точности аппроксимации интегрального оператора, сходимость итераций не должна изменяться. К таким итерационным методам относятся: GMRES [многошаговый метод минимальных невязок] и его модификации; QMR [метод квази-минимальных невязок] и его модификации; метод простой итерации и ряд других [60,68,69,80]. Сходимость этих итерационных процедур зависит от спектра оператора и, поскольку он мало меняется от способа дискретизации, удовлетворяет указанному выше критерию [скорость сходимости не зависит от шага сетки). При этом число итераций, требуемое для получения решения с относительной точностью 10 4 (это достаточная точность для большинства прикладных задач), обычно находится в пределах 10 - 300 итераций. Очень важная проблема - число операций, требуемое для умножения матрицы СЛАУ на вектор ТА. Ясно, что в случае плотной матрицы произвольного вида имеем Тд »N2. Для кардинального уменьшения величины ТА необходимо учитывать следующее обстоятельство - ядра многомерных интегральных уравнений математической физики зависят только от разности декартовых аргументов. Поэтому при дискретизации целесообразно учитывать это обстоятельство с целью получения матрицы СЛАУ, которая будет обладать соответствующими свойствами симметрии (теплицевы матрицы). Тогда, используя алгоритмы быстрого преобразования Фурье, можно построить «быстрые» алгоритмы умножения матрицы СЛАУ на вектор. Кроме того, количество различных элементов матрицы N, что является приемлемым с точки зрения памяти компьютера.
Общие положения
В данной работе, в которой используется ряд результатов изложенных в [69,73], будем рассматривать многомерные интегральные уравнения следующего вида.
Здесь и(х), f(x) это n-мерные вектора; а{х) и К(л:) -1x1 матрицы; г = х — у] - расстояние между точками х и у n-мерного эвклидова пространства Яп с декартовыми координатами х = (х1(...,хп),у = (уі,...,уп) Q " n-мерная ограниченная область Еп. Многие важные классы задач математической физики описываются уравнениями вида (2-1), например задачи электромагнитного и акустического рассеяния на прозрачных телах. При этом интегральный оператор для акустических задач является скалярным и компактным, а для трехмерных электромагнитных задач - матричным и сингулярным. В дальнейшем будем полагать, что уравнение (2-1) имеет единственное решение в некотором функциональном гильбертовом пространстве, а интегральный оператор в (2-1) может быть как компактным и тогда т п, так и сингулярным и тогда т = п.
Ниже опишем конкретные классы задач из областей электродинамики и акустики.
Дискретизация интегральных уравнений
Для численного решения интегральное уравнение [2-1) должно быть сведено к системе линейных алгебраических уравнений [СЛАУ], при этом получившаяся система должна аппроксимировать решение исходной задачи с заданной точностью. Пусть h - характерный линейный размер, на котором решение и мало меняется по сравнению с заданной точностью. Как правило, априори известны значения h, в зависимости от требуемой точности решения. Тогда размерность СЛАУ оценивается формулой.
Ниже будем рассматривать численное решение интегрального уравнения [2-1), которое сводится к СЛАУ очень большой размерности. Ясно, что в этих случаях мы можем использовать только итерационные методы. Главными критериями эффективности любого численного алгоритма являются: число арифметических операций Т, которое требуется выполнить для получения решения исходной задачи с заданной точностью; объем требуемой памяти М для реализации алгоритма. Умножение матрицы СЛАУ на вектор является наиболее трудоемкой операцией в итерационных методах. Поэтому количество таких умножений в процессе реализации алгоритма будем называть числом итераций. Тогда величину Т, можно оценить формулой.
Здесь L - число итераций; ТА - число арифметических операций, которое необходимо для умножения матрицы на вектор, а Т0 - число арифметических операций для других вычислений. Как правило, 7 0 « Тд. Наша цель состоит в минимизации величин ТА, LnM..
Требования к реализации Программного Комплекса
При разработке ПК основными требованиями для реализации были следующие:
1. Объектно-ориентированность. Все математические объекты и алгоритмы должны быть представлены в виде объектов с чёткими и явными зависимостями.
2. Расширяемость. ПК должен содержать некоторый набор типичных задач. В то же время пользователь может самостоятельно создавать новые задачи, аналитически записывая ядро интегрального уравнения, правую часть, и требуемый функционал решения.
3. Пользовательский интерфейс. Пользователь задаёт контейнер, в котором будет рассчитано решение задачи. Контейнер состоит из объектов, каждый из которых может быть наделён различными физическими свойствами. Например, в случае задач электромагнитного рассеяния это диэлектрическая и магнитная проницаемости. После создания модели, пользователь может рассчитать задачу и, задав в аналитическом виде функционал решения, просмотреть результат в каждом из разрезов модели.
4. Возможность сохранения моделей и результатов. Пользователь имеет возможность сохранять созданные модели, а также результаты их расчёта.
5. Скорость решения задачи. При численном решении используются эффективные «быстрые» алгоритмы.
