Методы_прогонки (Весенний семестр)

Нижегородский государственный университетим. Н.И.ЛобачевскогоФакультет Вычислительной математики и кибернетикиПараллельные численные методыМетод прогонкиПри поддержке компании IntelБаркалов К.А.,Кафедра математического обеспечения ЭВМСодержаниеПостановка задачиЛенточные матрицыМетод прогонки (правая и левая прогонки)Встречная прогонка в двух потокахПараллельная блочная прогонкаОценки эффективностиРезультаты экспериментовН.Новгород, 2010 г.Параллельные численные методы.2 из 46Постановка задачиРассмотрим систему из n линейных алгебраических уравнений видаa11 x1 a12 x 2 ...  a1n x n b1a 21 x1 a 21 x 2 ...  a 2 n x n b2 an 2 x2 ...  a nn x n bn...a n1 x1В матричном виде система может быть представлена какAxbA(aij) есть вещественная матрица размера n×n; b и x  вектора из nэлементов.Будем искать значения вектора неизвестных x, при которыхвыполняются все уравнения системы.Н.Новгород, 2010 г.Параллельные численные методы.3 из 46Ленточные матрицыМатрица A называется ленточной, когда все ее ненулевые элементынаходятся вблизи главной диагонали, т.е.aij0, если j > i + k1, i > j + k2, где k1, k2 < n.Числа k1 и k2 называют шириной верхней и нижней полуленты.Тогда k1 + k2 + 1  ширина ленты матрицы.Важным классом являются трехдиагональные матрицы (при k1  k2  1).Подобные системы уравнений возникают в задаче сплайнинтерполяции, при решении дифференциальных уравнений.Для решения задач с трехдиагональными матрицами существуютспециальные методы.Н.Новгород, 2010 г.Параллельные численные методы.4 из 46Трехдиагональные матрицыa1c1f1b2a2c2b3a3c3b4a4c4b5a5c5b6a6c6b7a7c7b8a8c8b9a9c9b10a10c10b11a11c11f11b12a12f12Н.Новгород, 2010 г.f2f3f4f5f6Параллельные численные методы.f7f8f9f105 из 46Метод прогонки (прямой ход)Предположим, что выполнено xi1ixi+iПодставим (1) в i-e уравнение системы, получим(1)(iai+ci)xi+bixi+1fiaii(2)Сравнивая (2) и выражение xii+1xi+1+i+1, получим bi i1 ai i  cif i  ai  i i1 ai i  ci(3)Из первого уравнения c1x1+b1x2f1 находим2b1/c1, 2f1/c1.Затем вычисляем i+1,i+1 ,используя (3) при i2,…,n1.Н.Новгород, 2010 г.Параллельные численные методы.6 из 46Метод прогонки (обратный ход)Определим xn из последнего уравненияf  an  nxn1nxn+nxn  nan n  cnanxn1+cnxnfnИспользуя xii+1xi+1+i+1, находим все xi, in1,…,1.ТеоремаМетод прогонки будет вычислительно устойчивым, если коэффициентысистемы уравнений удовлетворяют условиям диагональногопреобладания|c1||b1|, |cn||an|,ci  ai  bi , i2,…,n1.Н.Новгород, 2010 г.Параллельные численные методы.7 из 46Левая прогонкаРассмотренный в предыдущем пункте метод прогонки, при которомопределение xi происходит последовательно справа налево, называютправой прогонкой. Аналогично выписываются формулы левой прогонки Прямой ходf  bnan/cn, i   ai , nfn/cn, i  i i i1 , in1,…,2.ci  bi i 1ci  bii 1Обратный ходx1 f1  b12b1 2  c1Н.Новгород, 2010 г., xi+1i+1xi+i+1, i1,…,n1.Параллельные численные методы.8 из 46Левая прогонкаПредположим, что xi+1i+1xi+i+1исключим из i-го уравнение системы переменную xi+1aixi1+cixi+bi(i+1xi+i+1)fi aifi  bii 1xi xi 1 ci  bii 1ci  bii 1Сравнивая с xiixi1+i, получаем искомые формулы прямого и обратногохода левой прогонкиН.Новгород, 2010 г.Параллельные численные методы.9 из 46Встречная прогонкаКомбинация левой и правой прогонок дает метод встречной прогонки,которые допускает распараллеливание на два потока.Разделим систему между двумя потоками – первый будет оперироватьуравнениями с номерами 1ip, второй – уравнениями pin, p  n 2В первом потоке по формулам (1.4) вычисляются коэффициенты i,i,при 1ip; во втором потоке по формулам (1.8) вычисляютсякоэффициенты i,i, pin.При ip проводится сопряжение решений в форме (1.6) и (1.9): находимзначение xp из системыxpp+1xp+1+p+1xp+1p+1xp+p+1В первом потоке находим xi при 1i<p, а во втором все xi при p<in.Н.Новгород, 2010 г.Параллельные численные методы.10 из 46Встречная прогонка в двух потокахa1c1f1b2a2c2b3a3c3b4a4c4b5a5c5b6a6c6b7a7c7b8a8c8b9a9c9b10a10c10b11a11c11f11b12a12f12Н.Новгород, 2010 г.f2f3f4f5f6Параллельные численные методы.f7f8f9f1011 из 46Встречная прогонка в двух потокахa1c1f1a2c2f2b3a3c3b4a4c4b5a5c5b6a6c6b7a7c7b8a8c8b9a9c9b10a10c10f10b11a11f11f3f4f5f6f7f8f9b12Н.Новгород, 2010 г.Параллельные численные методы.a12f1212 из 46Встречная прогонка в двух потокахa1c1a2f1c2f2a3c3f3b4a4c4b5a5c5b6a6c6b7a7c7b8a8c8b9a9c9f9b10a10f10f4f5f6f7f8b11a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1213 из 46Встречная прогонка в двух потокахa1c1a2f1c2a3f2c3f3a4c4f4b5a5c5b6a6c6b7a7c7b8a8c8f8b9a9f9f5f6f7b10a10b11f10a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1214 из 46Встречная прогонка в двух потокахa1c1a2f1c2a3f2c3a4f3c4f4a5c5f5b6a6c6b7a7c7f7b8a8f8f6b9a9b10f9a10b11f10a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1215 из 46Встречная прогонка в двух потокахa1c1a2f1c2a3f2c3a4f3c4a5f4c5f5a6c6f6b7a7f7b8a8b9f8a9b10f9a10b11f10a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1216 из 46Встречная прогонка в двух потокахa1c1a2f1c2a3f2c3a4f3c4a5f4c5a6f5c6f6a7f7b8a8b9f8a9b10f9a10b11f10a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1217 из 46Встречная прогонка в двух потокахa1c1a2f1c2a3f2c3a4f3c4a5f4c5f5a6f6a7f7a8b9f8a9b10f9a10b11f10a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1218 из 46Встречная прогонка в двух потокахa1c1a2f1c2a3f2c3a4f3c4f4a5f5a6f6a7f7a8f8a9b10f9a10b11f10a11b12Н.Новгород, 2010 г.Параллельные численные методы.f11a12f1219 из 46Параллельная блочная прогонкаПрименим блочный подход к разделению данных: пусть каждый потокобрабатывает m  n / p строк матрицы A, т.е.

k-й поток обрабатываетстроки с номерами 1+(k–1)mikm. Будем предполагать, что числоуравнений в системе кратно числу потоков.В пределах полосы матрицы можно организовать исключениеподдиагональных элементов матрицы (прямой ход метода).вычитание строки i, умноженной на константу bi+1/ai, из строки i+1 с тем,чтобы результирующий коэффициент при неизвестной xi в (i+1)-й строкеоказался нулевымН.Новгород, 2010 г.Параллельные численные методы.20 из 46Параллельная блочная прогонкаa1c1d1b2a2c2b3a3c3b4a4c4b5a5c5b6a6c6b7a7c7b8a8c8b9a9c9b10a10c10b11a11c11d11b12a12d12Н.Новгород, 2010 г.d2d3d4d5d6Параллельные численные методы.d7d8d9d1021 из 46Параллельная блочная прогонкаa1c1d1a2c2d2b3a3c3b4a4c4b5a5f6d3d4c5d5a6c6d6b7a7c7b8a8c8b9a9f10Н.Новгород, 2010 г.Параллельные численные методы.d7d8c9d9a10c10d10b11a11c11d11b12a12d1222 из 46Параллельная блочная прогонкаa1c1a2d1c2d2a3c3b4a4c4b5a5f6f7d3d4c5a6d5c6d6a7c7b8a8c8b9a9f10Н.Новгород, 2010 г.d7d8c9a10d9c10d10f11a11c11d11f12b12a12d12Параллельные численные методы.23 из 46Параллельная блочная прогонкаa1c1a2d1c2a3d2c3d3a4c4b5a5f6f7f8d4c5a6d5c6a7d6c7a8c8b9a9f10f11f12Н.Новгород, 2010 г.d7Параллельные численные методы.d8c9a10d9c10a11d10c11d11a12d1224 из 46Параллельная блочная прогонкаЕсли исключение первым потоком поддиагональных переменных недобавит в матрицу новых коэффициентов, то исключениеподдиагональных элементов в остальных потоках приведет квозникновению столбца отличных от нуля коэффициентов: во всехблоках (кроме первого) число ненулевых элементов в строке неизменится, но изменится структура уравнений.

Модификации такжеподвергнутся элементы вектора правой части.Затем выполняется обратный ход алгоритма – каждый поток исключаетнаддиагональные элементы, начиная с последнегоН.Новгород, 2010 г.Параллельные численные методы.25 из 46Параллельная блочная прогонкаa1c1a2d1c2d2a3g3d3a4c4d4b5a5f6f7f8c5a6d5c6d6a7g7d7a8c8d8b9a9f10f11f12Н.Новгород, 2010 г.Параллельные численные методы.c9a10d9c10d10a11d11a12d1226 из 46Параллельная блочная прогонкаa1c1d1a2g2d2g3d3a4c4d4b5a5a3f6f7f8c5d5a6g6d6g7d7a8c8d8b9a9a7f10f11f12Н.Новгород, 2010 г.Параллельные численные методы.c9d9a10d10a11d11a12d1227 из 46Параллельная блочная прогонкаa1g1d1g2d2g3d3a4c4d4b5a5a2a3f6f7f8g5d5g6d6g7d7a8c8d8b9a9d9a6a7f10f11f12Н.Новгород, 2010 г.Параллельные численные методы.a10d10a11d11a12d1228 из 46Параллельная блочная прогонкаПосле выполнения обратного хода матрица стала блочной. Исключимиз нее внутренние строки каждой полосы, в результате получим системууравнения относительно части исходный неизвестныхДанная система будет содержать 2p уравнений, и будеттрехдиагональной.

Ее можно решить последовательным методомпрогонки. После того, как эта система будет решена, станут известнызначения неизвестных на границах полос разделения данных. Далееможно за один проход найти значения внутренних переменных.Н.Новгород, 2010 г.Параллельные численные методы.29 из 46Параллельная блочная прогонкаa1g1d1a4c4d4b5a5f8g5d5a8c8d8b9a9d9f12Н.Новгород, 2010 г.Параллельные численные методы.a12d1230 из 46Параллельная блочная прогонкаПосле выполнения обратного хода матрица стала блочной. Исключимиз нее внутренние строки каждой полосы, в результате получим системууравнения относительно части исходный неизвестныхДанная система будет содержать 2p уравнений, и будеттрехдиагональной. Ее можно решить последовательным методомпрогонки. После того, как эта система будет решена, станут известнызначения неизвестных на границах полос разделения данных.