Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Хіміч, О.М., Сидорук, В.А.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/111517
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею / О.М. Хіміч, В.А. Сидорук // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 106-113. — Бібліогр.: 9 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-111517
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1115172025-02-09T13:04:03Z Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею Гибридный алгоритм для линейной задачи наименьших квадратов с разреженной полуопределенной матрицей Hybrid algorithm for linear least squares problem with sparse semidefinite matrix Хіміч, О.М. Сидорук, В.А. Запропоновано алгоритм отримання нормального псевдорозв’язку систем лінійних рівнянь з розрідженими симетричними додатно-напіввизначеними матрицями на комп’ютерах гібридної архітектури – комп'ютерах з багатоядерними процесорами і графічними прискорювачами. Алгоритм апробовано на низці тестових задач. Показана його ефективність. Предложен алгоритм получения нормального псевдорешения системы линейных уравнений с разреженными симметричными положительно-полуопределенными матрицами на компьютерах гибридной архитектуры – компьютерах с многоядерными процессорами и графическими ускорителями. Алгоритм апробирован на ряде тестовых задач. Показана его эффективность. An algorithm of obtaining the normal pseudosolution of systems of linear equations with sparse symmetric positive-semidefinite matrices on hybrid architecture computers – computers with multicore processors and graphics accelerators is proposed. The algorithm is tested on a set of test problems. Shown its effectiveness. 2014 Article Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею / О.М. Хіміч, В.А. Сидорук // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 106-113. — Бібліогр.: 9 назв. — укр. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/111517 519.6 uk Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Запропоновано алгоритм отримання нормального псевдорозв’язку систем лінійних рівнянь з розрідженими симетричними додатно-напіввизначеними матрицями на комп’ютерах гібридної архітектури – комп'ютерах з багатоядерними процесорами і графічними прискорювачами. Алгоритм апробовано на низці тестових задач. Показана його ефективність.
format	Article
author	Хіміч, О.М. Сидорук, В.А.
spellingShingle	Хіміч, О.М. Сидорук, В.А. Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею Теорія оптимальних рішень
author_facet	Хіміч, О.М. Сидорук, В.А.
author_sort	Хіміч, О.М.
title	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею
title_short	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею
title_full	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею
title_fullStr	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею
title_full_unstemmed	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею
title_sort	гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
url	https://nasplib.isofts.kiev.ua/handle/123456789/111517
citation_txt	Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею / О.М. Хіміч, В.А. Сидорук // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 106-113. — Бібліогр.: 9 назв. — укр.
series	Теорія оптимальних рішень
work_keys_str_mv	AT hímíčom gíbridnijalgoritmdlâlíníjnoízadačínajmenšihkvadratívznapívviznačenoûrozrídženoûmatriceû AT sidorukva gíbridnijalgoritmdlâlíníjnoízadačínajmenšihkvadratívznapívviznačenoûrozrídženoûmatriceû AT hímíčom gibridnyjalgoritmdlâlinejnojzadačinaimenʹšihkvadratovsrazrežennojpoluopredelennojmatricej AT sidorukva gibridnyjalgoritmdlâlinejnojzadačinaimenʹšihkvadratovsrazrežennojpoluopredelennojmatricej AT hímíčom hybridalgorithmforlinearleastsquaresproblemwithsparsesemidefinitematrix AT sidorukva hybridalgorithmforlinearleastsquaresproblemwithsparsesemidefinitematrix
first_indexed	2025-11-26T01:39:20Z
last_indexed	2025-11-26T01:39:20Z
_version_	1849815113176973312
fulltext	106 Теорія оптимальних рішень. 2014 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Запропоновано алгоритм отримання нормального псевдороз-в’язку систем лінійних рівнянь з розрідженими симетричними до-датно- напіввизначеними матрицями на комп’ютерах гібридної архітектури – комп'ютерах з ба- гатоядерними процесорами і графічними прискорювачами. Алгоритм апробовано на низці тестових задач. Показана його ефективність.  О.М. Хіміч, В.А. Сидорук, 2014 УДК 519.6 О.М. ХІМІЧ, В.А. СИДОРУК ГІБРИДНИЙ АЛГОРИТМ ДЛЯ ЛІНІЙНОЇ ЗАДАЧІ НАЙМЕНШИХ КВАДРАТІВ З НАПІВВИЗНАЧЕНОЮ РОЗРІДЖЕНОЮ МАТРИЦЕЮ Вступ. Значна кількість прикладних задач включає у себе як складову частину знаходження розв’язку системи лінійних алгебраїчних рівнянь (СЛАР) з розрідженими матрицями. Характерною особливістю СЛАР, що виникають у тих чи інших задачах є їх великий порядок. У деяких моделях порядок матриці СЛАР може досягати кількох мільйонів. Разом з тим вимоги до високопродуктивних обчислень набагато випереджають можливості традиційних паралельних комп’юте-рів, навіть не зважаючи на багатоядерність процесорів. Розв’язання проблеми прискорення обчислень на комп’ютерах з багатоядерними процесорами розглядається в площині використання для прискорення обчислень гібридних систем на основі багатоядерних CPU і GPU. У даній роботі запропоновано алгоритм знаходження розв’язку задачі найменших квадратів з мінімальною нормою для симетричних додатно-напіввизначених розріджених матриць. Алгоритм є альтернативою як методу регуляризуючого функціоналу [1], так і методу дискретної регуляризації [2], в основі якого лежить, наприклад, SVD-ал- горитм, оскільки в обох випадках втрачається початкова структура матриці. Постановка задачі. Розглянемо задачу найменших квадратів min , min n nE Ex E x E x Arg Ax b       (1) ГІБРИДНИЙ АЛГОРИТМ ДЛЯ ЛІНІЙНОЇ ЗАДАЧІ НАЙМЕНШИХ КВАДРАТІВ ... Теорія оптимальних рішень. 2014 107 з симетричною додатно-напівизначеною розрідженою матрицею (A = A T , A  0) порядку n і рангу k, розв’язок якої існує і єдиний [2]. В основі гібридного алгоритму знаходження розв'язку задачі найменших квадратів з мінімальною нормою (нормального псевдорозв’язку відповідної несумісної системи Ax = b) з симетричною додатно-напіввизначеною розрідженою матрицею лежить метод паралельних перерізів приведення симетричної розрідженої матриці до блочно-діагонального вигляду з обрамленням [3, 4] та триетапного алгоритму знаходження нормального псевдорозв’язку для останньої [5]. Теоретичною передумовою методу розв’язання задачі (1) для розріджених матриць на комп’ютерах гібридної архітектури є попереднє застосування до вихідної матриці методу паралельних перерізів, який приводить вихідну матрицю до блочно-діагонального вигляду з обрамленням 11 1 22 2 33 3 1 1 1 1 2 3 1 0 0 0 0 0 0 0 0 0 € 0 0 0 p p pT p p p p p p р pp pp A A A A A A A P AP A A A A A A A                          , де P – матриця перестановок, а блоки Aii, Api Aip зберігають розріджену структуру. Таким чином, задача розв’язування вихідної задачі (1) зводиться до розв’язування задачі €€min , min , n nEx E x E E y Arg A y b       (2) €, .y P x b P b   (3) Оскільки в методі паралельних перерізів виконуються ортогональні перетворення, евклідова норма відносно яких інваріантна, задачі (1), (2) і (3) – еквівалентні. При цьому очевидно зберігається і додатна-напіввизначеність матриці. Триетапний алгоритм для знаходження нормального псевдорозв’язку (2), ( 3) реалізується наступним чином. Для довільного вибору параметра  (наприклад,  = 0,01) реалізуємо наступні кроки алгоритму: О.М. ХІМІЧ, В.А. СИДОРУК 108 Теорія оптимальних рішень. 2014  €A E z b  ,  € € ,A E u Az  , max H i i u u u   € ,HA E w u  max .i i w  Якщо 2 1       , то отримаємо розв’язок з гарантованою похибкою , x u x    де u – наближений розв’язок задачі найменших квадратів з мінімальною нормою. Очевидно, з точки зору комп’ютерної реалізації, алгоритм зводиться до € €TL L факторизації симетричної блочно-діагональної з обрамленням додатно- визначеної матриці ЕА ˆ і багаторазового розв’язання системи лінійних рівнянь з трикутними блочними розрідженими матрицями €L і € .TL Триетапна схема регуляризації є альтернативою як методу регуляризуючого функціоналу  2A E u Ab  [1], так і методу дискретної регуляризації [2], в основі якого лежить, наприклад SVD-алгоритм. Переваги алгоритму триетапної регуляризації підсилюються для матриць блочно-діагональних з обрамленням. Очевидно, що при першому підході, втрачається блочна структура матриці, а при другому – не вдається її ефективно використати. Блочний алгоритм на основі LL T факторизації. Враховуючи те, що матриця є блочно-діагональною з обрамленням, розглянемо блочний варіант алгоритму LL T факторизації. Його можна представити у такій формі. Факторизація: для і, 1,0  pi послідовно виконуємо:  факторизацію блоку Аіі ;T ii ii iiA L L  модифікацію блоку обрамлення ;ii ip ipL L A ГІБРИДНИЙ АЛГОРИТМ ДЛЯ ЛІНІЙНОЇ ЗАДАЧІ НАЙМЕНШИХ КВАДРАТІВ ... Теорія оптимальних рішень. 2014 109  знаходження добутку T ip ipL L та модифікацію Арр 1 0 . p T pp pp ip ip i A A L L     На останньому кроці виконується факторизація ppA ~ T pppppp LLA  ~ . Внаслідок виконання етапу факторизації матриця L̂ матиме вигляд: 11 22 33 1 1 2 3 1 0 0 0 0 0 0 0 0 0 € 0 0 0 p p p р pp pp L L L L L L L L L L                       , де T ippi LL  , 1,0  pi . Прямий хід: послідовно для і, 1,0  pi виконуємо:  розв’язання системи iiii byL  ;  знаходження добутків ipi yL і модифікацію р-ї частини вектора b в нульовому процесорі ipipp yLbb  ~ . На останньому кроці розв’язуємо систему pppp byL ~  . Зворотній хід:  виконуємо розв’язання системи .pp p pL x y Послідовно виконуємо наступні операції:  знаходимо добутки pip xL і модифікуємо і-ту частину вектора y ;i i ip py y L x   розв’язуємо систему iiii yLx 1 . Гібридний алгоритм. Розглянемо декомпозицію даних для комп’ютерів гібридної архітектури з багатоядерними (CPU) процесорами і графічними (GPU) прискорювачами. Нехай для виконання задачі маємо p – 1 процесорне ядро. Тоді отримаємо наступний розподіл даних:  у всіх процесах розміщуються відповідні діагональні блоки Аіі;  на GPU, що відповідають процесам з номерами i, 1,0  pi зберігаються відповідні блоки Aip і відповідні частини векторів х, y, b. Враховуючи таку декомпозицію даних можна записати гібридний алгоритм прямого методу на основі LL T -факторизації. О.М. ХІМІЧ, В.А. СИДОРУК 110 Теорія оптимальних рішень. 2014 Факторизація: у всіх процесах з номерами і, 1,0  pi паралельно виконуємо:  факторизацію блоку Аіі : ;T ii ii iiA L L  копіювання на відповідний GPU блоку Lii. На GPU виконуємо: 1) модифікацію блоку обрамлення 1 ;ip ii ipL L A 2) знаходження добутку .T ip ipL L Копіюємо на відповідний CPU результат виконання T ipip LL і виконуємо муль- тизбирання та модифікацію Арр у процесі з номером 0. 1 0 . p T pp pp ip ip i A A L L     В нульовому процесі виконується факторизація ppA ~ : T pppppp LLA  ~ . Копіюємо результат у відповідний GPU. Прямий хід: на GPU, що відповідають процесам з номерами і, 1,0  pi виконуємо:  розв’язання системи iiii byL  ;  знаходження добутків ipi yL . Копіюємо результати виконання ipi yL на відповідний процесор і виконуємо мультизбирання та модифікацію р-ї частини вектора b в нульовому процесі .p p pi ib b L y  На GPU, що відповідає процесу з номером 0 копіюємо рb і розв’язуємо систему .pp p pL y b Зворотній хід: на GPU, що відповідає процесу з номером 0 розв’язуємо систему pppp yxL  . Копіюємо результат виконання на процесор і виконуємо розсилку хр у інші процесори. На відповідних GPU виконуються наступні операції:  знаходимо добутки pip xL і модифікуємо і-у частину вектора y ;i i ip py y L x   розв’язуємо систему .ii i iL x y Результати чисельних експериментів. Для реалізації стандартних обчислювальних процедур (множення матриць, розв’язування трикутних систем) можна використовувати функції відомих бібліотек, наприклад, CUSPARSE [6], ГІБРИДНИЙ АЛГОРИТМ ДЛЯ ЛІНІЙНОЇ ЗАДАЧІ НАЙМЕНШИХ КВАДРАТІВ ... Теорія оптимальних рішень. 2014 111 0 0.5 1 1.5 2 2.5 3 3.5 0 2 4 6 8 10 cant mins urfo gridgena Dubcova1 CUSP [7], Paralution [8]. Для зберігання матриць застосовано розріджений рядковий формат, вектори зберігаємо як щільні. Слід зазначити, що в програмній реалізації алгоритму для факторизації діагональних блоків Аіі використовувалась функція факторизації стрічкової матриці з бібліотеки LAPACK, що міститься в MKL, блоки Aip і Арр зберігаються як щільні. Розрахунки проводились на вузлах кластеру Інпарком-G [9], які мають наступні характеристики: • процесори: 2 Xeon 5606 (8 ядер) з частотою 2.13 ГГц; • графічні прискорювачі: 2 Tesla M2090; • обсяг оперативної пам’яті: 24 Гб; • комунікаційне середовище: InfiniBand 40 Гбіт/с (з підтримкою GPUDirect), Gigabit Ethernet. Також на вузлах встановлена бібліотека MKL 10.2.6 та CUDA починаючи з версії 3.2. Чисельні експерименти здійснювались на наступних розріджених матрицях, характеристики яких наведені в таблиці. На рис. 1, 2 показані графіки, що показують часи виконання гібридного алгоритму і величину отриманих прискорень. Отримані результати відповідають архітектурі 1 CPU та 1 GPU. ТАБЛИЦЯ. Характеристики тестових матриць Назва Проблемна область Порядок матриці Кількість ненульових елементів Dubcova1 2D/3D problem 16130 253009 minsurfo optimization problem 40806 203622 gridgena optimization problem 48962 512084 cant 2D/3D problem 62452 4007383 О.М. ХІМІЧ, В.А. СИДОРУК 112 Теорія оптимальних рішень. 2014 Кількість діагональних блоків РИС. 1. Час виконання гібридного алгоритму 0 2 4 6 8 10 12 14 16 0 2 4 6 8 10 cant mins urfo gridgena Dubcova1 Кількість діагональних блоків РИС. 2. Графік отриманих прискорень в залежності від кількості діагональних блоків гібридного алгоритму в порівнянні з блочним алгоритмом реалізованим на CPU Висновки. Розроблено і експериментально досліджено гібридний алгоритм прямого методу для лінійної задачі найменших квадратів з розрідженою симетричною додатно-напіввизначеною матрицею. Отримані результати для гібридної архітектури з одним CPU і одним GPU показують ефективність алгоритму. Більший ефект можна очікувати від реалізації паралельного варіанта даного алгоритму на архітектурах типу n CPU + m GPU. Прискорення обчислень можна чекати також, використовуючи, наприклад, для факторизації діагонального блоку алгоритми, які значну кількість обчислень реалізують на GPU. Зауваження. Слід зазначити, що згідно роботи [3], вищенаведений алгоритм має місце і для задачі з наближеними даними. А.Н. Химич, В.А. Сидорук ГИБРИДНЫЙ АЛГОРИТМ ДЛЯ ЛИНЕЙНОЙ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ С РАЗРЕЖЕННОЙ ПОЛУОПРЕДЕЛЕННОЙ МАТРИЦЕЙ Ч ас ( се к .) П р и ск о р ен н я ГІБРИДНИЙ АЛГОРИТМ ДЛЯ ЛІНІЙНОЇ ЗАДАЧІ НАЙМЕНШИХ КВАДРАТІВ ... Теорія оптимальних рішень. 2014 113 Предложен алгоритм получения нормального псевдорешения системы линейных уравнений с разреженными симметричными положительно-полуопределенными матрицами на компьютерах гибридной архитектуры – компьютерах с многоядерными процессорами и графическими ускорителями. Алгоритм апробирован на ряде тестовых задач. Показана его эффективность. A.N. Khimich, V.A. Sydoruk HYBRID ALGORITHM FOR LINEAR LEAST SQUARES PROBLEM WITH SPARSE SEMIDEFINITE MATRIX An algorithm of obtaining the normal pseudosolution of systems of linear equations with sparse symmetric positive-semidefinite matrices on hybrid architecture computers – computers with multicore processors and graphics accelerators is proposed. The algorithm is tested on a set of test problems. Shown its effectiveness. 1. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. – М.: Наука, 1986. – 287 с. 2. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. – М.: Наука, 1984. – 318 с. 3. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. – М.: Мир, 1984. – 333 с. 4. Хіміч О.М., Полянко В.В. Оптимізація паралельного ітераційного процесу для лінійних систем з розрідженими матрицями // Теорія оптимальних рішень. – 2011. – № 10 – С. 47 – 53. 5. Химич А.Н., Яковлев М.Ф. О решении систем с матрицами неполного ранга // Компьютерная математика. – Киев: Ин-т кибернетики имени В.М. Глушкова НАН Украины, 2003. – № 1. – С. 119 – 125. 6. CUDA CUSPARSE_Library – Santa Clara: Nvidia, 2012. – 92 p. 7. http://code.google.com/p/cusp-library/ 8. http://www.paralution.com/ 9. Молчанов И.Н., Химич А.Н., Мова В.И., Николайчук А.А. Интеллектуальный персональный компьютер гибридной архитектуры // Искусственный интеллект. – 2012. – № 3. – С. 73–78. Одержано 11.04.2014 http://code.google.com/p/cusp-library/ http://www.paralution.com/

Гібридний алгоритм для лінійної задачі найменших квадратів з напіввизначеною розрідженою матрицею

Institution

Ähnliche Einträge