Систолические системы для задач матричных модификаций

• Автор: Бондаренко, Екатерина Владимировна
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 163 c. : ил

Глава I. Параллельные методы линейной алгебры

с малоранговыми модификациями

§1.1. Общие принципы анализа параллельных

алгоритмов

§ 1.2. Обращение модифицированных матриц

§ 1.3. Разложения Гаусса и Холесского для

модифицированных матриц

§ 1.4. Методы модификации разложений матриц

на ортогональные и треугольные множители

§ 1.5. Метод модификации симметричной проблемы

собственных значений

§ 1.6. Основные фрагменты алгоритмов линейной
алгебры с малоранговыми модификациями
Глава 2. Систолические массивы для одного класса
алгоритмов линейной алгебры
§ 2.1. Необходимость разработки алгоритмов для
систолических систем
§ 2.2. Описание одного класса алгоритмов
линейной алгебры
§ 2.3. Систолические массивы первого типа
(с двусторонними потоками данных) для
алгоритмов из класса Л
2.4. Систолические массивы второго типа ( с односторонними потоками данных и локальной памятью) для алгоритмов из класса М

Глава 3. Систолические массивы для реализации методов матричных модификаций
§ 3.1. Основные виды и функции элементарных
процессоров
§ 3.2. Фрагменты алгоритмов модификации,
принадлежащие классу М, и их реализация на

§ 3.3. Систолические.массивы первого типа для решения треугольной системы линейных
уравнений
§ 3.4. Систолические массивы второго типа для решения треугольной системы линейных
уравнений
§ 3.5. Некоторые замечания
Заключение
Литература
Приложение

На настоящем этапе развития вычислительной техники потребности в средствах обработки информации непрерывно возрастают.
Это вызвано качественным и количественным изменением характера вычислительных задач, увеличением их сложности и объема. Как отмечено в работе [12] , возникает необходимость исследования объектов и явлений в целом, перехода от линейных моделей к нелинейным, изучения объектов в динамике, построения пространственных моделей. Наиболее крупные вычислительные ресурсы требуются для задач ядерной энергетики, аэродинамики и гидродинамики, теории климата, циркуляции атмосферы и океана, оптимального управления, исследования операций и др. Математическое моделирование в этих областях приводит к необходимости решать, например, системы линейных алгебраических уравнений с ленточны-ми матрицами с числом переменных порядка 10 и шириной ленты
около Ю3 ; с разреженными симметричными матрицами размера око-£
ло 10 . В ряде приложений существует потребность решать задачи

линейного программирования с числом переменных порядка 10 и числом ограничений порядка 10^,
Быстродействие однопроцессорных машин традиционной структуры перестает удовлетворять возрастающим потребностям решения крупных научно-технических и экономических задач. Необходим новый подход к методам разработки, производства и применения ЭВМ [16 , Щ
Одно из главных направлений развития вычислительной техники включает радикальное увеличение суммарной производительности ЭШ за счет совершенствования технической и технологической базы и новых архитектурных решений; освоение более эффективных

(1.28) о; р >
где -единичная матрица размера Кь , х- )г-мерный вектор-столбец, р -число, й 0 , ||^|(—1 .Получим:
іУ(,)=рі|,= (ім-90Т)^ ; р= йог” II ; <}, = -у
В случае УИ= И из ортогональности матрицы 0. следует, что
р~ 0 и
Переортогонализация применяется, если величина р очень
мала, тогда из-за вычислительных ошибок вектор Оу может быть
вовсе не ортогонален матрице 0 . Повторяем процесс с заменой
- .(<)
Г на V , и так далее. Алгоритм можно записать следующим образом.
(в) л (о)
Положить % = ЧГ # Д ія К =1,2,3,
тех пор, пока
11VСк> 11 > II Vе“"1’ II ^ , <х*29)
где у -фиксированный параметр, 0< £ , выполнить:
^>=0ТЯ7(М) ; Х(“'= ХС“"°+ Л°° ;
а^= *,м .
ПОЛОЖИТЬ ... - (к)
г»*.00 , р= 1ИгмИ , (V» у ,
где К -число переортогонализаций. Обычно требуется одна или две переортогонализации.
Учитывая (1.28), получим