Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями
Розглядається один із підходів до побудови передобумовлювача для методу спряжених градієнтів розв'язування СЛАР з розрідженими матрицями нерегулярної структури. Запропоновано та досліджено передобумовлювачі на основі методу паралельних перерізів. Рассматривается один из подходов к построению пр...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/46785 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями / О.М. Хіміч, В.В. Полянко // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 135-141. — Бібліогр.: 8 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859954342203752448 |
|---|---|
| author | Хіміч, О.М. Полянко, В.В. |
| author_facet | Хіміч, О.М. Полянко, В.В. |
| citation_txt | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями / О.М. Хіміч, В.В. Полянко // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 135-141. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Розглядається один із підходів до побудови передобумовлювача для методу спряжених градієнтів розв'язування СЛАР з розрідженими матрицями нерегулярної структури. Запропоновано та досліджено передобумовлювачі на основі методу паралельних перерізів.
Рассматривается один из подходов к построению предобуславливателя для метода сопряженных градиентов решения СЛАУ с разреженными матрицами нерегулярной структуры. Предложены и исследованы предобуславливатели на основе метода параллельных сечений.
Considered is one of approaches for construction a preconditioner for method of conjunctive gradients for solution SLAE with sparse matrices of irregular structure. Preconditioners, which are based on method of parallel section, is proposed and investigated.
|
| first_indexed | 2025-12-07T16:18:28Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2011, № 10 135
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Розглядається один із підходів до
побудови передобумовлювача для
методу спряжених градієнтів ро-
зв’язування СЛАР з розрідженими
матрицями нерегулярної струк-
тури. Запропоновано та дослід-
жено передобумовлювачі на осно-
ві методу паралельних перерізів.
О.М. Хіміч, В.В. Полянко, 2011
ÓÄÊ 519.6
Î.Ì. ղ̲×, Â.Â. ÏÎËßÍÊÎ
ÎÏÒÈ̲ÇÀÖ²ß ÏÀÐÀËÅËÜÍÎÃÎ
²ÒÅÐÀÖ²ÉÍÎÃÎ ÏÐÎÖÅÑÓ ÄËß
˲ͲÉÍÈÕ ÑÈÑÒÅÌ Ç ÐÎÇвÄÆÅÍÈÌÈ
ÌÀÒÐÈÖßÌÈ
Вступ. При розв’язуванні систем лінійних
алгебраїчних рівнянь (СЛАР) з матрицями
великих порядків нерідко реалізація на
комп’ютері прямих методів, навіть тих, що
враховують розрідженість матриці, може ви-
явитися досить складною і неефективною.
При реалізації паралельних алгоритмів дода-
ється також проблема збалансованості заван-
таження процесів та витрати на обмін дани-
ми між ними. Проблеми машинної реалізації
прямих методів пояснюються обмеженням
об’єму оперативної пам’яті, зниженням шви-
дкодії при використанні дискової пам’яті та
непередбачені витрати у випадку матриць з
нерегулярною структурою. З цієї точки зору
для розв’язування СЛАР доцільно викорис-
товувати швидкозбіжні ітераційні методи [1,
2].
Значний виграш від використання ітера-
ційних методів можна отримати у задачах з
розрідженими матрицями нерегулярної стру-
ктури. Особливо відчутною може бути різ-
ниця у випадку паралельних обчислень,
оскільки у цьому випадку параметри методу
можна підібрати таким чином, щоб мінімізу-
вати кількість як обчислювальних, так і ко-
мунікаційних операцій, а також ефективніше
балансувати завантаженість процесів.
Постановка задачі. Для знаходження на-
ближеного розв’язку лінійного операторного
рівняння
Аи = f (1)
О.М. ХІМІЧ, В.В. ПОЛЯНКО
136 Теорія оптимальних рішень. 2011, № 10
з невиродженим оператором А, заданим у дійсному гільбертовому просторі Н,
використаємо ітераційну схему [3]
Bxk+1 = αk+1(B – τk+1A)xk + (1 – αk+1)Bxk-1 + αk+1τk+1f,
k = 1, 2,…, (2)
Bx1 = (B – τ1A)x0 + τ1f, x0 ∈Н,
де ітераційні параметри αk+1 і τk+1 знаходяться за формулами
( )
( )
( )
( )
,1,...,2,1,
1
,
,
1
,...,1,0,
,
,
τ
1
1
11
1
1
1
=α=
ατ
τ
−=α
==
−
−−
+
+
+
k
rBw
rBw
k
wBw
rBw
kkk
kk
k
k
k
kk
kk
k
(3)
rk = A хk – f; Bwk = rk;
Для збіжності ітераційного процесу необхідно виконання умов
γ1В ≤ А ≤ γ2В, γ1 > 0, A = A
*
> 0, B = B
*
> 0,
Відомо [3], що якщо Н – скінченновимірний простір, тобто H = HN, то метод
збігається за кількість ітерацій, що не перевищує розмірність простору. В зага-
льному випадку для визначення кількості ітерацій справедлива оцінка
n ≥ n0(ε) = ln (0.5 ε) / ln ρ, де ( ) ( ),1/1 ξ+ξ−=ρ ξ = γ1 / γ2.
Швидкість збіжності ітераційного процесу визначається величиною конс-
тант енергетичної еквівалентності (ξ = γ1 / γ2) матриці А і передобумволювача В.
Умови закінчення ітераційних процесів, що гарантують дану точність ε, та
оцінки повної похибки розв’язку СЛАР випливають з [4].
Якщо для яких-небудь значень xk-1, xk і xk+1, виконується нерівність
BAx
xx
k
k
kk
1
11
1 −
++ τ
ε+
ε
≤
−
, (4)
то для наближеного розв’язку xk має місце оцінка
ε≤− uuxk / (5)
Для оцінки повної похибки розв’язків СЛАР з симетричною додатно визна-
ченою матрицею і наближеними вихідними даними , які задовольняють умовам
||∆A|| / ||A|| ≤ εA, ||∆f|| / ||f|| ≤ εf, ||∆A|| ||A-1|| < 1 (або ||∆A A
-1|| < 1),
має місце наступний результат.
Якщо чисельний розрахунок моделі виконаний ітераційним процесом (2) з
закінченням за умовою (4), то знайдений розв’язок задовольняє нерівності (5), а
повна похибка наближеного розв’язку оцінюється формулою
f
fA
T
Tk
H
u
ux
ε−
ε+εε+
+ε≤
−
1
))(1( ,
Побудова передобумовлювача. Кількість ітерацій та час знаходження
розв’язку системи (1) значною мірою залежить від вигляду та властивостей пе-
ОПТИМІЗАЦІЯ ПАРАЛЕЛЬНОГО ІТЕРАЦІЙНОГО…
Теорія оптимальних рішень. 2011, № 10 137
редобумовлювача В. Одним із найбільш ефективних способів, є побудова В з
вихідної матриці методом неповної факторизації [5], проте такий підхід у зага-
льному випадку не гарантує збереження додатної визначеності матриці, що є
необхідним для збіжності методу [1]. З іншого боку, при розв’язуванні СЛАР на
MIMD-комп’ютері важливим є побудувати В так, щоб мінімізувати кількість
міжпроцесорних обмінів та забезпечити збалансованість завантаження процесів.
З цієї точки зору оптимальною є блочно-діагональна матриця, де кількість
блоків відповідає числу процесів, що беруть участь у розв’язуванні задачі [6].
Це, у свою чергу, диктує спосіб розподілу даних для розв’язування СЛАР (1).
Матрицю А та вектори х і f доцільно розподіляти згідно з блочним способом:
якщо п – порядок матриці, р – число процесів, то початково перші (п/р) рядків
матриці А зберігаються у першому процесі, другі (п/р) рядків – у другому, р-ті
(п/р) рядків – у р-му. Аналогічний спосіб застосовуємо для векторів.
Блочно-діагональний передобумовлювач. Відомо [7], що до блочно-
діагонального вигляду з обрамленням матриця може бути зведена методом па-
ралельних перерізів. Портрет матриці складається з діагональних блоків нену-
льових елементів та відповідних їм блоків в останніх рядках та стовпчиках мат-
риці. Цей метод не відкидає ненульові елементи, а лише змінює їхнє розташу-
вання, тому система з такою перетвореною матрицею дає точний розв’язок
СЛАР. Але, якщо діагональні блоки можуть бути оброблені процесами незале-
жно, то у випадку з обрамленням число міжпроцесорних обмінів досить значне.
Тому для побудови передобумовлювача В до вихідної матриці застосуємо метод
паралельних перерізів з подальшим відкиданням обрамлення. При цьому варто
зазначити, що зберігається додатня визначеність матриці [6].
Розглянемо побудову передобумовлювача на прикладі. Візьмемо симетрич-
ну матрицю порядка 16, розподілену між 4 процесами блочним способом
(рис. 1). Сірим кольором позначено ненульові елементи або такі, які будуть мо-
дифіковуватися під час факторизації матриці; подвійні горизонтальні смуги роз-
діляють частини матриці, які зберігаються у різних процесах.
Оскільки серед стовпчиків наведеної матриці є такі, ненульові елементи
яких розподілені між різними процесами, то під час факторизації виникатиме
необхідність у міжпроцесорних обмінах. Сенс побудови блочно-діагональної
матриці полягає у тому, щоб звести матрицю до такого вигляду, де ненульові
елементи будь-якого стовпчика зберігаються в межах одного процесу. Дотри-
мання цієї умови дозволяє провести факторизацію матриці без використання
міжпроцесорних обмінів.
Розглянемо граф, що відповідає наведеній матриці (рис. 1). Кількість вер-
шин графа дорівнює порядку матриці. Дві вершини графа вважаються зв’язані
ребром, якщо елемент на перетині відповідного рядка і стовпчика є ненульовим.
За допомогою методу паралельних перерізів здійснимо перевпорядкування вер-
шин графа (рис. 2). Пунктиром позначено множини вершин розділювачів графа.
Нумерація вершин поза розділювачами організована відповідно до структури
О.М. ХІМІЧ, В.В. ПОЛЯНКО
138 Теорія оптимальних рішень. 2011, № 10
рівнів з коренем у псевдопериферійній вершині. Вершини з множин розділюва-
чів нумеруються в останню чергу.
РИС. 1. Портрет розрідженої матриці та відповідний граф
РИС. 2. Нумерація вершин графа і портрет матриці після впорядкування
За цією схемою кількість блоків між перерізами має бути на одиницю мен-
ша за число процесів. Таким чином досягається значне зменшення кількості мі-
жпроцесорних зв’язків, а, наприклад під час факторизації обміни не виконують-
ся зовсім. Як наслідок, при збільшенні кількості процесорів витрати на міжпро-
цесорні обміни зростатимуть повільніше, ніж для прямого методу.
Разом з тим, на відміну від прямого методу, при використанні методу пара-
лельних перерізів з’являється додаткове обмеження на максимально можливе
число процесів, що пов’язано з особливостями графа матриці. Так, кількість
процесів не може перевищувати половину довжини структури рівнів, побудова-
ної з основою у периферійній вершині. Має місце твердження.
5
3
12
1 11
9
4 4
1 10
1 1
2
16
15
14
13
7
8
6
14
2
8
115
13
3
7
4
1
10
11
112
9
16
6
5
ОПТИМІЗАЦІЯ ПАРАЛЕЛЬНОГО ІТЕРАЦІЙНОГО …
Теорія оптимальних рішень. 2011, № 10 139
Нехай n – порядок матриці, а z – кількість ненульових елемнтів. Тоді мак-
симальна кількість блоків, на які можна розбити матрицю методом паралельних
перерізів, не може перевищувати ( )znn
z
n
893
4
2 −+ .
Дійсно, через те, що метод паралельних перерізів не змінює кількість нену-
льових елементів z, то, оскільки внаслідок роботи методу всі ненульові елемен-
ти будуть знаходитися або в діагональних блоках, або у блоках останнього сто-
впчика і рядка блоків, то їх сумарне число складатиме s2
(3p – 2). Отже,
n
2(3p – 2) ≥ p2
z. Звідси отримаємо верхнє обмеження для p.
Слід також зазначити, що більш ефективним буде застосування пропонова-
ного методу для тих матриць, у графах яких структура рівнів розкладається на
блоки, що мають приблизно однакову кількість вершин, оскільки у цьому випа-
дку завантаження процесів буде найбільш рівномірним. З точки зору портрету
матриці це означає, що кількість ненульових елементів у кожному з рядків та
стовпчиків має бути приблизно однаковою. Одним із прикладів таких матриць є
стрічкові.
Поперемінно-трикутний метод (ПТМ) передбачає вибір передобумовлю-
вача у фактризованому вигляді:
В = (Е + ωR1)(Е + ωR2),
де R1 + R2 = А (збіжність методу та вибір ω див. у [3]).
Представлення А методом паралельних перерізів у блочно-діагональному
вигляді з обрамленням дозволяє побудувати ефективний паралельний алгоритм
розв’язування рівняння Вw = r з блочно-діагональними трикутними матрицями
R1 і R2.
Результати. Методи апробовано на кластерних комплексах Інституту кібе-
рнетики СКІТ та Інпарком. Дослідження проводились як на тестових задачах,
наприклад зі стрічковими матрицями, побудованими шляхом дискретизації ме-
тодом скінченних елементів змішаної крайової задачі для оператора Лапласа у
прямокутному паралелепіпеді (таблиця), так і на реальних задачах аналізу міц-
ності конструкцій [8].
ТАБЛИЦЯ. Часові характеристики блочно-діагонального передобумовлювача за
різної кількості процесів для матриці порядку 1000000 з шириною стрічки 1000
Процеси 1 2 4 8 16 24 32
Факторизація,с 3149,35 973,34 445,49 230,29 152,85 106,73 70,21
Ітерації,с 46,69 12,59 6,08 3,99 1,93 1,49 2,64
Всього, с 3196,04 985,93 451,57 234,28 154,78 108,22 72,85
Проведено дослідження залежності часу розв’язування від параметрів мат-
риці та кількості процесів, що брали участь в обчисленнях, отримано практичні
О.М. ХІМІЧ, В.В. ПОЛЯНКО
140 Теорія оптимальних рішень. 2011, № 10
характеристики прискорення алгоритму, побудовано їх залежності від числа
процесів (рис. 3.).
0
10
20
30
40
50
1 2 4 8 16 24 32
Процеси
П
р
и
с
к
о
р
е
н
н
я
100
10
1000
РИС. 3. Графіки залежності прискорення алгоритму від числа процесів для ви-
падків з різною шириною стрічки
Для ряду прикладних задач ітераційний метод, виявився більш ефективним
у порівнянні з прямим методом (рис 4).
РИС. 4. Порівняння прямого та ітераційного методів розв’язування СЛАР
з матрицею порядку 13710 у задачі аналізу міцності споруди АЕС
Висновки. Розглядається один із підходів до побудови передобумовлювача
для методу спряжених градієнтів розв’язування СЛАР з розрідженими матриця-
ми нерегулярної структури, виходячи з критерію мінімізації комунікаційних ви-
трат для паралельного алгоритму. Запропоновано блочно-діагональний та попе-
ремінно-трикутний передобумовлювач на основі методу паралельних перерізів.
Розглянуто питання збіжності ітераційного алгоритму, збалансованого розподі-
лу даних по процесах та паралельної організації обчислень. Результати експе-
ОПТИМІЗАЦІЯ ПАРАЛЕЛЬНОГО ІТЕРАЦІЙНОГО …
Теорія оптимальних рішень. 2011, № 10 141
риментів для тестових і прикладних задач показали високу ефективність пара-
лельного алгоритму.
А.Н Химич, В.В. Полянко
ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ИТЕРАЦИОННОГО ПРОЦЕССА
ДЛЯ ЛИНЕЙНЫХ СИСТЕМ С РАЗРЕЖЕННЫІМИ МАТРИЦАМИ
Рассматривается один из подходов к построению предобуславливателя для метода
сопряженных градиентов решения СЛАУ с разреженными матрицами нерегулярной
структуры. Предложено и исследовано предобуславливатели на основе метода параллельных
сечений.
A.N. Khimich, V.V. Polyanko
OPTIMIZATION OF PARALLEL ITERATIVE PROCESS FOR THE LINEAR SYSTEMS WITH
SPARSE MATRICES
Considered is one of approaches for construction a preconditioner for method of conjunctive gra-
dients for solution SLAE with sparse matrices of irregular structure. Preconditioners, which are
based on method of parallel section, is proposed and investigated.
1. Saad Y. Iterative Methods for Sparse Linear Systems. – PWS Publishing Company, 2000. –
448 р.
2. Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности –
Новосибирск: изд-во НГТУ, 2000. – 70 с.
3. Самарский А.А., Николаев Е.С. Методы решения сеточных – М.: Наука, 1978. – 592 с.
4. Химич А.Н., Яковлев М.Ф. О полной погрешности расчета линейных математических
моделей итерационными методами // Кибернетика и системный анализ. – 2002. - №5.
– С. 132-142.
5. Капорин И.Е., Коньшин И.Н. Постфильтрация множителей ІС2-разложения для
балансировки параллельного предобусловливания // Журнал вычислительной
математики и математической физики. – 2009. – 49, № 6. – С. 940 – 957.
6. Полянко В.В. Оптимізація структури розрідженої матриці для побудови ефективного
обчислювального алгоритму // Теорія оптимальних рішень. – 2010. – №9 – С. 45 – 53.
7. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. –
М.: Мир, 1984. – 333 с.
8. ЛИРА 9.4. Примеры расчета и проектирования / Ю.В. Гензерский, Я.Е. Слободян,
В.П. Титок и др. – Киев: Изд-во НИИАСС, 2006. – 124 с.
Получено 29.03.2011
|
| id | nasplib_isofts_kiev_ua-123456789-46785 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:18:28Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Хіміч, О.М. Полянко, В.В. 2013-07-06T17:30:14Z 2013-07-06T17:30:14Z 2011 Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями / О.М. Хіміч, В.В. Полянко // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 135-141. — Бібліогр.: 8 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46785 519.6 Розглядається один із підходів до побудови передобумовлювача для методу спряжених градієнтів розв'язування СЛАР з розрідженими матрицями нерегулярної структури. Запропоновано та досліджено передобумовлювачі на основі методу паралельних перерізів. Рассматривается один из подходов к построению предобуславливателя для метода сопряженных градиентов решения СЛАУ с разреженными матрицами нерегулярной структуры. Предложены и исследованы предобуславливатели на основе метода параллельных сечений. Considered is one of approaches for construction a preconditioner for method of conjunctive gradients for solution SLAE with sparse matrices of irregular structure. Preconditioners, which are based on method of parallel section, is proposed and investigated. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями Оптимизация параллельного итерационного процесса для линейных систем с разреженными матрицами Optimization of parallel iterative process for the linear systems with sparse matrices Article published earlier |
| spellingShingle | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями Хіміч, О.М. Полянко, В.В. |
| title | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями |
| title_alt | Оптимизация параллельного итерационного процесса для линейных систем с разреженными матрицами Optimization of parallel iterative process for the linear systems with sparse matrices |
| title_full | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями |
| title_fullStr | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями |
| title_full_unstemmed | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями |
| title_short | Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями |
| title_sort | оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46785 |
| work_keys_str_mv | AT hímíčom optimízacíâparalelʹnogoíteracíinogoprocesudlâlíníinihsistemzrozrídženimimatricâmi AT polânkovv optimízacíâparalelʹnogoíteracíinogoprocesudlâlíníinihsistemzrozrídženimimatricâmi AT hímíčom optimizaciâparallelʹnogoiteracionnogoprocessadlâlineinyhsistemsrazrežennymimatricami AT polânkovv optimizaciâparallelʹnogoiteracionnogoprocessadlâlineinyhsistemsrazrežennymimatricami AT hímíčom optimizationofparalleliterativeprocessforthelinearsystemswithsparsematrices AT polânkovv optimizationofparalleliterativeprocessforthelinearsystemswithsparsematrices |