close

Вход

Забыли?

вход по аккаунту

?

Анализ полосковых структур методом моментов

код для вставкиСкачать
На правах рукописи
Ахунов Роман Раисович
Анализ полосковых структур методом моментов
Специальность 05.12.04 –
радиотехника, в том числе системы и устройства телевидения
Автореферат диссертации на соискание учёной степени
кандидата технических наук
Томск–2016
2
Работа выполнена в федеральном государственном бюджетном
образовательном учреждении высшего профессионального образования
«Томский
государственный
университет
систем
управления
и
радиоэлектроники» (ТУСУР)
Научный руководитель:
Газизов Тальгат Рашитович
доктор технических наук, старший
научный сотрудник, ТУСУР, г. Томск.
Официальные оппоненты:
Дмитренко Анатолий Григорьевич,
доктор физико-математических наук,
профессор, федеральное государственное
автономное образовательное учреждение
высшего образования «Национальный
исследовательский Томский
государственный университет», г. Томск;
Майстренко Василий Андреевич,
доктор технических наук, профессор,
федеральное государственное бюджетное
образовательное учреждение высшего
профессионального образования «Омский
государственный технический
университет», г. Омск.
Ведущая организация:
Акционерное общество «Научнопроизводственный центр «Полюс»,
г. Томск.
Защита состоится 29 марта 2016 г. в 9 часов 00 минут на заседании
диссертационного совета Д 212.268.01 при Томском государственном
университете систем управления и радиоэлектроники по адресу: 634050,
г. Томск, пр. Ленина, 40.
С
диссертацией
можно
ознакомиться
на
сайте
http://www.tusur.ru/ru/science/education/dissertations/ и в библиотеке Томского
государственного университета систем управления и радиоэлектроники по
адресу: 634045, г. Томск, ул. Красноармейская, 146.
Автореферат разослан «___» февраля 2016 г.
Ученый секретарь
диссертационного совета Д 212.268.01
доктор физико-математических наук
Мандель А.Е.
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы
Невыполнение требований электромагнитной совместимости (ЭМС) может иметь серьезные последствия в различных сферах деятельности человека:
из-за сбоев в радиоэлектронной аппаратуре (РЭА) воздушного и железнодорожного транспорта, автоматических производственных линий и объектов
энергетики, медицинского оборудования жизнеобеспечения и т.д. Исследованиям ЭМС РЭА посвящены работы известных школ, которыми руководят
Л.Н. Кечиев, В.Ю. Кириллов, С.А. Сухоруков, В.Е. Фортов, С.Ф. Чермошенцев, J.L. ter Haseborg, F. Rachidi, W. Radasky, E. Schamiloglu, S. Tkachenko, и
др.
Необходимость обеспечения ЭМС РЭА вынуждает разработчиков проводить длительные дорогостоящие испытания. Поэтому целесообразен учет
ЭМС на этапе проектирования РЭА посредством имитационного моделирования с помощью схемотехнического, квазистатического и электродинамического подходов. При предварительном моделировании, часто выполняемом в
широком диапазоне изменения параметров, актуально уменьшение вычислительных затрат. Большая их часть приходится на решение системы линейных
алгебраических уравнений (СЛАУ). В развитие методов решения СЛАУ, как
прямых, так и итерационных, внесли вклад отечественные и зарубежные ученые: В.В. Воеводин, С.К. Годунов, Х.Д. Икрамов, В.П. Ильин, Л.Ю. Колотилина, Г.И. Марчук, В.В. Радченко, А.А. Самарский, Е.Е. Тыртышников,
M. Bebendorf, S. Borm, C. Calgaro, J. Dongarra, D. Golub, W. Hack-busch,
S. Karimi, Q. He, S. Rjasanow, Y. Saad, T. Topa, I. Tsukerman, H. Van der Vorst и
др.
Между тем ряд задач по уменьшению вычислительных затрат остается
нерешенным. Так, известно, что использование полосковых структур позволяет разрабатывать более совершенную РЭА, а анализ связей в них важен для
разработки РЭА с учетом ЭМС. При этом для моделирования полосковых
структур широко используют квазистатический анализ на основе вычисления
электрической ёмкости методом моментов, которое предложили R. Harrington,
T. Sarkar, A. Djordjevic. Это вычисление предусматривает решение СЛАУ.
Примечательно, что специфика самого решения, а также изменений матрицы
СЛАУ при многовариантом анализе, могут быть использованы для его совершенствования, например, за счет итерационных методов.
Цель работы – усовершенствовать анализ полосковых структур методом
моментов за счет использования итерационных методов решения СЛАУ.
Для достижения цели необходимо решить следующие задачи:
1. Выполнить анализ современного состояния проблемы моделирования
ЭМС методом моментов, а также методов решения СЛАУ.
2. Усовершенствовать одновариантный анализ полосковых структур за
счет использования форматов хранения разреженных матриц.
3. Усовершенствовать многовариантный анализ полосковых структур за
счет учета специфики итерационного решения СЛАУ.
4
Научная новизна
1. Разработаны алгоритмы ILU(0)-разложения, отличающиеся учетом
особенностей разреженного строчного формата хранения разреженных матриц
для анализа полосковых структур методом моментов.
2. Исследован процесс решения СЛАУ итерационным методом с предобусловливанием, использующим новые алгоритмы ILU(0)-разложения, при одновариантном анализе полосковых структур методом моментов.
3. Исследовано многократное решение СЛАУ итерационным методом с
предобусловливанием и выбором вектора решения предыдущей СЛАУ в качестве начального приближения текущей при анализе полосковых структур методом моментов.
4. Разработаны алгоритмы многократного решения СЛАУ итерационным методом для анализа полосковых структур, отличающиеся адаптивным
переформированием предобусловливателя на основании оценок средних
арифметических значений времени и сложности.
5. Впервые исследован процесс многократного решения СЛАУ, полученных методом моментов при анализе полосковых структур, итерационным методом с адаптивным переформированием предобусловливателя.
6. Установлено, что время многократного решения СЛАУ итерационным
методом с предобусловливанием при многовариантном анализе полосковой
структуры методом моментов может зависеть от выбора очередности решения
СЛАУ и выбора матрицы предобусловливания, что можно использовать для
ускорения анализа электромагнитной совместимости.
Теоретическая значимость
1. Получены оценки максимального значения коэффициента сжатия
форматов хранения разреженных матриц.
2. Получены аналитические оценки максимально возможного ускорения
многократного
решения
СЛАУ
итерационным
методом
с
предобусловливанием относительно метода исключения Гаусса.
3. Получены формулы для аналитической оценки усредненного
ускорения многократного решения СЛАУ итерационным методом с
предобусловливанием относительно прямого метода.
4. Сформулирована и доказана теорема о существовании минимума
среднеарифметического времени решения ряда СЛАУ при анализе полосковых
структур методом моментов.
5. Получены формулы для оценки арифметической сложности LUразложения, стабилизированного метода бисопряженных градиентов и
квадратичного метода сопряженных градиентов с учетом программной
реализации.
5
Практическая значимость
1. Показана перспективность использования итерационных методов с
предобусловливанием для решения СЛАУ при многовариантном анализе
полосковых структур методом моментов.
2. Программно реализованы усовершенствованные алгоритмы ILU(0)разложения и многократного решения СЛАУ итерационными методами с
адаптивным переформированием предобусловливателя.
3. Показано, что реализованные алгоритмы позволяют уменьшить
вычислительные затраты на анализ ЭМС методом моментов.
4. Получены оценки арифметической сложности алгоритмов LUразложения, стабилизированного метода бисопряженных градиентов и
квадратичного метода сопряженных градиентов с учетом программной
реализации.
5. Полученные оценки возможного ускорения многократного решения
СЛАУ итерационным методом с предобусловливанием относительно прямого
метода позволяют априорно выбрать наиболее подходящий метод.
6. Усовершенствован учебный процесс ТУСУР.
Методология и методы исследования
В работе применено компьютерное моделирование, квазистатический
подход, метод моментов, LU-разложение, метод Гаусса, ILU(0)-разложение,
стабилизированный метод бисопряженных градиентов, квадратичный метод
сопряженных градиентов.
Положения, выносимые на защиту
1. При одновариантном анализе полосковых структур методом моментов
использование разреженного строчного формата хранения разреженных матриц позволяет уменьшить не только затраты оперативной памяти, но и время
решения СЛАУ итерационным методом с неявным предобусловливанием.
2. Выбор вектора решения предыдущей СЛАУ в качестве начального
приближения текущей при многократном решении СЛАУ итерационным методом с предобусловливанием позволяет ускорить анализ полосковых структур методом моментов.
3. При многовариантном анализе полосковых структур методом моментов использование адаптивных условий переформирования предобусловливателя позволяет ускорить решение 100 СЛАУ квадратичным методом сопряженных градиентов до 1,57 раза, а стабилизированным методом бисопряженных градиентов до 1,6 раза.
4. Выбор очередности решения СЛАУ итерационным методом с предобусловливанием позволяет ускорить многовариантный анализ полосковых
структур методом моментов.
5. При многовариантном анализе полосковых структур методом моментов выбор 50-й матрицы для формирования предобусловливателя позволяет
ускорить решение 100 СЛАУ стабилизированным методом бисопряженных
градиентов до 2,21 раза.
6
Достоверность результатов подтверждена использованием проверенных
алгоритмов и численных методов, согласованностью результатов теоретических оценок и вычислительного эксперимента, а также использованием результатов на практике.
Использование результатов
1. ОКР «Разработка комплекса программных и технических средств для
контроля информационных магистралей, обеспечения электромагнитной совместимости и исследования надёжности унифицированного ряда электронных
модулей на основе технологии «система-на-кристалле» для систем управления
и электропитания космических аппаратов связи, навигации и дистанционного
зондирования Земли с длительным сроком активного существования», тема
«УЭМ-ТУСУР», хоздоговор 95/10 от 24.11.2010 в рамках реализации Постановления 218 Правительства РФ, 2010–2012 гг.
2. ОКР «Разработка принципов построения и элементов системы автономной навигации с применением отечественной специализированной элементной базы на основе наногетероструктурной технологии для космических
аппаратов всех типов орбит», тема «САН», хоздоговор 96/12 от 16.11.2012 в
рамках реализации Постановления 218 Правительства РФ, 2013–2015 гг.
3. НИР «Выявление, исследование и реализация новых возможностей
уменьшения времени многократного решения СЛАУ с частично изменяющейся матрицей в задачах вычисления емкостной матрицы произвольной системы проводников и диэлектриков», грант РФФИ 14-07-31267 мол_а, 2014–
2015 гг.
4. НИР «Комплексные исследования по разработке алгоритмов, математического обеспечения и средств проектирования для создания новых элементов защиты и контроля вычислительных систем на основе модальных явлений», грант РФФИ 14-29-09254, 2014–2016 гг.
5. НИР «Комплексное обоснование возможностей создания модальной
технологии помехозащиты критичной радиоэлектронной аппаратуры и совершенствования существующих и разработки новых помехозащитных устройств
на её основе», грант РНФ 14-19-01232, 2014–2016 гг.
6. НИР «Разработка новых программных и аппаратных средств для моделирования и обеспечения электромагнитной совместимости радиоэлектронной аппаратуры» в рамках проектной части государственного задания в сфере
научной деятельности 8.1802.2014/K, 2014–2016 гг.
Апробация результатов
Подготовка заявок и победа в конкурсах: темы «УЭМ-ТУСУР» и «САН»
по Постановлению 218 Правительства РФ; грант РФФИ 14-07-31267 мол_а;
грант РФФИ 14-29-09254; грант РНФ 14-19-01232; проектная часть госзадания
8.1802.2014/К.
Результаты представлялись в материалах следующих конференций: Всеросс. научно-техн. конф. студентов, аспирантов и молодых ученых «Научная
сессия ТУСУР-2010», г. Томск, 2010 г.; Межд. симп. по электромагнитной совместимости и электромагнитной экологии, г. Санкт-Петербург, 2011 г.; Межд.
7
конф. по численному электромагнитному моделированию и оптимизации для
ВЧ, СВЧ и терагерцовых приложений, Италия, 2014 г.; Межд. конф. «Актуальные проблемы вычислительной и прикладной математики 2015», г. Новосибирск, 2015 г.; Межд. конф. по прикладной физике, моделированию и компьютерам, Австрия, 2015 г.; Межд. конф. по численному анализу и прикладной
математике, Греция, 2015 г.; Межд. конф. по моделированию и прикладной
математике, Таиланд, 2015 г.; Межд. научно-практ. конф. «Электронные средства и системы управления», г. Томск, 2015 г.
Публикации. 31 работа, в т.ч. 1 монография, 1 статья в зарубежном журнале, 8 статей в журналах из перечня ВАК, 1 статья в рецензируемом журнале,
4 доклада в трудах зарубежных конференций, 3 – в отечественных, 13 свидетельств о регистрации программы для ЭВМ (приведены в диссертации).
Структура и объём диссертации. В состав диссертации входят введение,
3 главы, заключение, список литературы из 145 наим., приложения на 28 с., в
т.ч. 3 табл. Объём диссертации без приложений – 144 с., в т.ч. 50 рис. и 18 табл.
Личный вклад. Все результаты работы получены автором лично или при
непосредственном его участии. Разработка исходных кодов программ, получение аналитических оценок и обработка результатов выполнены лично автором. Разработка алгоритмов, их исследование, анализ и обобщение полученных результатов выполнены совместно с С.П. Куксенко. Часть результатов получена совместно с соавторами публикаций.
Краткое содержание работы. Во введении представлена краткая характеристика работы. В гл. 1 выполнен обзор актуальных задач. В гл. 2 проведен
сравнительный анализ наиболее распространённых форматов хранения разреженных матриц, разработаны алгоритмы ILU(0)-разложения с применением
разреженного строчного формата (CSR), проведен вычислительный эксперимент, подтверждающий эффективность его использования. В гл. 3 представлены алгоритмы многократного решения СЛАУ с изменяющейся матрицей
итерационными методами с предобусловливанием и результаты вычислительных экспериментов. Далее приведен список литературы. В заключении подведены итоги работы. В Приложении А приведены расчеты сложности алгоритмов LU-разложения, стабилизированного метода бисопряженных градиентов
и квадратичного метода сопряженных градиентов. В Приложении Б представлены копии свидетельств о регистрации программы для ЭВМ, а в Приложении В – актов использования результатов работы.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении приведена общая характеристика работы.
1 ОБЗОР СОСТОЯНИЯ ПРОБЛЕМЫ
Представлено обоснование актуальности предварительного имитационного моделирования ЭМС. Приведен порядок расчета ёмкостной матрицы методом моментов для произвольной двумерной структуры. Также сделан краткий обзор методов решения СЛАУ. Рассмотрены форматы хранения разреженных матриц и существующие варианты многократного решения СЛАУ. Сформулированы цель и задачи работы.
8
2 ОДНОВАРИАНТНЫЙ АНАЛИЗ ПОЛОСКОВЫХ СТРУКТУР
С ИСПОЛЬЗОВАНИЕМ ФОРМАТОВ ХРАНЕНИЯ
РАЗРЕЖЕННЫХ МАТРИЦ
Представлены результаты анализа эффективности сжатия для различных форматов хранения разреженных матриц. Приведены аналитические
оценки границы эффективности и максимального коэффициента сжатия форматов двух векторов, Кнута, Рейнболдта и Местеньи, Ларкума, Шермана, CSR,
JDS и CDS. Показано что максимальный коэффициент сжатия, который равен
1/(2q), где q – плотность матрицы, рассчитанная как отношение числа ненулевых элементов матрицы к N2, обеспечивают форматы двух векторов, CSR и
JDS. Однако, при выборе формата хранения необходимо учитывать не только
эффективность сжатия формата, но и его применимость в алгоритмах. Поэтому для дальнейшего использования выбран формат CSR, т.к. он наиболее
удобен для многих важных операций над разреженными матрицами, таких как
сложение, умножение, перестановка строк и столбцов, транспонирование, решение СЛАУ с разреженными матрицами, как прямыми, так и итерационными
методами и т.д. Для каждого формата рассмотрена граница эффективности,
т.е. значение q, выше которого сжатие не происходит. Она оценена аналитически (раздел 2.1 диссертации). Таким образом, установлено, что использование
формата CSR обеспечит экономию оперативной памяти компьютера при
q<50% для всех исследуемых далее матриц.
Рассмотрено ускорение решения СЛАУ с плотной матрицей итерационными методами с неявным предобусловливанием, которое преобразует исходную систему Ax = b к виду MAx = Mb, где матрица M формируется с помощью ILU(0)-разложения. Для реализации ILU(0)-разложения выбран алгоритм
ikj-версии, где элементы матриц L и U вычисляются по строкам и поэтому возможно использование цикла по ненулевым элементам в формате CSR. Тогда
вычисления будут выполняться только с элементами строк i и k, у которых
равны индексы столбцов. В результате разработан алгоритм ILU(0)-разложения с использованием формата CSR. Анализ показал, что поиск диагонального
элемента в алгоритме существенно увеличивает время его работы, поэтому целесообразно ввести в формат хранения дополнительный вектор Diag, в котором будут храниться указатели на диагональные элементы.
Оценка временных затрат сделана для трёх СЛАУ (порядка N=4800,
6000, 8000), матрицы которых получены в системе TALGAT последовательным учащением сегментации границ проводник-диэлектрик и диэлектрик-диэлектрик из задачи вычисления электрической ёмкости двух полосок на диэлектрическом слое над идеально проводящей плоскостью (рисунок 2.1а). При
помощи предфильтрации менялась плотность матрицы M. Итерации продолжались, пока относительная норма вектора невязки не становилась меньше
10–6. Сравнение проводилось для двух вариантов алгоритма BiCGStab: без использования формата хранения разреженных матриц (T) и с использованием
формата CSR с дополнительным вектором Diag (Tcsrd). В таблице 2.1 приведены данные сравнения этих алгоритмов.
9
Следующим усовершенствованием было исключение поиска ненулевых
элементов в алгоритме, а последним – использование временных векторов.
Оценка ускорения выполнена для конфигураций из рисунка 2.1. Использовано
отношение времени решения СЛАУ по усовершенствованным алгоритмам
(без поиска ненулевых элементов (Ts) и с использованием временных векторов
(Tr)) ко времени алгоритма без этих усовершенствований (T). Полученные зависимости ускорения решения СЛАУ от плотности (q) матрицы M для
N = 4800 приведены на рисунке 2.2а. Видно, что ускорение достигает 2,5 раза,
но при малых q ускорение падает. Этот факт объясняется тем, что в данной
работе оптимизировался только этап ILU(0)-разложения, т.е. одна из трех составляющих общего времени: предфильтрации (Tp), ILU(0)-разложения (Tlu)
и итерационного процесса (Ti). На рисунке 2.2б приведено ускорение ILU(0)разложения для N = 4800 при использовании алгоритмов: без поисков ненулевых элементов (Tlus) и с использованием временных векторов (Tlur) относительно алгоритма без этих усовершенствований (Tlu). Видно, что ускорение
увеличивается с уменьшением q и нет тенденции к отсутствию ускорения при
минимальной плотности матрицы, как это было на рисунке 2.2а.
а
б
Рисунок 2.1 – Поперечные сечения исследуемых структур: два проводника с диэлектриком (а) и без диэлектрика (б) над идеально проводящей плоскостью
3
4
Ускорение
Таблица 2.1 – Сравнение времени решения СЛАУ разными
алгоритмами при разных N
N
T, с Tcsrd, с T/Tcsrd
4800 164
101
1,6
6000 335
206
1,6
8000 216
140
1,5
Ускорение
3
2
2
1
T/Ts
T/Tr
1
q, %
а
Tlu/Tlus
Tlu/Tlur
q, %
б
а
Рисунок 2.2 – Ускорение решения СЛАУ (а) и ILU(0)-разложения (б) для рисунка 2.1а
0
100 66 58 54 50 46 44 41 40 38
0
100 66 58 54 50 46 44 41 40 38
Для наглядности зависимость соотношения времени этапов решения
СЛАУ от q для N = 4800 изображена на рисунке 2.3. Из рисунка 2.3 видно, что
при уменьшении плотности матрицы часть времени, затрачиваемая на итерационный процесс, увеличивается, а на ILU(0)-разложение (за счет которого
получено ускорение) – уменьшается, что, в конечном счете, уменьшает ускорение решения СЛАУ. Между тем, уменьшение ускорения при малой плотности матрицы не уменьшает значимости усовершенствования алгоритма. Действительно, на практике требуется минимизировать время решения СЛАУ за
счет выбора оптимального значения допуска обнуления. При этом значение
времени ILU(0)-разложения примерно равно времени итерационного процесса. Поэтому уменьшение времени вычисления ILU(0)-разложения весьма
важно.
10
Алгоритм с использованием формата CSR с предложенными усовершен90
ствованиями позволил ускорить реше80
ние СЛАУ итерационным методом
70
BiCGStab до 1,6 раза по сравнению с ал60
горитмом без использования формата
CSR. Алгоритм, использующий два до50
Итерационный процесс
полнительных вектора, показал допол40
нительное ускорение до 1,7 относиILU(0)-разложение
30
тельно алгоритма без дополнительных
предфильтрация
20
векторов. Таким образом, при одновари10
антном анализе полосковых структур
q, %
методом моментов использование раз0
100 66 58 54 50 46 44 41 40 38 реженного строчного формата позвоРисунок 2.3 – Зависимость соотношения ляет уменьшить не только затраты
времени этапов решения СЛАУ итераци- оперативной памяти, но и время решеонным методом с предобусловливанием ния СЛАУ итерационным методом с неот плотности матрицы M для N = 4800
явным предобусловливанием.
3 МНОГОВАРИАНТНЫЙ АНАЛИЗ ПОЛОСКОВЫХ СТРУКТУР
С УЧЕТОМ СПЕЦИФИКИ ИТЕРАЦИОННОГО РЕШЕНИЯ СЛАУ
В главе представлены результаты использования итерационного метода
для многократного решения СЛАУ с изменяющийся матрицей.
Предположим, что время решения отдельных СЛАУ существенно не меняется и, в среднем, равно TA. Оценим возможное ускорение от применения
итерационного метода. Если представить его отношением (β) общего времени
решения m СЛАУ прямым методом (TD) ко времени решения итерационным
методом с предобусловливанием, то для максимального ускорения получим
100
Соотношение, %
βAmax  lim 
m 
m  TD
 TPR  m  TA
 TD
 
 TA
,
(3.1)
где TPR – время формирования матрицы предобусловливания.
Из этого вытекают важные следствия:
Следствие 1. Чем больше число решаемых СЛАУ, тем меньше ускорение зависит от времени построения предобусловливателя, а значит, от выбора вида предобусловливания, способа предфильтрации и оптимального значения допуска обнуления.
Следствие 2. Поскольку максимальное усредненное ускорение обратно
пропорционально среднему времени итерационного процесса, то актуально
уменьшение времени одной итерации и числа итераций.
Еще одним параметром, влияющим на время итерационного процесса,
является начальное приближение. Чем оно ближе к решению системы, тем
меньше итераций потребуется итерационному методу для его уточнения. Пример зависимости изменения значения диагонального элемента матрицы СЛАУ
11
w
t
εr
h
Рисунок 3.1 – Поперечное сечение микрополосковой линии
12
(Δa) от её номера (k) для рисунка 3.1 приведен
на рисунке 3.2. Видно, что скорость изменения Δa с увеличением k становится меньше, а
значение не превышает 12%. Таким образом,
для данной задачи целесообразно использовать вектор решения предыдущей СЛАУ в качестве начального приближения текущей.
1000
Δa, %
Nit
10
8
100
6
4
10
2
Вариант 1
Вариант 2
Вариант 3
Вариант 4
k
0
1
20
40
60
80 100
1
k
1
10 20 30 40 50 60 70 80 90 100
Рисунок 3.2 – Пример зависимости изменения элемента Рисунок 3.3 – Число итераций при решении k-й СЛАУ
методом BiCGStab в зависимости от k для вариантов 1–4
матрицы от её номера
Для подтверждения эффективности способов ускорения использованы
следующие варианты вычислений. В исходном варианте 1 ускорение не использовано. В варианте 2 использован в качестве начального приближения
вектор решения предыдущей СЛАУ. В варианте 3 используется матрица
предобусловливания, сформированная из матрицы первой СЛАУ. В варианте 4 – способы ускорения использованы совместно. На рисунке 3.3 приведено изменение числа итераций (Nit) с ростом k при изменении h на рисунке 3.1
для каждого из вариантов. Отношения общего времени решения методом
Гаусса ко времени решения итерационным методом для 100 СЛАУ при изменении h, w, t на рисунке 3.1 приведены в таблице 3.1. Из неё видно, что лучшие
результаты показал вариант 4 с совместным использованием двух способов
ускорения, а вариант 1 показал замедление решения. Для варианта 4 при изменении t ускорение меньше, чем при изменении h и w. Это объясняется увеличенным числом итераций из-за боТаблица 3.1 – Ускорение решения 100 СЛАУ
лее выраженных изменений элеВариант
Изменяемый
ментов в матрице. При этом примепараметр
1
2
3
4
няемые способы ускорения недоh
0,48 1,32 6,49 11,77
статочно эффективны.
w
0,31 1,15 5,87 10,98
Анализ полученных данных
t
0,37 1,28 2,87 4,92
позволяет сделать несколько выводов. В варианте 1 количество итераций велико и в среднем постоянно, поскольку не используются способы ускорения решения. В варианте 2, использующем в качестве начального приближения вектор решения предыдущей
СЛАУ, наблюдается небольшое и постепенное уменьшение количества итераций и, следовательно, времени решения СЛАУ. В варианте 3 используется
матрица предобусловливания, сформированная из матрицы первой СЛАУ.
12
При решении первой СЛАУ количество итераций равно 1, а при решении последующих СЛАУ оно растет из-за изменений в матрице. В варианте 4 количество итераций минимально, что, соответственно, приводит к снижению общего времени решения всех СЛАУ и доказывает эффективность совместного
использования способов ускорения.
Из этого следует, что для вектора начального приближения целесообразно использовать вектор решения предыдущей СЛАУ. Далее более детально
сравнивались два варианта выбора начального приближения: фиксированное
(все элементы вектора равны некоторому значению, в данном случае, единице), используемое для решения каждой СЛАУ; вектор решения предыдущей
СЛАУ. Проведены вычисления с целью оценки ускорения решения итерационным методом относительно метода Гаусса. В качестве исследуемой использована структура (рисунок 2.1а), полученная в системе TALGAT. Посредством изменения сегментации границ проводников и диэлектрика получены
СЛАУ с N = 708, 1416, 3540, 4425. В качестве итерационного метода использовался BiCGStab. Ускорения решения m СЛАУ сведены в таблицу 3.2.
m
1
5
10
100
1000
∞
Таблица 3.2 – Ускорение (относительно метода Гаусса) решения
итерационным методом BiCGStab m СЛАУ
Фиксированное начальное
Начальное приближение равно вектору
приближение
решения предыдущей СЛАУ
N = 708 N = 1416 N = 3540 N = 4425 N = 708 N = 1416 N = 3540 N = 4425
0,36
0,51
0,52
0,31
0,36
0,51
0,52
0,31
1,37
2,15
2,43
1,52
1,53
2,27
2,49
1,53
2,12
3,65
4,53
2,93
2,52
4,00
4,74
2,98
4,12
9,58
20,53
18,09
5,70
12,74
24,82
20,42
4,55
11,43
31,71
37,36
6,59
16,32
43,09
49,3
4,61
11,69
33,78
42,43
6,71
16,86
46,96
58,59
С ростом m ускорение растет, достигая 49 при m = 1000 и N = 4425. В
последней строке таблицы 3.2 приведены значения, полученные по (3.1).
Видно, что к ним сходятся значения предыдущих строк, что подтверждает возможность аналитических оценок ускорений по (3.1) без вычислительного эксперимента. Также видно, что начальное приближение, равное вектору решения предыдущей СЛАУ, дает большее ускорение, чем фиксированное (в 1,4
раза при N = 4425).
Таким образом, выбор начального приближения, равного вектору решения предыдущей СЛАУ при многократном решении СЛАУ итерационным методом с предобусловливанием позволяет ускорить анализ полосковых структур методом моментов: на рассмотренных примерах до 1,4 раза.
Далее рассмотрены различные условия переформирования предобусловливателя, позволяющего дополнительно ускорить многократное решение
СЛАУ с изменяющейся матрицей итерационным методом. На примере многовариантного анализа связанной и одиночной микрополосковых линий (раздел
3.1.2 диссертации) показано, что эффективность многократного решения
СЛАУ итерационным методом снижается, если увеличивается разница между
13
первой и текущей матрицами СЛАУ. Это ведет к росту числа итераций и замедляет решение итерационным методом. В обзоре упоминалось о неэффективности корректировки предобусловливателя при неявном предобусловливании, поэтому такой подход далее не исследовался. Вместо корректировки,
предложено переформировывать матрицу М для получения ускорения, когда
при решении текущей СЛАУ нет быстрой сходимости метода.
Первоначально предложено использовать переформирование, когда текущее число итераций Nit становится выше заданного порога NitMAX. На примере многовариантного анализа одиночной микрополосковой линии, при изменении t на рисунке 3.1, показано (раздел 3.2.2 диссертации), что существует
оптимум, при котором достигается максимальное ускорение. На рисунке 3.4
приведены изменения числа итераций при минимальном (NitMAX = 2) и максимальном (NitMAX = 13) значениях
13 Nitk
12
NitMAX
порога. При минимальном зна11
2
чении порога происходит много
10
13
9
переформирований,
которые
8
увеличивают общее время реше7
6
ния, поскольку время одного пе5
реформирования значительно.
4
3
При максимальном значении
2
порога, переформирований нет,
1
k
0
и общие затраты времени опре1
10 20 30 40 50 60 70 80 90 100
деляются затратами на итераРисунок 3.4 – Зависимости числа итераций
ции. Однако у данного подхода
при решении k-й СЛАУ от k
есть недостаток, который не
позволяет широко использовать его на практике: определить значение оптимального порога до начала решения не представляется возможным.
Эффективность итерационного метода при многократном решении
СЛАУ определяется суммарным временем решения всех СЛАУ ( T ):
m
T  TPR   Tk ,
(3.2)
k 1
где TPR – время формирования матрицы предобусловливания М из матрицы
первой СЛАУ, Tk – время решения k-й СЛАУ, m – количество СЛАУ.
Используя (3.2), рассмотрим изменение среднего арифметического времени решения k СЛАУ:
__
k
T (k ) 1 

T (k )     TPR   T j  .
k
k
j 1

k
Для удобства введем дополнительную величину sk  kTk 1   T j .
j 1
Теорема 1. Если sk монотонно возрастает при k = 1, 2, …, k* , … и выполнены условия s1 < TPR и sk  < TPR≤ sk  +1 для некоторого k* ≥ 1, то для этого
__
k* достигается единственный минимум функции T (k ) .
14
Теорема 2. Если при k = 1, 2, … выполняются условия Tk = t и t < TPR, то
__
функция T ( k ) убывает и стремится к t.
Условия, указанные в теореме 1, выполняются при многократном решении СЛАУ. Т.е. для монотонного увеличения sk достаточно увеличения времени решения k-й СЛАУ (Tk). Как правило, решение первой СЛАУ происходит
значительно быстрее, чем время формирования матрицы предобусловливателя, т.е. выполняется условие s1 < TPR. Из этого следует, что при многократном решении СЛАУ будет существовать единственный минимум функции
__
T ( k ) , а это позволяет использовать его как условие для переформирования
предобусловливателя. Для подтверждения сделанного предположения выполнен простой эксперимент по вычислению ёмкости проводника на диэлектрической подложке над идеально проводящей плоскостью (рисунок 3.5а). Зави__
симости Tk и T ( k ) приведены на рисунке 3.6, из которого видно наличие минимума в поведении среднего арифметического значения (при k = 52), что подтверждает сделанное предположение.
1
2
t
s
1
а
3
1
4
2
s
б
4
s
2
3
6
s
5
в
Рисунок 3.5 – Вид поперечного сечения исследуемых структур: 1 – проводник (1) на диэлектрической подложке (2) над идеально проводящей плоскостью (а); 2 – симметричный модальный фильтр с лицевой связью (1–3 –проводники, 4 – диэлектрик) (б);
3 – зеркальный симметричный модальный фильтр (1–5 –проводники, 6 – диэлектрик) (в)
При использовании среднего арифметического времени решения трудно
500
точно измерить время. Поэтому предло400
жено перейти от измерения времени к рас300
Tk
чету сложности алгоритмов. Для этого ис200
T(k)
пользованы арифметическая сложность и
100
O-нотация. Для верификаций полученных
k
0
оценок проведен вычислительный экспе1 10 20 30 40 50 60 70 80 90 100
римент. В системе TALGAT сформироРисунок 3.6 – Зависимости от k
ваны по 100 матриц для каждого случая.
времени: решения k-й СЛАУ (Tk) и
Рассмотрены три структуры. Для струк__
среднего арифметического ( T ( k ) ) туры 1 (рисунок 3.5а) матрицы с N = 1600
получены путем изменения высоты проводника (t) в диапазоне 6, 7, … 105 мкм. Для структуры 2 (рисунок 3.5б) матрицы с N = 2001 получены путем изменения зазоров (s) в диапазоне 100, 101,
… 199 мкм. Для структуры 3 (рисунок 3.5в) матрицы с N = 1709 получены путем изменения зазоров (s) в диапазоне 16,9; 16,8; … 7,1 мкм. Далее учащением
сегментации получены матрицы порядков 3200, 3001 и 3109, соответственно.
Для всех СЛАУ вектор b – единичный.
600
Время, мс
15
Полученные ускорения решения 100 СЛАУ для структур 1, 2 и 3 по отношению к алгоритму без переформирования предобусловливателя (для каждого итерационного метода отдельно) сведены в таблицу 3.3. Также приведены результаты, полученные при переформировании предобусловливателя с
помощью задания оптимального порога числа итераций (с указанием его значений). На рисунке 3.7 показано число
20 Nit
итераций при решении k-й СЛАУ метоOpt
дом BiCGStab с использованием приве15
O
денных алгоритмов для структуры 2
Q
10
при N = 3001.
Из анализа полученных результа5
тов (раздел 3.2.6 диссертации) можно
k
сделать вывод, что при более позднем
0
1 10 20 30 40 50 60 70 80 90 100
переформировании предобусловливателя ускорение уменьшается. Также отРисунок 3.7 – Число итераций при переформировании по O-нотации (O), арифмечено что, чем ближе момент переметической сложности (Q) и оптимальформирования к m, тем меньшее усконому порогу числа итераций (Opt)
рение будет получено.
Таким образом, при многовариантном анализе полосковых структур
методом моментов использование адаптивных условий переформирования
предобусловливателя позволяет ускорить решение 100 СЛАУ методом
BiCGStab до 1,6 раза, а методом CGS до 1,57 раза.
Таблица 3.3 – Ускорение решения 100 СЛАУ методами BiCGStab и CGS с переформированием предобусловливателя по разным условиям
По оптимальному порогу числа
По средней арифметичеПо O-нотации
Стритераций (указан в скобках)
ской сложности решения
N
ра
BiCGStab
CGS
BiCGStab CGS
BiCGStab
CGS
1600
1,42 (8)
1,34 (7)
1,20
1,52
1,12
1,40
1
3200
1,16 (8)
1,35 (7)
0,92
1,27
0,86
1,01
2001
1,62 (10)
1,44 (8)
1,60
0,94
1,52
1,05
2
3001
1,58 (10)
1,31 (9)
1,55
0,87
1,44
0,95
1709
1,12 (9)
1,18 (8)
1,55
1,57
1,55
1,57
3
3109
1,03 (10)
1,00(16)
1,59
1,33
1,59
1,33
Одним из ресурсов ускорения представляется использование определенной очередности решения СЛАУ. Действительно, эта очередность обычно
определяется заданным изменением параметра структуры. Но если общее
время решения всех СЛАУ зависит от того, какая именно СЛАУ будет решаться первой, какая – второй и т.д., то существует оптимальная очередность
по критерию минимального времени решения. То, что такая зависимость существует, следует из самой сути многократного решения СЛАУ итерационным методом с предобусловливанием. Очевидно, что она определяется двумя
факторами: выбором матрицы для вычисления предобусловливателя (то, какая
именно из всех матриц будет выбрана, влияет на число итераций, требуемых
для решения последующих СЛАУ), а также использованием решения преды-
16
дущей СЛАУ в качестве начального приближения текущей (чем ближе начальное приближение окажется к решению, тем меньше потребуется итераций).
При многовариантном анализе используют несколько основных видов изменения параметра: линейное, логарифмическое, с заданными пользователем
значениями. При оптимизации изменение может быть случайное, причем в
любом направлении. Рассмотрим самое простое, но широко используемое изменение: линейное. При нем изменение очередности решения сводится к тривиальному выбору порядка решения, т.е. по возрастанию параметра (прямой
порядок) или его убыванию (обратный порядок).
Отметим, что линейное изменение параметра вовсе не гарантирует монотонного изменения элементов матрицы СЛАУ или её нормы, но может быть
частым на практике. В любом случае полеТаблица 3.4 – Ускорение решезен анализ конкретных структур. Далее расния 100 СЛАУ методами
смотрено линейное изменение параметра,
BiCGStab и CGS с использованием
обратного порядка решения
что позволяет, меняя порядок решения (пряСЛАУ относительно прямого
мой или обратный), выявить оптимальный.
СтрВ таблицу 3.4 сведены полученные ускореN
BiCGStab CGS
ра
ния при использовании обратного порядка
1600
1,76
1,73
решения СЛАУ относительно прямого (ана1
3200
1,63
1,66
логично случаям для рисунка 3.5). Для всех
2001
1,71
1,58
2
структур наблюдается ускорение при ис3001
1,84
1,53
пользовании обратного порядка решения
1709
1,82
1,59
3
СЛАУ, причем оно получено для всех N и
3109
1,83
1,32
обоих итерационных методов. Ускорение
достигается разницей в числе требуемых итераций при решении СЛАУ в прямом (N +it) и обратном (N –it) порядках, выражаемой в площади фигуры, ограниченной кривыми числа итераций (рисунок 3.8, для метода BiCGStab).
25
Nit
20
M1
10
+
N it
N –it
15
Nit
12
M50
8
6
10
4
5
2
k
0
k
0
1
10 20 30 40 50 60 70 80 90 100
Рисунок 3.8 – Число итераций при решении k-й СЛАУ методом BiCGStab в прямом (N +it) и обратном (N –it) порядках
1
10 20 30 40 50 60 70 80 90 100
Рисунок 3.9 – Число итераций, в зависимости
от k, для предобусловливателя, полученного
из первой (M1) и из 50-й (M50) матриц СЛАУ
Таким образом, выбор очередности решения СЛАУ позволяет ускорить
многовариантный анализ полосковых структур методом моментов: на рассмотренных примерах до 1,84 раза.
Одним из факторов, влияющих на многократное решение СЛАУ, является выбор предобусловливателя. Очевидно, что данный выбор будет влиять
17
на общее время многократного решения СЛАУ, т.к. предобусловливатель будет меняться. Как правило, на практике значения параметра структуры меняют
Таблица 3.5 – Ускорение ре- в заданном диапазоне, что позволяет выбирать значение параметра для формирования предобусловливашения 100 СЛАУ методам
BiCGStab с использованием теля. Самый простой способ – выбрать среднее знавыбора 50-й матрицы для
чение параметра для формирования предобусловлипредобусловливателя
вателя. Проведен вычислительный эксперимент (анаСтрN
BiCGStab логично случаям для рисунка 3.5) с выбором 50-й
ра
матрицы для предобусловливателя и порядка реше1600
2,07
1
ния с 1-й по 100-ю СЛАУ. В таблице 3.5 приведены
3200
2,21
полученные ускорения относительно выбора 1-й мат2001
2,14
2
рицы для предобусловливания.Видно, что для всех
3001
1,94
1709
1,81
структур и N наблюдается ускорение (до 2,21 для
3
3109
1,86
структуры 2 при N = 3200). Оно достигается снижением общего числа итераций при многократном решении СЛАУ. На рисунке 3.9 приведено число итераций при решении k-й СЛАУ для случаев с
предобусловливателем, полученным из первой (M1) и из 50-й (M50) матриц
СЛАУ. Видно, что число итераций при формировании предобусловливателя
из 50-й матрицы СЛАУ значительно меньше, чем при формировании из 1-й,
эта разница и объясняет полученное ускорение.
Таким образом, при многовариантном анализе полосковых структур
методом моментов выбор 50-й матрицы для формирования предобусловливателя позволяет уменьшить время решения 100 СЛАУ стабилизированным методом бисопряженных градиентов до 2,21 раза.
4 ЗАКЛЮЧЕНИЕ
В заключении диссертации перечислены её основные результаты, показывающие, что цель работы достигнута, а полученные результаты уменьшения
вычислительных затрат для анализа электромагнитной совместимости методом моментов имеют значение для технических наук в области исследования
«Создание теории синтеза и анализа, а также методов моделирования радиоэлектронных устройств» специальности 05.12.04 –Радиотехника, в том числе
системы и устройства телевидения.
ПУБЛИКАЦИИ ПО МАТЕРИАЛАМ ДИССЕРТАЦИИ
Монография
1. Ахунов Р.Р., Куксенко С.П., Газизов Т.Р., Орлов П.Е. Многократное
решение систем линейных алгебраических уравнений итерационными
методами с предобусловливанием в задачах электромагнитной
совместимости. – Томск: Изд-во Томск. гос. ун-та систем упр. и
радиоэлектроники, 2015. – 152 с.
Статья в зарубежном журнале
2. Gazizov T.R. Acceleration of Multiple Solution of Linear Systems for Analyses
of Microstrip Structures /T.R. Gazizov, S.P. Kuksenko, R.R. Akhunov//
International journal of mathematical models and methods in applied sciences.
– 2015. Vol. 9. – P. 721–726.
18
Статьи в журналах из перечня ВАК
3. Ахунов, Р.Р. Форматы хранения разреженных матриц и ускорение решения
СЛАУ с плотной матрицей итерационными методами / Р.Р. Ахунов,
С.П. Куксенко, В.К. Салов, Т.Р. Газизов // Численные методы и вопросы
организации вычислений. XXV. Зап. научн. семин. ПОМИ. – 2012. – Т.
405(25). – С. 24–39.
4. Ахунов, Р.Р. Вычисление матрицы емкостей произвольной системы
проводников и диэлектриков методом моментов: оценка использования
разреженного строчного формата при решении СЛАУ методом Bicgstab /
Р.Р. Ахунов, С.П. Куксенко // Известия высших учебных заведений.
Физика. – 2012. – Т. 55 (7/2). – С. 27–30.
5. Ахунов, Р.Р.
Усовершенствование
алгоритма
ILU(0)-разложения,
использующего разреженный строчный формат / Р.Р. Ахунов,
С.П. Куксенко, В.К. Салов, Т.Р. Газизов // Численные методы и вопросы
организации вычислений. XXV. Зап. научн. семин. ПОМИ. – 2012. – Т.
405(25). – С. 40–53.
6. Ахунов, Р.Р. Многократное решение СЛАУ с частично изменяющейся
матрицей итерационным методом / Р.Р. Ахунов, С.П. Куксенко, В.К. Салов,
Т.Р. Газизов // Численные методы и вопросы организации вычислений.
XXV. Зап. научн. семин. ПОМИ. – 2013. – Т. 419. – С. 16–25.
7. Ахунов, Р.Р. Ускорение многократного решения СЛАУ итерационным
методом при вычислении емкости микрополосковой линии в широком
диапазоне изменения ее размеров. / Р.Р. Ахунов, С.П. Куксенко, Т.Р. Газизов
// Численные методы и вопросы организации вычислений. XXVII, Зап.
научн. сем. ПОМИ. – 2014. – Т. 428. – С. 32–41.
8. Ахунов, Р.Р. Многократное решение СЛАУ итерационным методом с
переформированием матрицы предобусловливания / Р.Р. Ахунов,
С.П. Куксенко, Т.Р. Газизов // Численные методы и вопросы организации
вычислений. XXVII, Зап. научн. сем. ПОМИ. – 2014. – Т. 428. – С. 42–48.
9. Лежнин Е.В. Алгоритм ILU(0)-разложения с использованием OpenMP /
Е.В. Лежнин, Р.Р. Ахунов, С.П. Куксенко // Докл. Томск. гос. ун-та систем
упр. и радиоэлектроники. – 2015. – № 3(37). – C. 181–183.
10. Ахунов, Р.Р. Простой способ ускорения вычисления емкостных матриц
полосковой структуры при изменении её геометрического параметра /
Р.Р. Ахунов, С.П. Куксенко, Т.Р. Газизов // Докл. Томск. гос. ун-та систем
упр. и радиоэлектроники. – 2015. – № 4. – С. 144–148.
Статья в рецензируемом научном издании
11. Газизов, Т.Р. Пути решения актуальных проблем проектирования
радиоэлектронных средств с учетом электромагнитной совместимости /
Т.Р. Газизов,
А.М. Заболоцкий,
А.О. Мелкозеров,
С.П. Куксенко,
П.Е. Орлов, В.К. Салов, И.Ф. Калимулин, Р.Р. Аширбакиев, Р.Р. Ахунов,
Р.С. Суровцев, М.Е. Комнатнов // Техника радиосвязи. – 2014. – № 2 (22). –
С. 11–22.
19
Доклады в материалах зарубежных конференций
12. New results on EMC simulation for space projects of TUSUR University /
T. Gazizov, A. Melkozerov, P. Orlov, V. Salov, R. Ashirbakiev, R. Akhunov,
S. Kuksenko, I. Kalimulin // IEEE International Conference on Numerical
Electromagnetic Modeling and Optimization for RF, Microwave, and Terahertz
Applications. May 14–16, 2014, Pavia, Italy. – P. 1–4.
13. T. Gazizov, A. Melkozerov, A. Zabolotsky, S. Kuksenko, P. Orlov, V. Salov,
R. Akhunov, I. Kalimulin, R. Surovtsev, M. Komnatnov, A. Gazizov. Ensurance
and simulation of electromagnetic compatibility: recent results in TUSUR
University. International Conference on Applied Physics, Simulation and
Computers, Vienna, Austria, 15–17 March 2015. – Р. 152–161.
14. S.P. Kuksenko, T.R. Gazizov, A.M. Zabolotsky, R.R. Ahunov, R.S. Surovtsev,
V.K. Salov, Eg.V. Lezhnin. New developments for improved simulation of
interconnects based on method of moments. Advances in Intelligent Systems
Research. Proc. of the 2015 Int. Conf. on Modelling, Simulation and Applied
Mathematics (MSAM2015). August 23–24, 2015, Phuket, Thailand. – P. 1–8.
15. R.R. Ahunov, S.P. Kuksenko, T.R. Gazizov. Multiple solution of linear algebraic
systems by an iterative method with recomputed preconditioner in the analysis
of microstrip structures. Proc. of the 13th Int. Conf. of Numerical Analysis and
Applied Mathematics. Sept. 23–29, 2015, Rhodes, Greece. – P. 1–4.
Доклады в материалах отечественных конференций
16. Ахунов Р.Р. Обзор форматов хранения разряженных матриц // Научная
сессия ТУСУР-2010: Материалы докладов Всероссийской научнотехнической конференции студентов, аспирантов и молодых ученых,
Томск, 4–7 мая 2010 г. – Томск: В-Спектр, 2010. – В пяти частях. Ч. 1. –
С. 137–139.
17. Салов В.К., Куксенко С.П., Комнатнов М.Е., Ахунов Р.Р., Мелкозеров А.О.,
Аширбакиев Р.И. Газизов Т.Р. Ускорение вычислений в задачах
моделирования ЭМС. Труды 9-го Межд. Симп. по электромагнитной
совместимости и электромагнитной экологии, г. Санкт-Петербург, 13–16
сентября 2011 г. – С. 269–272.
18. Ахунов, Р.Р. Ускорение многократного решения СЛАУ с изменяющейся
матрицей / Р.Р. Ахунов, С.П. Куксенко. – Международная конференция
«Актуальные проблемы вычислительной и прикладной математики 2015»,
посвященная 90-летию со дня рождения академика Гурия Ивановича
Марчука, Новосибирск, 19–23 октября. – 2015. – С. 84–90.
Документ
Категория
Без категории
Просмотров
4
Размер файла
644 Кб
Теги
анализа, методов, структура, моментов, полосковых
1/--страниц
Пожаловаться на содержимое документа