автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему: Решение некоторых задач математической физики методами Монте-Карло
Автореферат диссертации по теме "Решение некоторых задач математической физики методами Монте-Карло"
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
На правах рукописи
КУЗНЕЦОВ Андрей Николаевич
РЕШЕНИЕ НЕКОТОРЫХ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ МЕТОДАМИ МОНТЕ-КАРЛО
05.13.18 — Математическое моделирование, численные методы и комплексы программ
диссертации на соискание учёной степени кандидата физико-математических наук
Работа выполнена на кафедре прикладной математики факультета прикладной математики и компьютерных технологий Вологодского государственного педагогического университета
кандидат физико-математических наук, доцент, СИПИН Александр Степанович
доктор физико-математических наук, профессор МЕЛАС Вячеслав Борисович (Санкт-Петербургский государственный университет)
кандидат физико-математических наук, ведущий инженер-программист ТИМОФЕЕВ Константин Алексеевич (Санкт-Петербург, ЗАО «Транзас технологии»)
Ведущая организация: ФГБОУ ВПО «Московский государственный
университет имени М.В.Ломоносова» (факультет ВМК МГУ)
Защита состоится «Л» __ 2012 г. в А? часов на заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петергоф, Университетский пр., 28, математико-механический факультет, ауд. 405.
С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.
диссертационного совета „ Кривулин Н. К.
Общая характеристика работы
С расширением использования сверхбольших интегральных схем и развитием высокочастотной электротехники значительное влияние на работу электронных систем стали оказывать значения паразитных элементов сопротивления, индуктивности и ёмкости. Так как при проектировании схем может потребоваться моделирование сотен или даже тысяч различных их конфигураций, выдвигаются высокие требования к быстродействию и точности программ вычисления значений паразитных параметров. Аналитическое решение данной проблемы возможно лишь в случае небольшого количества проводников достаточно простой формы (параллелепипеды, сферы, цилиндры), поэтому для оценки взаимных электростатических емкостей трёхмерных систем из большого количества объектов требуется применение тех или иных способов численного решения этой задачи.
В работе проведён обзор существующих методов нахождения взаимных электростатических ёмкостей проводников и рассмотрена возможность их вычисления методами Монте-Карло.
Знание первого собственного числа для оператора Лапласа может потребоваться для оценки применимости различных алгоритмов решения краевых задач, например, при решении задачи Гельмгольца с помощью «блуждания по шарам и сферам». В работе рассмотрены алгоритмы нахождения оценок итераций оператора Грина для оператора Лапласа и. первого собственного числа для оператора Лапласа. Рассмотрена возможность использования оценок итераций оператора Грина для расширения области применимости методов Монте-Карло при решении уравнения Гельмгольца с помощью аналитического продолжения решения методом замены переменных. Цели работы
• Разработка алгоритмов вычисления взаимных электростатических емкостей методами Монте-Карло.
• Исследование оценок итераций оператора Грина с целью вычисления первого собственного числа оператора Лапласа и решения уравнения Гельмгольца.
• Реализация перечисленных алгоритмов для вычислений с использованием МР1-кластеров и графических процессоров общего назначения.
• Создание программного комплекса, упрощающего «обычную» и «параллельную» реализацию указанных программ.
Методика исследования включает применение методов статистического моделирования к решению краевых задач математической физики. С помощью формул Грина краевые задачи сводятся к интегральному уравнению, которое затем решается методом Монте-Карло. При решении уравнения Гельм-гольца используется аналитическое продолжение решения методом замены переменных [1]. При нахождении первого собственного числа для краевых задач используются известные итерационные методы.Для реализации алгоритмов использованы язык программирования С++, реализация MPI MPICH-2, технология CUDA.
Основные результаты, выносимые на защиту
• Универсальные алгоритмы вычисления взаимных электростатических ёмкостей методами «блуждания по сферам» и «блуждания по сферам и полусферам».
• Алгоритмы для оценок итераций оператора Грина и вычисления первого собственного числа оператора Лапласа.
• Комплекс программ для реализации алгоритмов Монте-Карло. Реализация перечисленных алгоритмов.
Разработан новый универсальный стохастический алгоритм вычисления взаимных электростатических емкостей с помощью «блуждания по сферам». Алгоритм не требует того, чтобы границы объектов были плоскими. В случае же, если все или часть границ являются плоскими, алгоритм «блуждания по сферам и полусферам» позволяет ускорить вычисления и повысить точность расчетов за счет построения несмещённой оценки. Представлены новые алгоритмы вычисления итераций оператора Грина. Практическая значимость
Разработанные статистические алгоритмы вычисления взаимных электростатических ёмкостей проводников могут быть использованы для оценки паразитных электростатических ёмкостей в больших и сверхбольших интегральных схемах и многослойных печатных платах. Проведены вычислительные эксперименты для алгоритмов, использующих методы Монте-Карло при решении задачи Дирихле для уравнения Гельмгольца. Рассмотрены различные методы вычисления итераций оператора Грина методами Монте-Карло. Проведены вычислительные эксперименты, позволяющие оценить возможность использования аналитического продолжения решения методом заме-
ны переменных. Представлены новые алгоритмы вычисления оценок первого собственного числа для оператора Лапласа с помощью оценок степеней оператора Грина. Разработан программный комплекс для реализации вычислительных задач, использующих методы Монте-Карло. Программный комплекс позволяет упростить реализацию и проведение вычислительных экспериментов как на выделенных компьютерах, так и на MPI-кластерс или графическом процессоре общего назначения. Апробация работы
Основные результаты обсуждались на семинарах кафедры прикладной математики в Вологодском государственном педагогическом университете, семинаре кафедры статистического моделирования математико-механичес-кого факультета СПбГУ и докладывались на
• пятой Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи» (СамГТУ, Самара, 29-31 мая 2008 г.);
• II ежегодном смотре-сессии аспирантов и молодых учёных по отраслям наук. Секция «Математика. Информатика. Методика преподавания» (Вологда, 12-14 ноября 2008 г.);
• научной школе-конференции молодых исследователей «Математические идеи П. JI. Чебышева и их приложение к современным проблемам естествознания» (Обнинск, 14-18 мая 2011 г.).
Материалы диссертации опубликованы в работах [А1-А4]. Из них работы [AI—A3] — в списке журналов, рекомендованных ВАК. Работы [AI-A3] выполнены в соавторстве. Соискателю в них принадлежат реализация задач, численные результаты, соавторам — общая постановка задач и верификация результатов.
Структура и объём диссертации
Диссертация состоит из введения, 4-х глав, заключения и списка литературы. Список литературы содержит 51 наименование. Общий объем работы составляет 147 страниц.
Во введении обосновывается актуальность диссертационной работы, формулируются задачи исследований, и содержится краткий обзор результатов работы.
В первой главе рассматривается проблема нахождения взаимных электростатических ёмкостей.
В первом разделе приводится постановка задачи нахождения электростатической ёмкости уединённого проводника и взаимных электростатических ёмкостей нескольких проводников.
Рассмотрим основную задачу электростатики в обратной постановке: требуется найти функцию у?, удовлетворяющую уравнению Лапласа = О вне заданной системы проводников, обращающуюся в нуль на бесконечности, принимающую некоторые постоянные значения ^pi на поверхностях проводников Г* и удовлетворяющую интегральному соотношению на поверхностях проводников
где п — вектор внешней нормали к поверхности проводника. В [2] показано, что эта задача имеет единственное решение.
После нахождения констант ^ определение потенциала сводится к решению внешней задачи Дирихле для уравнения Лапласа. Потенциал существенно зависит от формы и расположения других проводников. Согласно [2], имеют место соотношения:
91 = Сц91 + С\2 (^2 - Ы + • • ■ + С1п