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

Российская Академия наук Институт проблем управления им. В. А. Трапезникова

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

САМОХИН Алексей Александрович

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 20 Об

Работа выполнена в Институте проблем управления им В. А. Трапезникова Российской Академии наук.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Заслуженный деятель науки РФ, доктор технических наук, профессор Трахтенгерц Эдуард Анатольевич

Заслуженный деятель науки РФ, доктор физико-математических наук, профессор Лукин Дмитрий Сергеевич

Кандидат технических наук, доцент Григорьев Виктор Карлович

Институт электронных управляющих машин РАН

Защита диссертации состоится <с1г~у> К 2006 г. в ^ 1 час. на

заседании Специализированного совета №3 (Д 002.226.03) Института проблем управления по адресу: 117977, г. Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В.А. Трапезникова.

Автореферат разослан «. 23 » еиср 2006 г.

Ученый секретарь специализированного совета доктор технических наук

Е.В. Юркевич

шм

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

Диссертационная работа посвящена разработке новых подходов и методов создания программных комплексов, предназначенных для решения задач большой размерности [с количеством неизвестных до нескольких миллионов). Такие задачи возникают при численном решении многомерных интегральных уравнений. В диссертационной работе приведены критерии, которые необходимы при разработке и реализации подобных вычислительных систем. Для случая задач рассеяния волн на сложных структурах, которые сводятся к системам линейных алгебраических уравнений большой размерности (больше миллиона неизвестных), построены эффективные «быстрые» численные алгоритмы решения, разработан и реализован программный комплекс с удобным пользовательским интерфейсом.

Актуальность проблемы

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

"РОС. НАЦИОНЛДЬ^ч ; библиотека

С.-Пегербург

ОЭ 200 гЦЦ 1

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

Цели и задачи исследования

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

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

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

Методы исследования

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

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

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

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

• Разработаны эффективные «быстрые» алгоритмы численного решения рассматриваемых задач рассеяния.

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

Практическое значение работы

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

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

Внедрение

Алгоритмы и программные средства работы используются в Институте электронных управляющих машин РАН и в Московском физико-техническом институте при проведении научно-исследовательских работ.

Апробация работы

Результаты работы были представлены на IV Международной научной конференции «Идентификация систем и задачи управления» в Институте проблем управления РАН; ЬХ1 Научной сессии, посвященной Дню Радио, в Российском научно-техническом обществе радиотехники, электроники и связи имени А.С. Попова; докладывались на научных семинарах.

Публикации

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

Объём и структура диссертации

Работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объем диссертации составляет 97 страниц. Список литературы включает 85 наименований.

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

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

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

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

программной системы, предназначенной для решения задач большой размерности:

M~k(N)N, T~c(N~)N

Здесь N - количество неизвестных, k(N), c(N) - функции, которые очень мало изменяются с ростом N, например функция логарифма. В работе показано, что для того, чтобы добиться выполнения указанных критериев, можно использовать общий подход к решению различных физических задач, но, в то же время, необходимо последовательно учитывать специфику и особенности исходного интегрального уравнения.

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

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

Во второй главе приводится математическая формулировка задач рассеяния волн различной физической природы на прозрачных объектах. Рассматриваются многомерные интегральные уравнения следующего общего вида:

аШОО + f dy = Пх) (1)

<3

Здесь и(хХ f(x) это /-мерные вектора; а(дО и К(х) -1x1 матрицы; г=\х — у| - расстояние между точками х и у n-мерного эвклидова пространства Еп с декартовыми координатами х = (хъ ...,х„),у =

(у1; ...,уп), (} - п-мерная конечная область [п=2 для двухмерных задач и п=3 для трехмерных задач]. Многие важные классы задач математической физики описываются уравнениями вида (1), например задачи электромагнитного и акустического рассеяния на прозрачных телах. Отметим, что ядро интегрального уравнения зависит только от разности аргументов, что будет использовано в дальнейшем при построении «быстрых» вычислительных алгоритмов и реализующих их программ.

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

Для электромагнитных задач получено строгое описание области локализации спектра оператора для квазистатического случая (длина волны значительно меньше размеров рассеивающего объекта), что дает возможность построить быстросходящиеся итерационные алгоритмы [метод простой итерации). Приводится интегральное неравенство, которое используется для обоснования применимости итерационного метода минимальных невязок при решении задач рассеяния.

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

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

Т~Ь(.ТА + Т0) (2)

Здесь £. - число итераций (количество умножений матрицы на вектор), требующихся для достижения заданной точности; ТА - число

арифметических операций, которое необходимо для умножения матрицы на вектор, а Т0 - число арифметических операций для других вычислений. Как правило, Т0 « ТА.

Для повышения эффективности алгоритмов необходимо, по возможности, минимизировать величины ТА, I и М, где М - объём требуемой оперативной памяти.

Обсуждаются способы дискретизации интегральных уравнений. Область <2 помещается в прямоугольный параллелепипед П со сторонами N0цЛ = 1,п, где /ц - шаги сетки по декартовым координатам. Для дискретизации интегральных уравнений используется метод коллокации с узловыми точками в центрах ячеек параллелепипеда. Тогда можно показать, что элементы матрицы СЛАУ, к которой сводится исходное интегральное уравнение, зависят только от разности индексов. При этом для описания матрицы используется многоиндексная нумерация. В этом случае количество различных элементов матрицы ~Л/ и значит М~Л/, где N -размерность СЛАУ.

Любой итерационный алгоритм использует умножение матрицы СЛАУ на вектор. В работе приводится эффективный «быстрый» алгоритм умножения матрицы СЛАУ, получающейся в результате дискретизации интегрального уравнения, на вектор. Алгоритм использует тот факт, что элементы в матрице зависят только от разности индексов. В этом случае исходную матрицу можно расширить до циркулянтной матрицы, которая определяется только одним вектором размерности ~А/, который будем называть расширенным вектором матрицы. Размерность расширенного вектора в 4 раза больше размерности исходной матрицы для двухмерных задач и в 8 раз больше для трехмерных задач. Затем, достраивая исходный вектор нулями до размерности расширенного вектора матрицы и

используя быстрое преобразование Фурье (БПФ), можно построить «быстрый» алгоритм умножения исходной матрицы на вектор. В работе приведены алгоритмы БПФ для случая, когда размерность представляется в виде произведения простых чисел, не обязательно двойки.

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

Та « I2 (Д ty) (jj 2-1 LOG (3)

где

п i=1

a Ki - простые сомножители целого числа К, которые учитываются с учетом их кратности.

Из (3) следует грубая оценка для количества арифметических операций

TA~NLOG(N), (4)

где N -размерность СЛАУ.

Таким образом, предложенный алгоритм позволяет кардинально уменьшить сложность вычислений одной итерации с ~ЛГ2 (в общем случае] до ~WLOG(/V). Например, в случае N = 10б (миллион неизвестных)

выигрыш составит = ^ = ^-10* раз.

Блок-схему «быстрого» алгоритма умножения матрицы СЛАУ на вектор, для случая п=3, т.е. для трехмерных задач, можно изобразить следующим образом:

Блок-схема быстрого алгоритма умножения матрицы на вектор

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

невязок не требует знания спектра и в работе обсуждается использование этого метода для общего случая.

В четвертой главе рассмотрены методы реализации программного комплекса (ПК), осуществляющего численное решение рассматриваемых задач волнового рассеяния.

Рассмотрена общая структура системы и даны основные понятия.

Схема Программного Комплекса

Моделью называется контейнер (параллелепипед), обладающий заданными геометрическими параметрами. Геометрические параметры контейнера задаются в единицах модульной сетки. Шаг модульной сетки в физических единицах также задаётся пользователем. В контейнере можно задать один или более объектов.

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

Сценарий работы пользователя

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

В работе детально описаны подходы к реализации программной модели ПК:

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

» Создание дизайнера физической задачи (препроцессора). Дизайнер физической задачи позволяет пользователю быстро конструировать интересующую задачу рассеяния.

• Реализация интерфейса вычислительного модуля, позволяющего задавать расчётные параметры задачи.

• Создание модуля для анализа результатов решения (постпроцессора), который позволяет пользователю просматривать значения целевых функций решения.

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

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

1. Задание геометрических параметров модели (шаг сетки, размеры)

2. Выбор физической задачи [рассеяние электромагнитных волн, рассеяние акустических волн и др.)

3. Задание правой части интегрального уравнения (внешнее поле)

4. Добавление объектов в модель, задание их геометрических и физических параметров

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

Детально описаны подходы, применяемые для минимизации вычислительных ресурсов, требующихся для алгоритма:

• Использование многоиндексной нумерации позволяет существенно упростить вычисления. Многоиндексная нумерация заключается в том, что рассматривается вектор с п индексами (п = 2 для двухмерных задач и п=3 для трехмерных задач).

• Применяется "послойное" преобразование Фурье, уменьшающее в 4 раза объём оперативной памяти, требующейся для Фурье-преобразования расширенного вектора.

• Производится выбор оптимального линейного представления в памяти п-мерных векторов, что позволяет, в среднем, на 10-15% уменьшить время обработки вектора.

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

Приведены результаты расчёта задач рассеяния при помощи разработанных алгоритмов и программ. На основании проведенных исследований можно сделать следующие выводы:

• Возможно решение задач с числом неизвестных до 3-5 миллионов. Например, для трехмерных задач электромагнитного рассеяния (самые трудоемкие задачи) с числом неизвестных 3 миллиона (количество узловых точек 1 миллион, в каждой узловой точке определяются 3 декартовых компоненты электрического поля) время выполнения одной итерации - 80 секунд. Число итераций, в зависимости от физических параметров задачи, изменялось от 20 до 500. Вычисления производились на 32-битном процессоре AMD Athlon 2 GHz.

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

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

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

В последнее время начат массовый выпуск компьютеров с 2-4 процессорами (Intel Core Duo, AMD Athlon64 X2), поэтому оптимизация вычислительного модуля для работы с многопроцессорными системами

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

1. Распараллеливание на уровне координат. Каждый процессор рассчитывает результирующее поле по заданной декартовой координате.

2. Распараллеливание на уровне умножения матрицы на вектор. Каждый процессор работает со своим набором сечений контейнера.

Результаты вычислений показывают, что при увеличении количества процессоров в два раза скорость алгоритма возрастает на 70-90%. Это можно объяснить ростом затрат со стороны операционной системы.

В заключении сформулированы основные результаты диссертационной работы.

Основные результаты работы

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

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

интегральным уравнениям с ядрами, зависящими только от разности аргументов.

• Разработаны эффективные «быстрые» алгоритмы численного решения рассматриваемых задач рассеяния.

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

Список публикаций

1. Будко Н.В., Самохин А.Б., Самохин A.A. Обобщенный метод простой итерации для решения объемных сингулярных интегральных уравнений задач низкочастотного рассеяния./ Дифференциальные уравнения, том 41, №9, с. 1198-1202,2005.

2. Самохин A.A. Подсистема управления довериями в распределённой вычислительной системе./ Труды Международной научной конференции «Идентификация систем и задачи управления», с. 12091213, Москва, 2006.

3. Самохин A.A., Программный комплекс для расчёта электромагнитного поля трёхмерных диэлектрических антенн./ Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова, с. 14-16, Москва, 2006.

4. Самохин A.A. Структура программного комплекса для решения физических задач, описываемых многомерными интегральными уравнениями с ядрами, зависящими от разности аргументов./ Межвуз сб. научных трудов «Процессы и методы обработки информации», с. 92-103, МФТИ, 2006.

5. Самохин А.А., Самохин А.Б., Быстрые алгоритмы для численного решения задач, описываемых многомерными интегральными уравнениями с ядрами, зависящими от разности аргументов. Межвузовский сб. научных трудов./ Теоретические и программные вопросы вычислительной техники, Москва 2006.

Подписано в печать 23.10.2006 Формат 60x90/16 Объём 1,125 пл. Тираж 100 экз. Заказ №23100620

Оттиражировано на ризографе в ООО «УпиверПрнпт» ИННЖПП 7728572912\772801001

Адрес: 117292, г. Москва, ул. Дмитрии Ульянова, д. 8, кор. 2.

Тел. 740-76-47,125-22-73.

ЬИр;/Дутт.ип8уегрНп^гц

13 2 2-8 60

Введение.

Актуальность проблемы.

Цели и задачи исследования.

Методы исследования.

Научная новизна исследований и полученных результатов.

Достоверность научных положений, выводов и практических рекомендаций.

Практическое значение работы.

Во многих фундаментальных и прикладных исследованиях большое значение имеют задачи рассеяния волновых полей различной физической природы на объектах сложной структуры. К таким прикладным областям, в частности, относятся: построение диэлектрических антенн; задачи физики плазмы рассеяние электромагнитных волн на плазменных образованиях; задачи акустики рассеяние звуковых волн на прозрачных телах; задачи квантовомеханического рассеяния на потенциалах. При этом потребности практики диктуют необходимость решения подобных задач в постановке, максимально приближенной к реальной. Это значит, что актуальными становятся задачи рассеяния волновых полей на трехмерных объектах сложной формы и с переменными параметрами. Естественно, что решение подобных задач возможно только с и работы использованием современных численных Целью методов настояш,ей высокопроизводительных компьютеров. является разработка и реализация программной системы для расчета характеристик рассеяния волн различной физической природы на сложных структурах. Долгое время считалось, что наиболее адекватным математическим аппаратом для описания рассматриваемых задач рассеяния являются дифференциальные уравнения. Действительно, на основе дифференциальных постановок задач был получен ряд аналитических решений для простейших рассеивающих объектов. Однако при численном решении, которое необходимо при математическом моделировании реальных задач, дифференциальная постановка приводит к большим вычислительным затратам. Эти затраты обусловлены тем, что искомое решение должно удовлетворять условию излучения на бесконечности. Альтернативной математической постановкой рассматриваемых задач являются интегральные уравнения относительно искомого поля только в области рассеяния. При этом интегральные уравнения после дискретизации сводятся к системам линейных алгебраических уравнений [СЛАУ) значительно меньшей размерности 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 неизвестных

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

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

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

2. Антоневич А.Б., Радыно Я.В. Функциональный анализ и интегральные уравнения. Минск: Университетское, 1984. - 352 с.

3. Ахмед Н., Pao К. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980

4. Балакришнан A.B. Прикладной функциональный анализ. М.: Наука, 1980.-384 с.

5. Бахвалов Н.С. Численные методы. М.: Наука, 1973. - 632 с.

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

7. Беккенбах Э., Беллман Р. Неравенства. М.: Мир, 1965

8. Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983. - 335 с.

9. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. М.: Наука, 1980. - 336 с.

10. Белоцерковский С.М., Лифанов И.К. Численные методы в сингулярных интегральных уравнениях и их применение в аэродинамике, теории упругости, электродинамике. М.: Наука, 1985.-256 с.

11. Боглаев Ю.П. Вычислительная математика и программирование. М.: Высш. шк., 1990. - 544 с.

12. Брусин В.А. Матрицы и системы линейных уравнений // Соросовский Образовательный Журнал. 2000. Т.6, №1. - С. 108-112.

13. Брусин В.А. Матрицы как линейные операторы // Соросовский Образовательный Журнал. 2000. Т.6, №1. - С. 102-107.

14. Бугров Я.С., Никольский С.М. Элементы линейной алгебры и аналитической геометрии. М.: Наука, 1980. - 175 с.

15. Васильева А.Б., Тихонов H.A. Интегральные уравнения. М.: Физматлит, 2002. - 160 с.

16. Ватульян А.О. Измерение расстояний между функциями // Соросовский Образовательный Журнал. 2000. Т.6, №11. - С. 123-127.

17. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977. - 304 с.

18. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.-318 с.

19. Воеводин В.В., Тыртышников Е.Е. Вычислительные процессы с теплицевыми матрицами. М.: Наука, 1987. - 320 с.

20. Волков Е.А. Численные методы. М.: Наука, 1987. - 248 с.

21. Вулих Б.З. Введение в функциональный анализ. М.: Наука, 1967.-416 с.

22. Гантмахер Ф.Р. Теория матриц. 4-е изд. - М.: Наука, 1988. - 552 с.

23. Годунов С.К. Решение систем линейных уравнений. -Новосибирск: Наука, 1980. 177 с.

24. Данфорд Н., Шварц Дж. Линейные операторы: Спектральные операторы. М: Мир, 1974. - 664 с.

25. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Наука, 1970. - 664 с.

26. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения. 3-е изд. - М.: Наука, 1967. - 368 с.

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

28. Дмитриев В.И., Захаров Е.В. Интегральные уравнения в краевых задачах электродинамики. М.:Изд-во МГУ, 1987

29. Довгий С. А., Лифанов И. К. Методы решения интегральных уравнений. Киев: Наукова Думка, 2002, - 344 с.

30. P. Duhamel and М. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," Signal Processing, vol. 19, pp. 259-299, Apr. 1990.

31. Забрейко П.П., Кошелев А.И. и др. Интегральные уравнения. -М.: Наука, 1968

32. А. P. М. Zwanborg, P. М. van den Berg. The three-dimensional weak form of conjugate gradient FFT method for solving scattering problems. IEEE Trans. Microwave Theory Tech., 1992, MTT-40,9: pp. 1757-1765.

33. Икрамов Х.Д. Численные методы линейной алгебры. М.: Знание, 1987. - 47 с.

34. Ильин В.А. Итерационные методы решения функциональных уравнений // Соросовский Образовательный Журнал. 2001. Т.7, №2. -С. 116-120.

35. Ильин В.А., Позняк Э.Г. Линейная алгебра. М.: Наука, 1984. -294 с.

36. Ильинский А.С., Кравцов В.В., Свешников А.Г. Математические модели электродинамики. М.: Высшая школа, 1991

37. Интегральные уравнения / П.П. Забрейко, А.И. Кошелев, М.А. Красносельский и др. М.: Наука, 1968. - 448 с.

38. Канторович Л. В., Акилов Г. П. Функциональный анализ М.: Наука, 1977

39. Калиткин Н.Н. Численные методы. М.: Наука, 1978. - 512 с.

40. Кнут Д. Э. Искусство программирования. М.: Вильяме, 2002. -712 с.

41. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. М.: Наука, 1972. - 368 с.

42. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1984. - 831 с.

43. Колтон Д., Кресс Р. Методы интегральных уравнений в теоории рассеяния. М.: Мир, 1987. - 317 с.

44. Краснов М.Л., Киселёв А.И., Макаренко Г.И. Интегральные уравнения М.: Наука, 1968. - 192 с.

45. Крылов В.И., Бобков В.В., Монастырный П.Н. Вычислительные методы. Т.1. М.: Наука, 1976. - 302 с.

46. Курант Р., Гильберт Д. Методы математической физики. Т.1. 3-е изд. - М.-Л.: Гостехиздат, 1951. - 476 с.

47. Купрадзе В. Д. Граничные задачи теории колебаний и интегральные уравнения. М.; Л., 1950

48. Лизоркин П.И. Курс дифференциальных и интегральных уравнений с дополнительными главами анализа. М.: Наука, 1981. -384 с.

49. Люстерник Л.А., Соболев В.И. Краткий курс функционального анализа. М: Высш. шк., 1982. - 272 с.

50. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. 2-е изд. - М.: Наука, 1965. - 520 с.

51. Нечепуренко Ю. М. Быстрые численно устойчивые алгоритмы для широкого класса линейных дискретных преобразований. М.: 1985. Препринт ОВМ АН СССР №98.

52. Максимов В.П. Арифметика рациональных чисел и компьютерное исследование интегральных уравнений // Соросовский Образовательный Журнал. 1999. №3. - С. 121-126.

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

54. Matteo Frigo and Steven G. Johnson, FFTW: an adaptive Software architecture for the FFT, MIT Laboratory for Computer Science, 1998

55. Вычислительные методы в электродинамике. / Под ред. P.M. Митры.: М.: Мир, 1977

56. Михлин С.Г. Лекции по линейным интегральным уравнениям. -М.: Физматгиз, 1959. 232 с.

57. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М.: Наука, 1986. - 288 с.

58. Петровский И.Г. Лекции по теории интегральных уравнений. -3-е изд. М.: Наука, 1965. - 128 с.

59. Полянин А.Д., Манжиров A.B. Справочник по интегральным уравнениям. М.: Физматлит, 2003. - 608 с.

60. Приближенное решение операторных уравнений / М.А. Красносельский, Г.М. Вайникко, П.П. Забрейко и др. М.: Наука, 1969. -456 с.

61. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978. - 848 с.

62. Райе Дж. Матричные вычисления и математическое обеспечение. М.: Мир, 1984. - 264 с.

63. Brent Rector, Introducing Longhorn for Developers, Microsoft Press, 2004

64. Jeffrey Richter, Applied Microsoft .NET Framework Programming, Microsoft Press, 2002

65. Романовский И. В., Дискретный Анализ. М.: Физматлит, 2001

66. Самарский A.A. Введение в численные методы. М.: Наука, 1982. - 272 с.

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

68. Самарский А. А., Николаев Е. С. Методы решения сеточных уравнений. М.: Наука, 1978 - 589 с.

69. Самохин А.Б. Интегральные уравнения и итерационные методы в электромагнитном рассеянии. М.: Радио и связь, 1998. - 160 с.

70. Самохин А.Б. Итерационный метод для интегральных уравнений задач рассеяния на трехмерном прозрачном теле // Дифференциальные уравнения. 1994. Т.ЗО, №12. - С. 2162-2174.

71. Самохин А.Б. Метод простой итерации для решения линейных операторных уравнений // Журнал Выч. мат и мат. физ. 1988. Т.28, №10.-С. 1573-1583.

72. Самохин А.Б. Многошаговый метод минимальных невязок для решения линейных уравнений // Журнал Выч. мат и мат. физ. 1991. Т.31,№2.-С. 317-320.

73. Самохин А.Б. Численные методы решения многомерных интегральных уравнений математической физики с ядрами, зависящими от разности аргументов/ Радиотехника и электроника. 2005, т.50, №2, с. 208-212.

74. Samokhin А.В. Integral equations and iteration methods in electromagnetic scattering, Utrecht: VSP, The Netherlands, 2001.

75. Chris Sells, Ian Griffiths, Windows Presentation Foundation, O'Reilly Media, 2005

76. Тихонов A.H., Костомаров Д.П. Вводные лекции по прикладной математике. М.: Наука, 1984. - 190 с.

77. Троелсен Э. С# и платформа .NET. Санкт Петербург: Питер, 2002 795 с.

78. Тьюарсон Р. Разреженные матрицы. М.: Мир, 1977. - 189 с.

79. Тыртышников Е. Е. Методы быстрого умножения и решение уравнений // Матричные методы и вычисления М.: ИВМ РАН, 1999. с. 4-41

80. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. 3-е изд. - СПб.: Лань, 2002. - 736 с.

81. Будко Н.В., Самохин А.Б., Самохин A.A. Обобщенный метод простой итерации для решения объемных сингулярных интегральных уравнений задач низкочастотного рассеяния./ Дифференциальные уравнения, том 41, №9, с. 1198-1202,2005.

82. Самохин A.A., Структура программного комплекса для решения физических задач, описываемых многомерными интегральными уравнениями с ядрами, зависящими от разности аргументов / Межвуз сб. научных трудов, Процессы и методы обработки информации, МФТИ 2006

83. Самохин A.A. Подсистема управления довериями в распределённой вычислительной системе./ Труды Международной научной конференции «Идентификация систем и задачи управления», с. 1209-1213, Москва, 2006.

84. Самохин A.A., Программный комплекс для расчёта электромагнитного поля трёхмерных диэлектрических антенн / Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова. Москва 2006.