Про паралельні алгоритми факторизації розріджених матриць

Розглядаються блочні циклічні паралельні алгоритми факторизації дійсних квадратних розріджених невироджених матриць різної структури – стрічкової, профільної, нерегулярної тощо. Запропоновано блочно-циклічний паралельний алгоритм LU-розвинення стрічкової несиметричної матриці....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Попов, О.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Назва видання:	Компьютерная математика
Теми:	Математические модели в биологии и медицине
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/84755
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Про паралельні алгоритми факторизації розріджених матриць / О.В. Попов // Компьютерная математика. — 2013. — № 2. — С. 115-124. — Бібліогр.: 8 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84755
record_format	dspace
spelling	irk-123456789-847552015-07-15T03:02:09Z Про паралельні алгоритми факторизації розріджених матриць Попов, О.В. Математические модели в биологии и медицине Розглядаються блочні циклічні паралельні алгоритми факторизації дійсних квадратних розріджених невироджених матриць різної структури – стрічкової, профільної, нерегулярної тощо. Запропоновано блочно-циклічний паралельний алгоритм LU-розвинення стрічкової несиметричної матриці. Рассматриваются блочные циклические параллельные алгоритмы факторизации невырожденных действительных квадратных разреженных матриц различной структуры – ленточной, профильной, нерегулярной и др. Предложен блочно-циклический параллельный алгоритм LU-разложения ленточной несимметричной матрицы. The block cyclic parallel algorithms of real square sparse nonsingular matrices of different structure (band, profile, irregular and others like that) decomposition are dealt with. The block cyclic parallel algorithm of LU-decomposition of band asymmetrical matrix is offered. 2013 Article Про паралельні алгоритми факторизації розріджених матриць / О.В. Попов // Компьютерная математика. — 2013. — № 2. — С. 115-124. — Бібліогр.: 8 назв. — укр. ХХХХ-0003 http://dspace.nbuv.gov.ua/handle/123456789/84755 519.6 uk Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Математические модели в биологии и медицине Математические модели в биологии и медицине
spellingShingle	Математические модели в биологии и медицине Математические модели в биологии и медицине Попов, О.В. Про паралельні алгоритми факторизації розріджених матриць Компьютерная математика
description	Розглядаються блочні циклічні паралельні алгоритми факторизації дійсних квадратних розріджених невироджених матриць різної структури – стрічкової, профільної, нерегулярної тощо. Запропоновано блочно-циклічний паралельний алгоритм LU-розвинення стрічкової несиметричної матриці.
format	Article
author	Попов, О.В.
author_facet	Попов, О.В.
author_sort	Попов, О.В.
title	Про паралельні алгоритми факторизації розріджених матриць
title_short	Про паралельні алгоритми факторизації розріджених матриць
title_full	Про паралельні алгоритми факторизації розріджених матриць
title_fullStr	Про паралельні алгоритми факторизації розріджених матриць
title_full_unstemmed	Про паралельні алгоритми факторизації розріджених матриць
title_sort	про паралельні алгоритми факторизації розріджених матриць
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
topic_facet	Математические модели в биологии и медицине
url	http://dspace.nbuv.gov.ua/handle/123456789/84755
citation_txt	Про паралельні алгоритми факторизації розріджених матриць / О.В. Попов // Компьютерная математика. — 2013. — № 2. — С. 115-124. — Бібліогр.: 8 назв. — укр.
series	Компьютерная математика
work_keys_str_mv	AT popovov proparalelʹníalgoritmifaktorizacíírozrídženihmatricʹ
first_indexed	2025-07-06T11:53:46Z
last_indexed	2025-07-06T11:53:46Z
_version_	1836898401405370368
fulltext	Компьютерная математика. 2013, № 2 115 Розглядаються блочні циклічні паралельні алгоритми фактори- зації дійсних квадратних розрід- жених невироджених матриць різної структури – стрічкової, профільної, нерегулярної тощо. Запропоновано блочно-циклічний паралельний алгоритм LU-розви- нення стрічкової несиметричної матриці. © О.В. Попов, 2013 Компьютерная математика. 2013, № 2 116 УДК 519.6 О.В. ПОПОВ ПРО ПАРАЛЕЛЬНІ АЛГОРИТМИ ФАКТОРИЗАЦІЇ РОЗРІДЖЕНИХ МАТРИЦЬ Вступ. Математичне моделювання та пов’я-заний з ним комп’ютерний експеримент нині один з основних засобів вивчення різно-манітних явищ і об’єктів природи, процесів і об’єктів у різних галузях науки та техніки, про-цесів у суспільстві, економіці тощо. При чисельному моделюванні часто вини- кають, наприклад, при використанні триви-мірних моделей, розрахункові (дискретні або напівдискретні) задачі з надвеликою кіль-кістю рівнянь, яка може перевищувати 107. Причому дані (матриці) цих задач мають розріджену структуру, тобто кількість нену-льових елементів значно менша (не переви-щує 5%) загальної кількості елементів матри-ці. Зберігання таких даних, незважаючи на розрідженість, потребує значних обсягів комп’ютерної пам’яті, які можуть переви-щувати 1 Tb. Задачі такого обсягу вини-кають, зокрема, при використанні тривимір-них моделей. Зростання параметрів задач, що розв’я- зуються, розрахунок на комп’ютерах більш повних моделей об’єктів, процесів, явищ вимагає відповідного зростання продуктив- ності комп’ютерів. Вимоги до високо- продуктивних обчислень набагато випере- джають можливості персональних комп’ю- терів, навіть незважаючи на багатоядерність процесорів. На сьогодні зростання продуктивності обчислень досягається за рахунок розпарале- лювання, яке базується на використанні ком- п’ютерів з багатьма процесорними пристро- ями, зокрема з багатоядерними процесорами. ПРО ПАРАЛЕЛЬНІ АЛГОРИТМИ ФАКТОРИЗАЦІЇ РОЗРІДЖЕНИХ МАТРИЦЬ Компьютерная математика. 2013, № 2 117 В цих комп’ютерах, як правило, реалізується MIMD-архітектура (архі- тектура з множинним потоком команд і даних). За останні роки також набули поширення гібридні обчислювальні системи, в яких використовуються сопро- цесори, наприклад, графічні процесори, для прискорення обчислень при вико- нанні великих обсягів однорідних арифметичних операцій. На таких сопроце- сорах-прискорювачах, як правило, реалізується SIMD-архітектура паралельних обчислень. Такі комп’ютери гібридної архітектури вже зайняли провідні позиції у світовому рейтингу найпродуктивніших комп’ютерів TOP500 [1]. Розв’язування розрахункових задач у переважній більшості потребує розв’я- зування систем лінійних алгебраїчних задач (СЛАР) з розрідженими матрицями (див., наприклад, [2, 3]). У свою чергу при розв’язуванні цих СЛАР прямими методами, як правило, використовується факторизація (розвинення) матриці в добуток матриць (в більшості випадків трикутних та діагональних). Часто розвинення матриці в добуток трикутних матриць використовується і в ітера- ційних методах розв’язування СЛАР. Структура розріджених матриць визначається нумерацією невідомих і може бути регулярною (наприклад, стрічковою) або нерегулярною. Мета цієї роботи – дослідження алгоритмів паралельних і розподілених обчислень для факторизації розріджених матриць різної структури. Зокрема, узгодження структури розрідженої матриці та архітектури обчислювальної системи з метою ефективної реалізації алгоритму. Постановка задачі. Розглянемо СЛАР Ах = b, (1) де в загальному випадку А – дійсна квадратна матриця порядку n; b – матриця правої частини розміру n×q (або n-вимірний вектор). Розв’язування цієї СЛАР полягає у знаходженні такого розв’язку х (матриці розмірності n×q або n-вимірного вектора), щоб рівняння (1) перетворювалося в тотожність. Якщо матриця А системи невироджена (тобто її визначник │A│ ≡ det(A) ≠ 0), то розв’язок СЛАР (1) існує і єдиний. Якщо матриця симетрична, то розгля- датимемо випадок, коли вона додатно визначена. Розглядаються СЛАР як з симетричними, так і з несиметричними розрід- женими матрицями. Тобто, як зазначалося вище, з матрицями, загальна кількість ненульових елементів (ΗA) яких значно менша загальної кількості всіх елементів (що дорівнює n2). Структури розріджених матриць. Структура розрідженої матриці визнача- ється нумерацією невідомих і може бути регулярною (стрічковою, профільною, блочно-діагональною з обрамленням тощо) або нерегулярною (див. рис. 1). Зміна нумерації невідомих викликає зміну структури матриць, яку можна таким чином оптимізувати за якимось критерієм. Позначимо ηC(i) – кількість ненульових елементів в i-у рядку матриці C, ∑ = =Η n i AA i 1 )(η , ml(i) = i – min{j \| aij≠0}, mu(i) = max{j \| aij≠0} – i, )(max 1 imm l ni l ≤≤ = , )(max 1 imm u ni u ≤≤ = . Зауважимо, що у випадку симетричної матриці ml = mu = m. Множини значень ml (i) та mu (i), i = 1, 2, …, n, визначають профіль матриці A. О.В. ПОПОВ Компьютерная математика. 2013, № 2 118 РИС. 1. Приклади структур розріджених матриць Серед різних розріджених матриць доцільно виділити матриці, ненульові елементи яких концентруються біля головної діагоналі (рис. 1, а, 1, б), тобто коли ml << n та mu << n. Такі матриці часто називають профільними. А якщо )(min iml niml ≤< та )(min 1 imu mni u−≤≤ мало відрізняються (на 5–10 %) відповідно від ml і mu, то таку матрицю доцільно вважати стрічковою з шириною стрічки ml + mu +1. Якщо ширина стрічки не перевищує 300, то матрицю вважають вузькою стрічковою. Розріджені матриці з таким структурами переважно є вихідними або отримуються в результаті оптимізації за алгоритмами фактор- дерев або Катхілл – Маккі [2]. При використанні алгоритму паралельних перерізів [2] для оптимізації структури матриці отримують матрицю із структурою, яку показано на рис. 1, б, 1, в і яку часто називають блочно-діагональною з обрамленням. У цьому випадку ненульові елементи розташовуються в досить великих діагональних блоках та в блоках обрамлення. Часто також доцільно оптимізувати структуру цих діагональних блоків. ПРО ПАРАЛЕЛЬНІ АЛГОРИТМИ ФАКТОРИЗАЦІЇ РОЗРІДЖЕНИХ МАТРИЦЬ Компьютерная математика. 2013, № 2 119 Алгоритм мінімальної степені [2] дозволяє суттєво зменшити загальну кількість елементів у профілі матриці, але оптимізована структура матриці втрачає регулярність і в ній з’являються довгі рядки (або стовпчики) такі, що ml та / або mu можуть перевищувати 0,5n (рис. 1, г). Розв’язування СЛАР з розрідженими матрицями. Перші детальні дослід- ження методів розв’язування СЛАР з розрідженими матрицями почали проводи- тися з появою і розвитком ЕОМ. Через обмежені можливості ЕОМ 50–70 років минулого століття спочатку розвивалися ітераційні методи. Проте як збіжність, так і ефективність ітераційних методів істотно залежить від знання апріорної інформації про властивості матриці задачі. Крім того в разі багаторазового розв’язування СЛАР з однією і тією ж матрицею і різними правими частинами прямі методи виявляються набагато ефективнішими. Тому в міру нарощування обчислювальних ресурсів комп’ютерів все більш широкий розвиток отримують алгоритми прямих методів розв’язування СЛАР з розрідженими матрицями. У 80-і роки минулого століття опубліковано низку фундаментальних робіт, які висвітлювали основні досягнення в цьому напрямку. В монографії [2] описана більшість основних методів розв’язування СЛАР з розрідженими симетричними додатно визначеними матрицями великих розмірів, а монографія [3] присвячена проблемам реалізації наведених методів на паралельних комп’ютерах. На основі накопиченого матеріалу визначено низку ефективних алгоритмів розв’язування СЛАР з розрідженими матрицями, способи зберігання розріджених даних, а також різні алгоритми оптимізації заповнення (див., наприклад, [4], де наведено широкий огляд сучасних алгоритмів розв’язування СЛАР з розрідженими матрицями). При використанні прямих методів матриця задачі факторизується в добуток трикутних або трикутних та діагональної матриць. Також варто зазначити, що збіжність ітераційних методів залежить від використовуваної схеми (явної або неявної) і є невисокою для явних схем. Використання неявних схем з перед- обумовлювачем дозволяє зменшити кількість ітерацій, але потребує, як правило, факторизації матриці-передобумовлювача, яка також має розріджену структуру. Отже, розв’язування системи (1) полягає у розв’язуванні трьох підзадач: − розвинення (факторизація) матриці системи A = LU, або A = LLT, або A = LDLT, (2) де L – нижня трикутна матриця з одиницями на головній діагоналі (крім випадку LLT-розвинення), U – верхня трикутна матриця, D – діагональна матриця; − розв’язування СЛАР з нижньою трикутною матрицею Ly = b; − розв’язування СЛАР з верхньою трикутною матрицею Ux = y, або LTx = y, або LTx = 1 .D y− О.В. ПОПОВ Компьютерная математика. 2013, № 2 120 Розвинення розріджених матриць. Розвинення симетричних матриць проводиться методом Холецького, а розвинення несиметричних матриць – методом Гаусса. При цьому у випадку несиметричних матриць, якщо відсутня діагональна перевага (коли модуль кожного діагонального елемента перевищує суму модулів позадіагональних елементів відповідного рядка або стовпчика), необхідно проводити хоча б частковий вибір головного елемента. Наприклад, елементи LDLT-розвинення з (2) можна обчислити за формулами (для k = 1, 2, …, n): lkj = tkj/dj, j=1,…,k−1, ∑ − = −= 1 1 k j kjkjkkk tlad , ∑ − = −= 1 1 i j ijkjikik tlat , i = k+1,…,n. (3) LU-розвинення несиметричної матриці може бути виконане за формулами (для i, j = k+1, …, n, k = 1, 2, …, n): )1( −= k kkkk au , )1( −= k kjkj au , kk k ikik uam /)1( −= , ikkj k ij k ij muaa −= − )1()( . (4) Тут mij – елементи матриці L, причому у випадку виконання розвинення без вибору головного елемента mij ≡ l ij. З формули (4) легко отримати формули для LDLT-розвинення симетричної матриці алгоритму метода Холецького у формі зовнішніх добутків (для i = k+1, …, n, k = 1, 2, …, n): )1( −= k kkk ad , k k ikik dal /)1( −= , )1()1()( −− −= k jkik k ij k ij alaa , j = k+1, …, i. (5) У випадку розріджених матриць загальний обсяг обчислень істотно скорочується, якщо обчислення за формулами або (3), або (4), або (5) виконувати тільки з явно ненульовими елементами розвинення матриці. Розглянемо, наприклад, обчислення за формулами (3). Позначимо Zi (L) – множина других індексів ненульових піддіагональних елементів i-го рядка нижньої трикутної матриці L. Тоді підсумовування в формулах (3) ведеться лише для k ∈ Zi(L) або k ∈ Zi(L)∩Zj(L). Таким чином, елемент l ij = 0, якщо aij = 0 та Zi(L)∩Zj(L) = ∅. (6) Якщо в рядках нижньої трикутної матриці L міститься багато довільно розташованих нульових елементів, то при обчисленнях за формулами (3) сут- тєво зростають накладні витрати на пошук відповідних пар ненульових елемен- тів. У цьому випадку доцільно використовувати інший порядок обчислень елементів трикутного розвинення – за формулами (5). У випадку несиметричної матриці маємо аналогічні (6) умови того, що 0)( =k ija , а отже і l ij = 0 або uij = 0, aij = 0 та Zi(L)∩Zj(U) = ∅. (7) Легко бачити, що всі нульові елементи вихідної матриці, які розташовано в рядках ліворуч або в стовпчиках вище за перший ненульовий елемент залишаються нульовими у відповідному трикутному розвиненні. Тому ці елементи в обчисленнях участь не беруть, а перші ненульові елементи – ліві ПРО ПАРАЛЕЛЬНІ АЛГОРИТМИ ФАКТОРИЗАЦІЇ РОЗРІДЖЕНИХ МАТРИЦЬ Компьютерная математика. 2013, № 2 121 (в рядках) або верхні (в стовпчиках) – визначають профіль розрідженої матриці. Формули (6), (7) свідчать, що профілі вихідної матриці та її трикутного розви- нення збігаються. Водночас заповнення профілю трикутного розвинення розрідженої матриці суттєво зростає у порівнянні з вихідною розрідженою матрицею. Заповнення профілю трикутного розвинення розрідженої матриці залежить від зв’язків між невідомими системи і регулюється їх нумерацією. Існують (див., наприклад [2]) різні алгоритми переупорядковування невідомих, які дозволяють як зменшити заповнення, так і поліпшити інші характеристики профілю трикутного розвинення, які впливають на загальну кількість арифме- тичних операцій при розв’язуванні СЛАР. Паралельні алгоритми трикутного розвинення розріджених симетрич- них матриць. Паралельні алгоритми дослідження та розв’язування задач ліній- ної алгебри з симетричними матрицями, в тому числі трикутного розвинення розрідженої симетричної матриці, досить повно представлено в монографії [5]. Історично перші паралельні алгоритми трикутного розвинення розрідженої симетричної матриці розроблено для блочно-діагонального з обрамленням представлення такої матриці [6]. Досить детально такий же алгоритм описано також в [5] для розв’язування задач з вузькими стрічковими матрицями. Проте можливості паралельних алгоритмів цієї групи обмежені через появу в процесі розвинення зведеної матриці, порядок якої дорівнює кількості рядків (стовпчиків) в обрамленні. Трикутне розвинення такої матриці може бути виконано або в послідовному режимі (якщо її порядок порівняно невеликий), або в паралельному, але для цього необхідно перерозподілити дані між процесорними пристроями та використати паралельний алгоритм для щільних симетричних матриць. Крім того, при розвиненні матриць з вузькою стрічкою необхідно таку матрицю, використовуючи алгоритм паралельних перерізів, привести до блочно-діагональної матриці з обрамленням, що збільшує в 4 рази кількість арифметичних операцій. Тому ефективність такого алгоритму обмежена зверху 25 %. У роботі [7] запропоновано рядково-циклічний паралельний алгоритм методу Холецького для стрічкових симетричних матриць, в якому реалізовано формули (3). Надалі на базі цього алгоритму розроблено одновимірний блочний циклічний алгоритм методу Холецького для стрічкових і профільних симетрич- них матриць (див., наприклад [5]). Цей алгоритм дозволяє проводити обчислення лише з явно ненульовими елементами матриць (вихідної та трикут- ного розвинення. Проте накладні витрати на пошук таких елементів можуть перевищити виграш від скорочення кількості арифметичних операцій. Ефективне використання одновимірних блочних циклічних алгоритмів мож- ливо при високій збалансованості завантаження процесів, щоб не було простоїв окремих процесів при виконанні обчислень. У загальному випадку цього можна досягти для стрічкових матриць. Якщо ж кількість елементів, з якими проводяться операції, в рядках профілю матриці істотно відрізняються, то обчислення можуть потребувати часу, який порівнянний з випадком стрічкової матриці з шириною стрічки, що дорівнює максимальній кількості елементів профілю в одному рядку. О.В. ПОПОВ Компьютерная математика. 2013, № 2 122 Для розріджених симетричних матриць довільної структури часто можна досягти кращої збалансованості, якщо виконувати розвинення за формулами (5). У цьому випадку при використанні схеми завдання ненульових елементів група- ми і одновимірного блочного циклічного або рядково-циклічного розподілу даних (верхнього трикутника вихідної матриці та верхньої трикутної матриці розвинення) між процесами можна досягти більш рівномірного завантаження процесів та подолати «проблему довгих рядків», яка згадувалась вище. Відпо- відний одновимірний блочний циклічний алгоритм запропоновано в [8]. В роботах [5, 8] досліджено ефективність запропонованих блочного та одновимірних блочних циклічних паралельних алгоритмів факторизації розріджених симе-тричних матриць. У роботі [8] доведено, що ефективність цих паралельних алгоритмів обмежена зверху ( 2 1 1 ( ) n L i O i = = η∑ ). 2 c o 1 11 1 1 log 1 ( ) ( ) n n p L L i i p p p t n t E i i O O t s t= =  −  ≤ − η + + η      ∑ ∑ , (8) де p – кількість паралельних процесів, s – розмір блоку, t – середній час виконання однієї арифметичної операції (додавання або множення) з плаваючою комою, tо – час, необхідний для обміну одним машинним словом між двома процесами, tс – час, необхідний для синхронізації двох процесів. Виходячи з оцінки (8), для стрічкових матриць маємо оцінку [5]:             +++−−≈ t t smt t m pp m sp E со p 1log)1)(1(2 1 2 , а для блочного алгоритму розвинення вузької стрічкової матриці маємо [5]:             ++−−−−≈ t t mt tp m p n p m E c 2 o p 2 23 187 16 1 8 1 25,0 . Враховуючи сучасні тенденції розвитку технічних та програмних засобів для високопродуктивних обчислень, зокрема розробку виробниками технічних засобів також і програмного забезпечення, доцільно модифікувати запропо- новані алгоритми так, щоб переважну більшість операцій зводилась до мат- рично-матричних або матрично-векторних операцій із щільними блоками елементів розріджених матриць. Такий підхід буде використано далі для випад- ку несиметричної матриці. Блочний циклічний паралельний алгоритм розвинення стрічкової несиметричної матриці. Формули (5) LU-розвинення стрічкової несиметричної матриці з частковим вибором по стовпчику головного елемента можна записати в блочній формі. Для K = 1, 2, …, N : ( 0,5) ( ) ( 1),K K K K KA P A− −= ( ) ( 0,5) , , , , , 1, , min{ , },K K I K K K I K lL U A I K K K N−= = + + ΜK ПРО ПАРАЛЕЛЬНІ АЛГОРИТМИ ФАКТОРИЗАЦІЇ РОЗРІДЖЕНИХ МАТРИЦЬ Компьютерная математика. 2013, № 2 123 ( ) ( 0,5) , , , , 1, , min{ , },K K K K K J K J uL U A J K K N−= = + + ΜK ( ) ( 0,5) ( ) , , , , , 1, , min{ , },K K K I J I J I K K J lA A L U I K K N−= − = + + ΜK 1, , min{ , },uJ K K N= + + ΜK (9) де N = (n – 1)/s+1 (s – розмір блока, a – ціла частина числа a), Ml = = (ml –1)/s + 1, Mu = (mu+ml – 1)/s+1, )5,0()1( , −− K K K K AA – права нижня під- матриця порядку n – (K–1)s, AA ≡)0( 0 , P(K) – матриця перестановок на K-у кроці, ( ) ( ) , , ,, ,K J I J I J I JA L U – у загальному випадку (крім, можливо, останніх рядка та стовп- чика блоків) квадратні блоки порядку s. За рахунок перестановок збільшується порівняно з матрицею A кількість наддіагоналей верхньої трикутної матриці U – до mu+ml. Водночас для економії обчислень на K-у кроці не виконуються перестановки в матрицях )( , J JIL при I ≥ K та J < K. Необхідно зауважити, що згідно (9) на K-у кроці модифікується тільки прямокутна підматриця розмірами (ml+s)×(mu+ml+s) (рис. 2). РИС. 2. Схема блочного алгоритму О.В. ПОПОВ Компьютерная математика. 2013, № 2 124 Аналіз формул (9) засвідчив, що для реалізації більшості обчислень (крім обчислення блоків )( , K KIL ) можна використати програмні модулі для матрично- матричних операцій від розробників технічних засобів. Ці модулі можуть ефективно виконуватись також на прискорювачах-сопроцесорах. Для паралельного алгоритму рядки блоків вихідної матриці A та матриць розвинення L, U розподіляються циклічно між процесами так, щоб кожен процес мав хоча б один рядок блоків, які модифікуються на даному кроці. Називатимемо на K-у кроці провідним рядком або стовпчиком блоків відповідно K-й рядок або стовпчик, а провідним процесом процес, якому розпо- ділено провідний рядок блоків. Тоді блочно-циклічний паралельний алгоритм полягає у наступній послідовності операцій. В циклі по K = 1, 2, …, N. 1. Формування підматриці, що модифікується )5,0( −K KA та обчислення блоків розвинення )( , K KKU і )( , K KIL , I = K, …, K+M l. 2. Обчислення згідно (9) блоків розвинення JKU , провідного рядка; виконується провідним процесом. 3. Розсилка всім процесам провідного рядка блоків. 4. Модифікація (s-рангова) згідно (9) елементів блоків )( , K JIA прямокутної підматриці, що модифікується; виконується паралельно всіма процесами. Порядок і ефективність виконання першого кроку переважно залежить від множини елементів стовпчика матриці, на якій виконується вибір головного елемента. Найбільш ефективним є варіант, коли головний елемент вибирається тільки серед елементів стовпчика, які розподілено провідному процесу. Тоді провідний процес формує свою частину підматриці )5,0( −K KA , обчислює блоки розвинення )( , K KKL і )( , K KKU та розсилає блок )( , K KKU іншим процесам, після цього всі процеси обчислюють згідно (9) розподілені їм блоки розвинення )( , K KIL , I = K, …, K+M l. Висновок. Запропоновані блочно-циклічні паралельні алгоритми фактори- зації розріджених матриць різної структури є досить ефективними, що підтвер- дили результати їх апробації на різних кластерних комплексах [5, 7, 8]. Подальший їх розвиток пов’язаний з використанням програмних модулів від виробників технічних засобів, що реалізують матрично-векторні та матрично- матричні операції, у тому числі на комп’ютерах гібридної архітектури. Актуаль- ним є розповсюдження такого підходу із стрічкових матриць на матриці інших розріджених структур. ПРО ПАРАЛЕЛЬНІ АЛГОРИТМИ ФАКТОРИЗАЦІЇ РОЗРІДЖЕНИХ МАТРИЦЬ Компьютерная математика. 2013, № 2 125 Роботу виконано за договором В.К.150.12.13 «Розробка та впровадження інтелектуальних інформаційних технологій грід-обчислень для математичного моделювання процесів, що протікають при зварюванні та споріднених процесах» в рамках Державної цільової науково-технічної програми «Впровад- ження і застосування грід-технологій на 2009-2013 роки». А.В. Попов О ПАРАЛЛЕЛЬНЫХ АЛГОРИТМАХ ФАКТОРИЗАЦИИ РАЗРЕЖЕННЫХ МАТРИЦ Рассматриваются блочные циклические параллельные алгоритмы факторизации невырожден- ных действительных квадратных разреженных матриц различной структуры – ленточной, профильной, нерегулярной и др. Предложен блочно-циклический параллельный алгоритм LU-разложения ленточной несимметричной матрицы. A.V. Popov ON THE PARALLEL ALGORITHMS OF SPARSE MATRICES FACTORIZATION The block cyclic parallel algorithms of real square sparse nonsingular matrices of different structure (band, profile, irregular and others like that) decomposition are dealt with. The block cyclic parallel algorithm of LU-decomposition of band asymmetrical matrix is offered. 1. http://www.top500.org 2. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. – М.: Мир, 1984. – 334 с. 3. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем – М.: Мир, 1991. – 300 с. 4. Глушакова Т.Н., Эксаревская М.Е. Методы работы с разреженными матрицами произ- вольного типа. – Воронеж: Воронежский гос. ун-т, 2005. – 44 с. 5. Химич А.Н., Молчанов И.Н., Попов А.В. и др. Параллельные алгоритмы решения задач вычислительной математики – Киев: Наукова думка, 2008. – 248 с. 6. http://www.netlib.org/scalapack 7. Попов А.В., Химич А.Н. Параллельный алгоритм решения системы линейных алгебра- ических уравнений с ленточной симметричной матрицей // Компьютерная математика. – 2005. – № 2. – С. 52–59. 8. Химич А.Н., Попов А.В., Полянко В.В. Алгоритмы параллельных вычислений для задач линейной алгебры с матрицами нерегулярной структуры // Кибернетика и системный анализ. – 2011. – № 6. – С. 159–174. Одержано 11.10.2013 Про автора: Попов Олександр Володимирович, кандидат фізико-математичних наук, старший науковий співробітник О.В. ПОПОВ Компьютерная математика. 2013, № 2 126 Інституту кібернетики імені В.М. Глушкова НАН України.

Про паралельні алгоритми факторизації розріджених матриць

Репозитарії

Схожі ресурси