Вычислительная математика и структура алгоритмов

Воеводин В. В.5-211-05310-9

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

Содержание
Введение
Лекция 1. БОЛЬШИЕ ЗАДАЧИ И БОЛЬШИЕ КОМПЬЮТЕРЫ
Компьютеры как эффективный инструмент численных исследований. Дискретизация объектов. Примеры больших задач – моделирование климатической системы и обтекание летательных аппаратов. Взаимосвязь компьютеров и задач. Необходимость создания больших вычислительных систем. Этапы численного эксперимента.
Лекция 2. БОЛЬШИЕ ЗАДАЧИ И ПРОГРАММИРОВАНИЕ
Интересы специалистов и программирование. Предельно сложные задачи. Совершенствование техники и программирование. Преемственность программных наработок. Переносимость программного обеспечения. Отсутствие гарантий качества компиляции. Простые примеры. Необходимость изучения структуры алгоритмов.
Лекция 3. КОМПЬЮТЕРЫ И ПАРАЛЛЕЛЬНЫЕ ФОРМЫ АЛГОРИТМОВ
Абстрактная модель последовательного компьютера. Влияние последовательных вычислений. Развитие параллелизма в компьютерах. Концепция неограниченного параллелизма. Граф алгоритма. Необходимость новых сведений о структуре алгоритмов. Параллельная форма алгоритма. Абстрактная модель параллельной системы.
Лекция 4. ХАРАКТЕРИСТИКА ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ
Простое и конвейерное функциональное устройство. Загруженность. Производительность. Ускорение. Система устройств. Влияние связей между устройствами. Законы Амдала и следствия.
Лекция 5. МАТЕМАТИЧЕСКИ ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ
Математически эквивалентные преобразования. Алгебраические законы на практике не выполняются. Эквивалентные преобразования и устойчивость. Эквивалентные преобразования и число операций. Эквивалентные преобразования и параллелизм вычислений. Принцип сдваивания. Информационное ядро алгоритма. Снова граф алгоритма. Граф алгоритма и ошибки округления. Оценка параллелизма алгоритма снизу.
Лекция 6. КОМПЬЮТЕРЫ И ОШИБКИ ОКРУГЛЕНИЯ
Позиционные системы счисления. Ошибки округления. Наилучшее округление. Преимущества сокращенных систем счисления. Фиксированная и плавающая запятая. Машинный нуль. Точность представления чисел. Обоснование вероятностных свойств ошибок округления. Особенность операций сложения и вычитания. Двоичная система счисления не является лучшей. Ошибки округления иногда помогают.
Лекция 7. РАЗВЕРТКИ И ГРАФ-МАШИНА
Строгие и обобщенные развертки. Развертки и параллелизм в алгоритмах. Компьютерная интерпретация. Граф-машина. Теорема о гомоморфной свертке графа. Параллельная структура. Макро- и микропараллелизм. Расщепляющие развертки. Полумодуль обобщенных разверток. Направленные графы. Линейные развертки. Расщепление алгоритма на фрагменты. Рекуррентные соотношения. Регулярные графы.
Лекция 8. НОВЫЙ МАТЕМАТИЧЕСКИЙ АППАРАТ
Выбор формы описания алгоритмов. Линейный класс программ. Пространство итераций. Размещение вершин графа. Покрывающие функции. Теорема об информационном покрытии. Инвариантность линейных многогранников. Кусочно-линейные развертки. Теорема о кусочно-линейных развертках. Косвенная адресация и хаос в дугах. Унифицированное описание алгоритмов. Локальные алгоритмы и графы. Задача укладки графа.
Лекция 9. ТИПОВЫЕ ИНФОРМАЦИОННЫЕ СТРУКТУРЫ
Перемножение матриц. Решение треугольных систем. Неожиданный эффект. Система с блочно-двухдиагональной матрицей. Макро- и микрореализации. Явная схема для уравнения теплопроводности. Макро- и микропараллелизм. Локальный алгоритм. Очень “простой” пример. Гипотеза о типовых структурах.
Лекция 10. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И МАТЕМАТИЧЕСКОЕ ОБРАЗОВАНИЕ
Что заставляет менять образование. Параллельные вычисления на стыке дисциплин. Последовательные вычисления маскируют проблемы развития. Необходимость учить решать задачи эффективно. Причина многих трудностей – незнание структуры алгоритмов. Возможные пути изменения ситуации.
Рекомендуемая литература

Другие книги автора на сайте
Современные проблемы вычислительной математики и математического моделирования. В 2 томах / под ред. Н. С. Бахвалова и В. В. Воеводина

Еще по теме ?параллельное программирование?
Богачев К. Ю. Основы параллельного программирования
Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем
Топорков В. В. Модели распределенных вычислений
Шпаковский Г. И., Серикова Н. В. Программирование для многопроцессорных систем в стандарте MPI
Якобовский М. В. Распределенные системы и сети

Еще по теме ?вычислительная математика?
Воробьева Г. Н., Данилова А. Н. Практикум по вычислительной математике
Коллатц Л. Функциональный анализ и вычислительная математика
Марчук Г. И. Методы вычислительной математики