БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТВыпускная работа по«Основам информационных технологий» Магистранткафедры численных методов и программированияЖердецкий Алексей АлександровичРуководители:доцент, профессор кафедры численных методов и программированияВолков Василий Михайлович,ст. преподаватель Кожич Павел ПавловичМинск – 2009 г. Оглавление Оглавление 3Список обозначений ко всей выпускной работе 4Реферат на тему «Применение информационных технологий в численных методах для уравнения Пуассона в цилиндрической системе координат» 5 Введение 5 Глава 1 (обзор литературы). 6 Глава 2 Основные прикладные математические пакеты. 7 Возможности Matlab 7 Возможности Intel Math Kernel Library. 8 Глава 3 (обсуждение результатов). 10 Заключение. 11 Список литературы к реферату. 11 Список использованных источников. 11 Список публикаций соискателя. 12Предметный указатель к реферату. 13Интернет ресурсы в предметной области исследования. 14Действующий личный сайт в WWW. 15Граф научных интересов. 16Тестовые вопросы по Основам информационных технологий 17Презентация магистерской диссертации. 18Список литературы к выпускной работе. 19 Приложение А 20 ^ Список обозначений ко всей выпускной работе MKL – Math Kernel LibraryGNU – свободная UNIX-подобная операционная системаGCC – GNU Compiler CollectionИТ – информационные технологииПК – персональный компьютерСЛАУ – система линейных алгебраических уравнений^ Реферат на тему «Применение информационных технологий в численных методах для уравнения Пуассона в цилиндрической системе координат» Введение ИТ на сегодняшний день являются основным объектом использования в научно-технических решениях. Уже ушли те времена, когда модельные задачи рисовались на бумаге. Сейчас все больший размах набирает оборот и развитие программных средств для симуляции тех или иных жизненно важных процессов. Благодаря комплексу программно-инженерных подходов для анализа той или иной проблемы перестают быть открытыми ранее неизученные вопросы. Вспомнить хотя бы злосчастный 2004 год, когда землетрясение в Индийском океане породило цунами невероятной силы. Долгое время не находилось объяснения многим фактам тех событий. И только после многочисленных компьютерных проверок и испытаний, ученые нашли ответы на свои вопросы.Да, информация сегодня имеет определяющее значение, а способность ее грамотно обрабатывать и использовать помогает людям справляться со многими комплексами трудноразрешимых задач. И уже часто не важно, в какой области вы работаете либо учитесь. Благодаря огромному разнообразию прикладных вычислительных пакетов обычный человек, имеющий доступ к компьютеру, может пользоваться этими пакетами и не заботиться о том, кем, когда и как они написаны. Огромную популярность среди математиков и физиков в последние годы получили программные продукты Matlab и Mathematica, имеющие у себя в наличии готовые библиотеки функций для практических расчетов. В этой статье будет более подробно изложен материал по применению пакета Matlab8.0 для решения эллиптических задач физики, в частности, для численного решения уравнения Пуассона для неоднородной среды в цилиндрических координатах со смешанными краевыми условиями. Также мы сделаем небольшой обзор мощных коммерческих продуктов компании Intel, как-то Intel MKL, написанные на основе языков программирования C++ и Fortran и которые начали вытеснять стандартные математические пакеты благодаря оптимизированным алгоритмам.Нас, в первую очередь, будет интересовать эффективность использования той или иной технологии, а именно: скорость выполнения одной итерации, количество используемой памяти и ряд других параметров. В данной работе мы попытаемся ответить на следующие вопросы: какие программные продукты лучше адаптированы к решению СЛАУ с разреженными матрицами;сравнительный анализ решения систем с помощью итерационных методов с использованием всевозможных переобуславливателей на каждой итерации;^ Глава 1 (обзор литературы). 1. «Численные методы» А. А. Самарский, А. В. Гулин. В книге присутствуют разделы, описывающие способы построения базиса пространства Фурье для одномерного уравнения Лапласа. 2. «Iterative Methods for Sparse Linear Systems» Y. Saad. Книга разбирает основные алгоритмы для решения СЛАУ с разреженными матрицами. Большое внимание концентрируется на описании методов градиентного типа, основывающихся на построении подпространства Крылова, и их реализации в пакете Matlab. 3. «Numerical Recipes in C» H. Press, A. Teukolsky, T. Vetterling. Книга приводит ряд наиболее применимых вспомогательных алгоритмов для решения целого комплекса физических и математических задач. Несколько глав акцентируют внимание на вопросах обработки сигналов, свертках сигнала с помощью быстрого преобразования Фурье. Приводятся готовые алгоритмы сверток, которые можно использовать для построения переобуславливателей Фурье. 4. «A 3D Vector-Additive Iterative Solverfor the Anisotropic Inhomogeneous Poisson Equation in the Forward EEG problem» V. Volkov, S. Turovets, A. Malony, A. Zherdetsky. Статья описывает новый подход для решения СЛАУ с разреженными матрицами методом декомпозиции области и последующего распараллеливания процессов.5. «Journal of NeuroEngineering and Rehabilitation» H. Hallez, B. Vanrumste, R. Grech, J Muscat. В этом электронном журнале приводятся последние достижения в области реабилитации мозга: описываются процессы генерации нервных импульсов, изменения проводимости тканей под воздействием внешних факторов. Также анализируется возможность использования прикладной математики и физики в решении различных проблем, в том числе прямой и обратной задачи электроэнцефалографии.6. «Методы решения задач математической физики» Е. А. Рындин. Книга является практическим руководством по применению пакета Matlab для решения различных классов задач математической физики. В частности разбираются примеры решения однородного уравнения Пуассона с разными видами граничных условий.7. «Intel Math Kernel Library for Windows* OS». Пользовательское практическое руководство по настройке и использованию библиотек MKL.Задачами реферата являются: продемонстрировать работу методов в пакете Matlab на реальных примерах; запустить те же задачи под MKL и сравнить скорости поиска решения; привести примеры алгоритмов решения задач.^ Глава 2 Основные прикладные математические пакеты. Возможности Matlab Matlab – широко используемый физико-математический прикладной пакет, предназначенный для выполнения инженерных и научных расчетов. Одним из достоинств данного пакета является то, что многие функции написаны на низкоуровневых языках программирования. Это способствует тому, что многие вычислительные процессы легко векторизуются, то есть, например, сложение и умножение векторов происходит не поэлементно, а целиком. Возможность написания кода в отдельных *.m файлах разделяет целую задачу на ряд подзадач. Пакет обладает широкими графическими возможностями, расширяемыми от версии к версии. Помимо этого, в состав коммерческих версий входит целый набор так называемых тулбоксов (Matlab Toolboxes), которые предназначены для решения конкретных задач во всевозможных областях, с которыми сталкивается человек. Умение грамотно пользоваться всеми этими возможностями существенно сокращает время реализации всяческих проектов в математике и физике и делает процесс вычислений быстрее и экономичнее. Рассмотрим несколько практических примеров использования Matlab. Перед этим следует сказать, что сам по себе Matlab является достаточно умным программным средством. Почему? Ответ прост. Matlab работает по-разному в зависимости от типа и количества входящих параметров, и, следовательно, ищется более эффективный способ решения той или иной задачи. Приведем пример решения СЛАУ. В Matlab это реализуется с помощью наклонной черты "\". A =2 4 -6 6 4 2 -7 2 9b = [7 3 -2]A\b = [0.0357 1.0446 -0.4821] В данном случае система решается методом Гаусса (с большой вероятносью). Если исходная матрица имеет трехдиагональный вид, поиск решения будет происходить иными, более экономичными, методами. Для решения дискретизированного уравнения Пуассона просто обойтись теми средствами, которыми обладает Matlab, не получится. Дело в том, что перенос исходного уравнения на мелкие сетки, приводит к образованию линейных систем больших порядков. Существует встроенная функция bicg(), решающая разреженные системы методом бисопряженных градиентов без переобуславливателей и с переобуславливателем. Однако эта функция работает хорошо лишь с ограниченным набором переобуславливателей (например, с переобуславливателем Якоби). Недостатком использования bicg() с переобуславливателем Якоби является то, что число итераций, необходимых для поиска решения, достаточно велико. Для применения переобуславливателя Фурье, который строится по принципу того, что уравнение Пуассона рассматривается для однородной среды, код функции bicg() необходимо корректировать, так как на каждой итерации должно производиться прямое и обратное преобразования Фурье. В общем, эта задача не очень сложная, если подробно разобрать код bicg()-функции, однако это требует понимания того, как работает сам алгоритм бисопряженных градиентов, и для рядового пользователя зачастую это не под силу. Процесс внедрения преобразования Фурье в метод бисопряженных градиентов и эффективность его использования с точки зрения сокращения числа итераций еще полностью не изучены. Однако предварительные результаты для исследуемого уравнения Пуассона обнадеживают. Первые проверки показывают, что число итераций упало и практически не зависит от числа узлов сетки. ^ Возможности Intel Math Kernel Library. Этот набор функций является более мощным по сравнению с Matlab в плоскости операционного исчисления и скорости выполнения алгебраических операций. Однако библиотеки MKL не могут быть использованы так, как используются библиотеки Matlab. Для решения какой-то конкретной задачи необходимо подготовить существенное количество программного кода, что часто ведет к ошибкам во время выполнения.После многочисленных тестов были сделаны выводы на счет того, что наиболее эффективно эта библиотека работает на 64-битных Intel® процессорах с мультиядерной архитектурой. Основными компонентами MKL являются следующие пакеты: BLASSparse BLASLAPACKSparse solver routinesFFTСтандартно под эти пакеты пишутся программы на C/C++ либо на Fortran. Самым проверенным способом включения в работу MKL является ее интеграция в Microsoft Visual Studio.^ Рис. 1 Microsoft Visual Studio с подключенными библиотеками MKL.MKL имеет в своем арсенале более гибкие по сравнению с другими библиотеками подходы для решения той или иной задачи. Если коснуться, например, решения линейных систем, то MKL непременно предложит из имеющегося у него набора функционала тот необходимый инструментарий, который больше всего подходит в данном конкретном случае: будет произведен поиск самого оптимального солвера1 для каждого типа матрицы линейной системы. Одна из особенностей Intel MKL – независимость от компилятора. Это означает, что программный код, написанный однажды, свободно переносится на другие системы. Кроме того, компоненты библиотеки распределены по независимым уровням. Предусмотрено как распараллеливание для компилятора Intel® Compiler, так и распараллеливание для компилятора GCC. Код может быть слинкован с любым из уровней, а процедуры, зависимые от компиляторов Intel или GNU, изолированы на каждом уровне. Другая особенность MKL заключается в том, что разработчику, подключающему библиотеку, не нужно беспокоиться о настройках для конкретного процессора; библиотека Intel MKL осуществляет диспетчеризацию кода таким образом, что на стадии выполнения на каждом типе процессора запускаются оптимальные для него процедуры. Тестировщиками компании Intel® были запущены приложения, использовавшие BLAS, на 64-битной Windows*. Для процессоров Intel® Xeon Processor 5400 series с одной стороны, и процессоров Intel AVX с другой, в каждом случае выполняется свой код. Библиотека Intel MKL позволяет разработчику всегда получать максимальную возможную производительность, не требуя наличия отдельных двоичных файлов для различных процессоров. Еще одним достоинством библиотеки Intel MKL является ее конкурентоспособная производительность на процессорах других производителей, помимо Intel, что упрощает использование библиотеки в массовых продуктах. Библиотека Intel MKL является потоко-безопасной, поддерживает распараллеливание и оптимизировано под многоядерные системы. Используя Intel MKL, разработчик может повысить производительность своего приложения в тех случаях, когда целесообразно использование многопоточности.^ Глава 3 (обсуждение результатов). При использовании программных продуктов Matlab и Intel MKL более интуитивно понятным и не требующим особых знаний в области программирования является первый из двух вариантов. Простота, грамотно построенный пользовательский интерфейс и широчайшие графические возможности зачастую имеют преимущества даже перед самыми быстрыми и оптимизированными средствами. Для студентов, преподавателей и обычных пользователей Matlab–незаменимый пакет. Более того, при грамотном применении его можно использовать в инженерии. Низкоуровневые математические библиотеки MKL, совместимые с компиляторами Intel C/C++ and Fortran Compiler, по своим возможностям и перспективам, безусловно, заслуживают отдельного внимания, но они требуют дополнительных знаний в области программирования и не каждый пользователь ПК в состоянии применять данную технологию на практике. Сейчас наука подошла к тому этапу, когда необходимо сделать следующий шаг вперед. И дело здесь не столько в каких-то открытиях, сколько в новых методах исследования. Способность интегрировать такие мощные средства, как MKL, в сложные программы инженерных расчетов несомненно может явиться положительным моментом в решении этих вопросов. Заключение. В данной работе дано краткое описание двух наиболее востребованных на сегодняшний день средств решения задач математики и физики. Как уже отмечалось, серия продуктов Matlab довольно популярна среди пользователей благодаря продуманному интерфейсу. Также дополнительные пакеты-тулбоксы (фактически это отдельные подпрограммы), ориентированные на решение конкретного спектра задач, привлекают людей использовать этот продукт как основной. Однако не стоит забывать и об альтернативах. Конечно, если говорить об MKL, то зачастую трудно неопытному пользователю привыкнуть к такому вроде как неудобному инструментальному средству. Но, научившись пользоваться всеми имеющимися на сегодня программными продуктами и грамотно использовать в каждом конкретном случае свои знания, можно достичь очень серьезных результатов.^ Список литературы к реферату. Список использованных источников. H. Hallez, B. Vanrumste, R. Grech, J Muscat. Journal of NeuroEngineering and Rehabilitation. BioMed Central Ltd 2007.Press W.H., Teukolsky S.A., Vetterling W.T. Numerical Recipes in C. Cambridge University Press 1997.Y. Saad. Iterative Methods for Sparse Linear Systems. 2000.Е. А. Рындин. Методы решения задач математической физики. Режим доступа: http://www.intel.com/. – Дата доступа: 12.10.2009.Режим доступа: http://www.mathworks.com. – Дата доступа: 15.10.2009.Режим доступа: http://www.wikipedia.org. – Дата доступа: 12.12.2009.Самарский А. А., Гулин А. В. Численные методы. Москва: Наука 1989.^ Список публикаций соискателя. V. Volkov, S. Turovets, A. Malony, A. Zherdetsky. A 3D Vector-Additive Iterative Solverfor the Anisotropic Inhomogeneous Poisson Equation in the Forward EEG problem. ICCS (1) 2009, 511-520.^ Предметный указатель к реферату. bicg 8 Mathcad 7, 8, 9 Matlab 5, 6, 7, 8, 10, 14 MKL 4, 5, 7, 8, 9, 10, 11 метод бисопряженных градиентов 8 СЛАУ 6 уравнение Пуассона 8^ Интернет ресурсы в предметной области исследования. http://www.mathworks.com – сайт представляет последние программные апдейты для пакета Matlab и знакомит с новыми девелоперскими решениями данного продукта.http://www.vak.org.by – сайт Высшей аттестационной комиссии Республики Беларусь.http://www.bookam.net. – здесь представлен широчайший выбор литературы отечественных и зарубежных авторов, в том числе по математике и по физике.http://www.exponenta.ru – сайт обладает неплохой базой готовых задач, которые можно скачать и запустить на своем компьютере. http://www.mexmat.net – российский неофициальный сайт мехмата МГУ. Как часто это бывает, на неофициальных сайтах можно найти материалы намного лучше и содержательнее, чем на официальном ресурсе.^ Действующий личный сайт в WWW. Личный сайт: http://www.alexei-zherdetsky.narod.ru/ Граф научных интересов. Магистранта Жердецкого А.А. механико-математический факультет Специальность математика Смежные специальности 01.01.01 – Математический анализ Скалярное произведение. Евклидовы и унитарные пространства. Гильбертовы пространства. Операции анализа для обобщенных функций (свертки, преобразование Фурье). Полные и замкнутые ортонормированные системы. Ряды Фурье. ^ 05.13.18—Математическое моделирование, численные методы и комплексы программ Метод конечных разностей решения краевых задач. Метод аппроксимации краевых условий. Разностная схема. Решение систем линейных алгебраических уравнений (СЛАУ) точными методами. Метод сопряженных градиентов. Особенности моделирования на ЭВМ с многопроцессорной архитектурой и ЭВМ с параллельными процессорами. Программные средства для компьютерного моделирования. Прикладное программное обеспечение научных исследований. Основная специальность ^ 01.01.07 – Вычислительная математика Метод прогонки решения систем с трехдиагональной матрицей. Численные методы решения дифференциальных уравнений. Оценка погрешности, сходимость и устойчивость. Основные понятия теории разностных схем (аппроксимация, устойчивость, сходимость). Разностные методы решения краевых задач для эллиптических уравнений. Экономные методы численного решения многомерных задач. Методы градиентного типа. Построение переобуславливателей. Переобуславливатель Фурье. Сопутствующие специальности ^ 01.01.04 – Геометрия и топология Системы координат. Цилиндрическая система координат. ^ Тестовые вопросы по Основам информационных технологий v021.txt01 Какой тег предназначен для обмена данными между пользователем и сервером?: нет правильного ответа v521.txt01 Векторы x и y называются A-ортогональными, если: все ответы правильные^ Презентация магистерской диссертации. Ссылка на презентацию: http://www.alexei-zherdetsky.narod.ru/presentation.html. Также презентацию работы можно посмотреть в Приложении А.^ Список литературы к выпускной работе. H. Hallez, B. Vanrumste, R. Grech, J Muscat. Journal of NeuroEngineering and Rehabilitation. BioMed Central Ltd 2007.Press W.H., Teukolsky S.A., Vetterling W.T. Numerical Recipes in C. Cambridge University Press 1997.V. Volkov, S. Turovets, A. Malony, A. Zherdetsky. A 3D Vector-Additive Iterative Solverfor the Anisotropic Inhomogeneous Poisson Equation in the Forward EEG problem. ICCS (1) 2009, 511-520.Y. Saad. Iterative Methods for Sparse Linear Systems. 2000.Е. А. Рындин. Методы решения задач математической физики. Самарский А. А., Гулин А. В. Численные методы. Москва: Наука 1989.^ Приложение А 1 Солвер (от англ. solver) – средство, или метод, решения некоторой задачи.