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

Во многих фундаментальных и прикладных исследованиях большое значение имеют задачи рассеяния волновых полей различной физической природы на объектах сложной структуры. К таким прикладным областям, в частности, относятся: построение диэлектрических антеннзадачи физики плазмы рассеяние электромагнитных волн на плазменных образованияхзадачи акустики рассеяние звуковых волн на прозрачных телахзадачи квантовомеханического рассеяния на потенциалах. При этом потребности практики диктуют необходимость решения подобных задач в постановке, максимально приближенной к реальной. Это значит, что актуальными становятся задачи рассеяния волновых полей на трехмерных объектах сложной формы и с переменными параметрами. Естественно, что решение подобных задач возможно только с и работы использованием современных численных Целью методов настояш, ей высокопроизводительных компьютеров. является разработка и реализация программной системы для расчета характеристик рассеяния волн различной физической природы на сложных структурах. Долгое время считалось, что наиболее адекватным математическим аппаратом для описания рассматриваемых задач рассеяния являются дифференциальные уравнения. Действительно, на основе дифференциальных постановок задач был получен ряд аналитических решений для простейших рассеивающих объектов. Однако при численном решении, которое необходимо при математическом моделировании реальных задач, дифференциальная постановка приводит к большим вычислительным затратам. Эти затраты обусловлены тем, что искомое решение должно удовлетворять условию излучения на бесконечности. Альтернативной математической постановкой рассматриваемых задач являются интегральные уравнения относительно искомого поля только в области рассеяния. При этом интегральные уравнения после дискретизации сводятся к системам линейных алгебраических уравнений [СЛАУ) значительно меньшей размерности N, чем в случае использования дифференциальной постановки. Однако матрица СЛАУ, в силу интегральной постановки, оказывается полностью заполненной, что приводит к практической невозможности использования прямых методов (метод Гаусса) для численного решения, особенно для трехмерных рассеивающих объектов. В последнее время ряд исследователей [32, 69, 79] обратили внимание на то, что ядра интегральных уравнений задач рассеяния зависят только от разности декартовых аргументов, что позволяет построить, при соответствующей дискретизации, эффективные итерационные алгоритмы решения соответствующих СЛАУ. В диссертационной работе последовательно рассматриваются эффективные вычислительные алгоритмы для численного решения интегральных уравнений задач рассеяния: способы дискретизации интегральных уравнений- «быстрые» алгоритмы умножения матрицы СЛАУ на вектор, использующие быстрое дискретное преобразование Фурье (БПФ) — быстросходящиеся итерационные методы. В работе рассматривается программная реализация вычислительных алгоритмов. Рассматривается пользовательский интерфейс, который позволяет создать требуемую задачу. Актуальность проблемы В настоящее время потребности практики приводят к необходимости как можно более точного моделирования реальных устройств и систем. При этом во многих случаях в результате численного моделирования исходная задача сводится к системам линейных алгебраических уравнений (СЛАУ) очень большой размерности (больше миллиона неизвестных) с плотной матрицей. Такие СЛАУ возникают, как правило, при численном решении многомерных стандартных интегральных программных уравнений. систем Ясно, что использование задач для решения подобных невозможно, поскольку это приводит к потребности в нереальных вычислительных ресурсах как по быстродействию, так и по памяти. Поэтому актуальной является выработка общего подхода и критериев, которые можно применять при разработке и реализации программных систем, предназначенных для решения указанных задач. К числу таких проблем относятся задачи рассеяния волн различной физической природы на сложных структурах. Подобные задачи появляются во многих практически важных областях: моделирование диэлектрических антенн для расчёта их характеристик, моделирование электромагнитного полупроводниках с рассеяния целью от их дислокаций и примесей в дистанционного обнаружения, моделирование взаимодействия звукового поля с препятствиями и т. п. Данные задачи, в силу трехмерной постановки, приводят к необходимости решать системы линейных алгебраических уравнений (СЛАУ) сверхбольшой размерности (число неизвестных больше миллиона] с плотной матрицей. Таким образом, актуальными являются разработка эффективных вычислительных алгоритмов, разработка и реализация программной системы для моделирования рассеяния волн на сложных структурах. Цели и задачи исследования Разработка критериев, необходимых при создании и реализации программных комплексов, предназначенных для решения задач большой размерности. Разработка эффективных «быстрых» алгоритмов численного решения для задач рассеяния волн на сложных структурах, которые сводятся к СЛАУ сверхбольшой размерности (с количеством неизвестных 10). Разработка и реализация программного комплекса с удобным пользовательским интерфейсом для решения задач рассеяния волн различной физической природы на сложных структурах, которые сводятся к СЛАУ сверхбольшой размерности. Методы исследования При работе над диссертацией использовались: теория программирования, теория алгоритмов, методы теории сложных систем, методы, методы теория аппроксимации функций, итерационные дифференциальных и интегральных уравнений. Научная новизна исследований и полученных результатов Предложен общий подход и критерии, которые необходимы при разработке и реализации программных комплексов, предназначенных для решения задач реальном масштабе времени. большой размерности в Исследованы проблемы, возникающие при численном решении задач рассеяния волн на сложных структурах, которые сводятся к многомерным интегральным уравнениям с ядрами, зависящими только от разности аргументов. Разработаны эффективные «быстрые» алгоритмы численного решения рассматриваемых задач рассеяния. Разработан и реализован программный комплекс с удобным решать задачи пользовательским интерфейсом, позволяющий рассеяния в различных предметных областях, которые сводятся к СЛАУ сверхбольшой размерности [10 неизвестных}.Достоверность научных положений, выводов и практических рекомендаций Достоверность рекомендаций обоснованием, научных положений, выводов и практических математическим эксперимента, подтверждены результатами соответствующим численного подтверждающими правильность теоретических выводов. Практическое значение работы Изложенные в работе общий подход и критерии используются при разработке и реализации программных комплексов, предназначенных для решения задач, сводящихся к СЛАУ очень большой размерности и плотной матрицей. Предложенные эффективные «быстрые» алгоритмы используются, как составные части, при разработке численных методов решения в других предметных областях. Разработанный программный комплекс может использоваться для моделирования задач рассеяния волн различной физической природы на сложных структурах, в частности при моделировании диэлектрических антенн. Внедрение Алгоритмы и программные средства работы используются в Институте электронных управляющих машин РАН и в Московском физикотехническом институте при проведении научно-исследовательских работ. Апробация работы Результаты работы были представлены на IV Международной научной конференции «Идентификация систем и задачи управления» в Институте проблем управления РАНLXI Научной сессии, посвященной Дню Радио, в Российском научно-техническом обществе радиотехники, электроники и связи имени А. С. Поповадокладывались на научных семинарах. Публикации За время работы над диссертацией было опубликовано пять научных работ, в том числе одна статья в журнале «Дифференциальные уравнения». Структура работы В первой главе диссертации рассматривается общий подход и критерии, которые необходимы при разработке и реализации программных систем, предназначенных для решения задач большой размерности. Во второй главе дается общая математическая постановка рассматриваемых задач рассеяния с помощью многомерных интегральных уравнений. Приводится конкретный вид интегральных уравнений для нескольких предметных областей. Для электромагнитных задач математически строго описана область локализации спектра оператора для квазистатического случая (длина дает волны значительно меньше рассеивающего объекта), что возможность построить быстросходящиеся итерационные алгоритмы. В третьей главе рассматриваются численные алгоритмы решения рассматриваемых интегральных задач. Обсуждаются способы дискретизации быстрого уравнений. Рассматриваются алгоритмы преобразования Фурье (БПФ) для слзая, когда размерность задачи представляется в виде произведения простых чисел, не обязательно степеней двойки. С использованием эффективный Обсуждаются алгоритм умножения методы: алгоритмов матрицы БПФ приводится СЛАУ на вектор. простой итерационные обобщенный метод итерациимногошаговый метод минимальных невязок. В четвёртой главе рассматриваются (ПК), подходы к реализации расчёт Программного Комплекса осуществляющего рассматриваемых задач. Рассмотрены основные подходы, связанные с реализацией объектной модели задачи, а также математических алгоритмов, используемых при расчёте. Описан подход, используемый для абстрагирования ядра ПК от реализации конкретных физических моделей. Рассмотрены подходы к реализации параллельного вычисления рассматриваемых задач. Некоторые программы, написанные для решения поставленных задач, приводятся в приложениях. На защиту выносятся следующие основные результаты, полученные в диссертации: Исследованы проблемы, возникающие при численном решении задач рассеяния волн на сложных структурах, которые сводятся к многомерным интегральным уравнениям с ядрами, зависящими только от разности аргументов. Реализованы эффективные «быстрые» алгоритмы численного решения рассматриваемых неизвестных Разработан Программный задач, сводящиеся к СЛАУ с 10 Комплекс, природы, позволяющий сводящиеся решать к СЛАУ физические задачи различной сверхбольшой размерности и теплицевой матрицей Для Программного Комплекса разработана библиотека рассеяния электромагнитных волн на сложных структурах расчёта 1 Общий подход и критерии для решения задач большой размерности Подобные задачи возникают при численном решении многих функциональных задач, особенно в многомерных случаях. Например, при дискретизации дифференциальных или интегральных уравнений в трехмерных случаях могут возникать системы линейных алгебраических уравнений [СЛАУ) огромной размерности [больше миллиона неизвестных]. При этом такие СЛАУ являются далеко не экзотическими, а появляются практически в результате потребности в моделировании в трехмерных многих задачах важных процессов, например электромагнитного рассеяния. Сначала рассмотрим сложность решения подобных задач. Мы будем использовать два основных параметра, которые характеризуют сложность вычислительного алгоритма объем памяти М и число арифметических операций Т, которые требуются для реализации алгоритма. Выбор этих критериев ясен, поскольку они определяют требуемые вычислительные ресурсы [память и время) для решения поставленной задачи. При использовании многопроцессорных вычислительных систем следует использовать эффективный параметр Гэфф, который связан с полным числом арифметических операций Т неравенством СТ Здесь т число процессоров, а С 1 величина, зависящая от архитектуры многопроцессорной системы и особенностей распараллеливания алгоритма. Сначала оценим сложность вычислительных алгоритмов при решении дифференциальных задач. В этом случае матрица СЛАУ, получающаяся после дискретизации дифференциальных уравнений, оказывается очень сильно разреженной, т. е. количество ненулевых элементов матрицы N, где N размерность СЛАУ. Для таких СЛАУ, как с использованием прямых, так и итерационных методов, разработаны вычислительные алгоритмы со следующей оценкой сложности Приведенные оценки показывают, что возможно численное решение дифференциальных уравнений, которые сводятся к СЛАУ большой размерности. С помощью указанных алгоритмов решено множество практически важных задач. Многие актуальные задачи из самых разных областей, в том числе волновые задачи рассеяния, описываются многомерными, например объемными, интегральными уравнениями в ограниченных областях. Долгое время инженеры-вычислители считали бесперспективным численное решение подобных задач. Действительно, в этих случаях матрица СЛАУ, получающаяся после дискретизации интегрального уравнения, оказывается плотной и в общем случае для ее хранения требуется N ячеек памяти, а количество арифметических операций при реализации прямого метода Гаусса Л/. Совершенно ясно, что использование стандартных программных систем приводит к нереальным вычислительным затратам, поскольку размерность СЛАУ очень большая. При этом использование высокопроизводительных вычислительных систем принципиально ситуацию изменить не может, поскольку, при более точном моделировании задач, размерность N будет очень сильно возрастать. Для численного решения указанных СЛАУ рассмотрим итерационные методы. Умножение матрицы СЛАУ на вектор является наиболее трудоемкой операцией в итерационных методах. Поэтому количество таких умножений в процессе реализации алгоритма будем называть числом итераций. Тогда величину Т, можно оценить формулой Где L число итераций, SLT число арифметических операций, которое требуется для умножения матрицы СЛАУ на произвольный вектор. Важная проблема численного решения многомерных интегральных уравнений минимизация числа итераций L. Поскольку размерность рассматриваемых СЛАУ огромная, необходимо использовать такие итерационные методы, сходимость которых зависит только от физических характеристик задачи и не зависит (точнее очень слабо зависит) от способа дискретизации интегрального уравнения. Другими словами, при уменьшении аппроксимации шага сетки, например для повышения точности не интегрального оператора, сходимость итераций должна изменяться. К таким итерационным методам относятся: GMRES (многошаговый метод минимальных невязок) и его модификацииQMR (метод квази-минимальных невязок) и его модификацииметод простой итерации и ряд других [60,68,69,80]. Сходимость этих итерационных процедур зависит от спектра оператора и, поскольку он мало меняется от способа дискретизации, удовлетворяет указанному выше критерию (скорость сходимости не зависит от шага сетки). При этом число итераций, требуемое для получения решения с относительной точностью 10* (это достаточная точность для большинства прикладных задач), обычно находится в пределах 10 300 итераций. Очень важная проблема число операций, требуемое для умножения матрицы СЛАУ на вектор Тд. Ясно, что в случае плотной матрицы произвольного вида имеем Тд «N. Для кардинального уменьшения величины Тд необходимо учитывать следующее обстоятельство ядра многомерных интегральных уравнений математической физики зависят только от разности декартовых аргументов. Поэтому при дискретизации целесообразно учитывать это обстоятельство с целью получения матрицы СЛАУ, которая будет обладать соответствующими свойствами симметрии [теплицевы матрицы). Фурье, Тогда, можно используя построить алгоритмы «быстрые» быстрого алгоритмы преобразования умножения матрицы СЛАУ на вектор. Кроме того, количество различных элементов матрицы N, что является приемлемым с точки зрения памяти компьютера. Приведем критерии, которым должны удовлетворять вычислительные алгоритмы программной системы, предназначенной для решения задач большой размерности: Здесь N число неизвестных, k (_N), с (Ы) функции, которые очень мало изменяются с ростом N, например функция логарифма. Для того чтобы добиться выполнения указанных критериев, необходимо последовательно учитывать специфику и особенности исходного интегрального уравнения. Приведенные критерии сложности асимптотически близки к критериям сложности численного решения дифференциальных задач. Рассмотрим требования, которым должен удовлетворять программный комплекс, предназначенный для решения задач большой размерности. ПК (Программный Комплекс) должен обладать пользовательским интерфейсом, позволяющим в удобной форме задавать сложные модели, состоящие из геометрических форм и физических параметров ПК должен позволять в аналитическом виде записывать правую часть искомой задачи ПК должен быть расширяемым, с возможностью подключать новые физические задачи.

Заключение

.

В диссертационной работе решены следующие основные задачи:

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

• Реализованы эффективные «быстрые» алгоритмы численного решения рассматриваемых задач, сводящиеся к СЛАУ с ~106 неизвестных.

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

• Для Программного Комплекса разработана библиотека расчёта рассеяния электромагнитных волн на сложных структурах.