БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Выпускная работа по
«Основам информационных технологий»
Магистрант
кафедры численных методов и программирования
Жердецкий Алексей Александрович
Руководители:
доцент, профессор кафедры численных методов и программирования
Волков Василий Михайлович,
ст. преподаватель Кожич Павел Павлович
Минск – 2009 г.
Список обозначений ко всей выпускной работе. 4
Глава 2 Основные прикладные математические пакеты. 7
Возможности Intel Math Kernel Library. 8
Глава 3 (обсуждение результатов). 10
Список литературы к реферату. 11
Список использованных источников. 11
Список публикаций соискателя. 12
Предметный указатель к реферату. 13
Интернет ресурсы в предметной области исследования. 14
Действующий личный сайт в WWW. 15
Тестовые вопросы по Основам информационных технологий. 17
Презентация магистерской диссертации. 18
Список литературы к выпускной работе. 19
MKL – Math Kernel Library
GNU – свободная UNIX-подобная операционная система
GCC – GNU Compiler Collection
ИТ – информационные технологии
ПК – персональный компьютер
СЛАУ – система линейных алгебраических уравнений
ИТ на сегодняшний день являются основным объектом использования в научно-технических решениях. Уже ушли те времена, когда модельные задачи рисовались на бумаге. Сейчас все больший размах набирает оборот и развитие программных средств для симуляции тех или иных жизненно важных процессов. Благодаря комплексу программно-инженерных подходов для анализа той или иной проблемы перестают быть открытыми ранее неизученные вопросы. Вспомнить хотя бы злосчастный 2004 год, когда землетрясение в Индийском океане породило цунами невероятной силы. Долгое время не находилось объяснения многим фактам тех событий. И только после многочисленных компьютерных проверок и испытаний, ученые нашли ответы на свои вопросы.
Да, информация сегодня имеет определяющее значение, а способность ее грамотно обрабатывать и использовать помогает людям справляться со многими комплексами трудноразрешимых задач. И уже часто не важно, в какой области вы работаете либо учитесь. Благодаря огромному разнообразию прикладных вычислительных пакетов обычный человек, имеющий доступ к компьютеру, может пользоваться этими пакетами и не заботиться о том, кем, когда и как они написаны.
Огромную популярность среди математиков и физиков в последние годы получили программные продукты Matlab и Mathematica, имеющие у себя в наличии готовые библиотеки функций для практических расчетов. В этой статье будет более подробно изложен материал по применению пакета Matlab8.0 для решения эллиптических задач физики, в частности, для численного решения уравнения Пуассона для неоднородной среды в цилиндрических координатах со смешанными краевыми условиями. Также мы сделаем небольшой обзор мощных коммерческих продуктов компании Intel, как-то Intel MKL, написанные на основе языков программирования C++ и Fortran и которые начали вытеснять стандартные математические пакеты благодаря оптимизированным алгоритмам.
Нас, в первую очередь, будет интересовать эффективность использования той или иной технологии, а именно: скорость выполнения одной итерации, количество используемой памяти и ряд других параметров. В данной работе мы попытаемся ответить на следующие вопросы:
o какие программные продукты лучше адаптированы к решению СЛАУ с разреженными матрицами;
o сравнительный анализ решения систем с помощью итерационных методов с использованием всевозможных переобуславливателей на каждой итерации;
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.
Задачами реферата являются:
o продемонстрировать работу методов в пакете Matlab на реальных примерах;
o запустить те же задачи под MKL и сравнить скорости поиска решения;
o привести примеры алгоритмов решения задач.
Глава 2 Основные прикладные математические пакеты.
Matlab – широко используемый физико-математический прикладной пакет, предназначенный для выполнения инженерных и научных расчетов. Одним из достоинств данного пакета является то, что многие функции написаны на низкоуровневых языках программирования. Это способствует тому, что многие вычислительные процессы легко векторизуются, то есть, например, сложение и умножение векторов происходит не поэлементно, а целиком.
Возможность написания кода в отдельных *.m файлах разделяет целую задачу на ряд подзадач. Пакет обладает широкими графическими возможностями, расширяемыми от версии к версии. Помимо этого, в состав коммерческих версий входит целый набор так называемых тулбоксов (Matlab Toolboxes), которые предназначены для решения конкретных задач во всевозможных областях, с которыми сталкивается человек. Умение грамотно пользоваться всеми этими возможностями существенно сокращает время реализации всяческих проектов в математике и физике и делает процесс вычислений быстрее и экономичнее.
Рассмотрим несколько практических примеров использования Matlab. Перед этим следует сказать, что сам по себе Matlab является достаточно умным программным средством. Почему? Ответ прост. Matlab работает по-разному в зависимости от типа и количества входящих параметров, и, следовательно, ищется более эффективный способ решения той или иной задачи.
Приведем пример решения СЛАУ. В Matlab это реализуется с помощью наклонной черты "\".
A =
2 4 -6
6 4 2
-7 2 9
b = [7 3 -2]
A\b = [0.0357 1.0446 -0.4821]
В данном случае система решается методом Гаусса (с большой вероятносью). Если исходная матрица имеет трехдиагональный вид, поиск решения будет происходить иными, более экономичными, методами.
Для решения дискретизированного уравнения Пуассона просто обойтись теми средствами, которыми обладает Matlab, не получится. Дело в том, что перенос исходного уравнения на мелкие сетки, приводит к образованию линейных систем больших порядков. Существует встроенная функция bicg(), решающая разреженные системы методом бисопряженных градиентов без переобуславливателей и с переобуславливателем. Однако эта функция работает хорошо лишь с ограниченным набором переобуславливателей (например, с переобуславливателем Якоби). Недостатком использования bicg() с переобуславливателем Якоби является то, что число итераций, необходимых для поиска решения, достаточно велико. Для применения переобуславливателя Фурье, который строится по принципу того, что уравнение Пуассона рассматривается для однородной среды, код функции bicg() необходимо корректировать, так как на каждой итерации должно производиться прямое и обратное преобразования Фурье.
В общем, эта задача не очень сложная, если подробно разобрать код bicg()-функции, однако это требует понимания того, как работает сам алгоритм бисопряженных градиентов, и для рядового пользователя зачастую это не под силу. Процесс внедрения преобразования Фурье в метод бисопряженных градиентов и эффективность его использования с точки зрения сокращения числа итераций еще полностью не изучены. Однако предварительные результаты для исследуемого уравнения Пуассона обнадеживают. Первые проверки показывают, что число итераций упало и практически не зависит от числа узлов сетки.