Алгоритмы решения систем линейных уравнений с блочно-ленточными матрицами (207,00 руб.)

Стр.3

Стр.4

Стр.5

УДК 517.983:[512.644:519.612] (035.3) ББК 22.143+22.162.3 я44Ш 88 Печатается по решению Комитета при Ученом совете Рецензенты: профессор кафедры информатики и вычислительного эксперимента ИММ и КН им. И. И. Воровича Южного федерального университета, доктор физико-математических наук Г. В. Муратова; заведующий лабораторией функционально-градиентных и композитных материалов научно-образовательного центра «Материалы» ДГТУ доктор физико-математических наук С. М. Айзикович Ш 88 Алгоритмы решения систем линейных уравнений с блочно-ленточ-ными матрицами : монография / Б. Я. Штейнберг, О. Б. Штейнберг ; Южный федеральный университет. — Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2022. — 138 с. Штейнберг, Б. Я. ISBN 978-5-9275-4061-7 DOI 10.18522/801287963 Монография содержит новые быстрые алгоритмы решения систем линейных уравнений с блочно-ленточными матрицами. В задачах математического моделирования часто возникает необходимость решения систем линейных алгебраических уравнений большой размерности с разреженными матрицами. Во многих таких случаях матрица системы уравнений оказывается блочно-ленточной или систему уравнений можно преобразовать к эквивалентной системе с такой матрицей. Такие матрицы допускают более компактное хранение в памяти, чем разреженные матрицы общего вида. В данной работе приводятся быстрые алгоритмы решения некоторых таких систем уравнений. Эти алгоритмы опираются на особенности задачи и на особенности современных вычислительных систем. В частности, многие методы решения целевых задач с блочно-ленточными матрицами сводятся к вычислению программных циклов с линейной рекуррентной зависимостью. В данной работе приводятся новые алгоритмы распараллеливания таких рекуррентных циклов, демонстрирующие хорошее ускорение. Эти алгоритмы оказываются эффективными на новых процессорных микросхемах, имеющих большое количество вычислительных ядер. Работа поддержана грантом Правительства РФ № 075-15-2019-1928 ISBN 978-5-9275-4061-7 ББК 22.143+22.162.3 я44 УДК 517.983:[512.644:519.612] (035.3) © Южный федеральный университет, 2022 © Штейнберг Б. Я., Штейнберг О. Б., 2022 © Оформление. Макет. Издательство Южного федерального университета, 2022 Южного федерального университета по естественнонаучному и математическому направлению науки и образования (протокол № 10 от 9 июня 2021 г.)

Стр.3

СОДЕРЖАНИЕ Список сокращений .........................................................................................5 Введение .............................................................................................................6 1. Влияние вычислительных архитектур и компиляторов на быстродействие алгоритмов и их программных реализаций .......9 1.1. Разнообразие и особенности вычислительных систем .......................9 1.2. Модели параллельных вычислений ....................................................16 1.3. Анализ узких мест производительности программ ..........................19 1.4. Отставание развития оптимизирующих компиляторов от развития процессоров ......................................................................20 1.5. Информационные зависимости в программе ....................................22 1.6. Гнезда циклов и пространство итераций ............................................24 1.7. Блочно-ленточные матрицы .................................................................25 2. Преобразования программ и предкомпилятор для ускорения решения СЛАУ с блочно-ленточными матрицами .............................29 2.1. Некоторые эквивалентные преобразования программ .....................29 2.2. Предкомпилятор для ускорения алгоритмов ......................................36 3. О параллельных прямых алгоритмах решения СЛАУ с ленточными и блочно-ленточными матрицами ...............................37 3.1. Параллельное решение СЛАУ с двухдиагональными и блочными двухдиагональными матрицами ..........................................................38 3.2. О последовательном алгоритме, соответствующем параллельному алгоритму решения СЛАУ с двухдиагональной матрицей ...............40 3.3. Применения алгоритма параллельного решения системы уравнения с ленточной двухдиагональной матрицей .......................43 3.4. СЛАУ с ленточными треугольными матрицами ................................45 3.5. СЛАУ с блочной трехдиагональной не треугольной матрицей .......47 3.6. СЛАУ с ленточной матрицей с преобладанием по одной из диагоналей ........................................................................................51 3.7. Параллельное вычисление дробнолинейных рекуррентных последовательностей ............................................................................55 3.8. Разложения трехдиагональных матриц в произведение двухдиагональных ................................................................................57 3.9. Оценки погрешностей решения СЛАУ с двухдиагональной матрицей ................................................................................................59

Стр.4

4. Распараллеливание рекуррентных циклов ..........................................64 4.1. Рекуррентно вычисляемые переменные и рекуррентные циклы .....64 4.2. Рекуррентно замкнутое множество отображений .............................66 4.3. Рекуррентные циклы с несколькими использованиями рекуррентно вычисляемой переменной..............................................69 4.4. О циклах с нелинейной рекуррентной зависимостью ......................72 4.5. Распараллеливание циклов с рекуррентной зависимостью на общей памяти ...................................................................................75 4.6. Векторизация рекуррентных циклов ..................................................82 4.7. Совместное применение распараллеливания и векторизации циклов с линейной рекуррентной зависимостью ..............................85 5. Алгоритмы итерационного типа и их ускорение .................................92 5.1. Итерационные алгоритмы решения СЛАУ с блочно-ленточными матрицами .......................................................92 5.2. Умножение и итерационное умножение блочно-ленточной матрицы на вектор ................................................................................97 5.3. О сводимости программ, аффинно вычисляющих данные, к задачам линейной алгебры ................................................................99 5.4. Операторы сдвига, операторы умножения на функцию и соответствующие им матрицы .......................................................107 5.5. Операторы сдвига ...............................................................................109 5.6. Действия операторов сдвига на массивы и примеры соответствующих этим действиям матриц .......................................114 5.7. О восстановлении алгоритма типа Гаусса-Зейделя по СЛАУ с блочно-ленточной матрицей ...........................................................119 6. Параллельные алгоритмы для вычислительных систем с распределенной памятью ....................................................................122 6.1. Блочно-аффинные размещения массивов в распределенной памяти ...................................................................122 6.2. Межпроцессорные пересылки данных .............................................126 6.3. Оптимальное количество процессорных элементов при параллельном вычислении массивов данных рекуррентным программным циклом .........................................................................126 6.4. Изменение ускорения многопроцессорной вычислительной системы при повышении быстродействия процессоров ................128 Заключение ....................................................................................................130 Литература ....................................................................................................131

Стр.5