A GPU-based singular value decomposition algorithm

In this research paper we present an implementation of a singular value decomposition algorithm designed specifically for the graphics processing unit. It consists of two parts: orthogonal matrix decomposition and matrix diagonalization. Presented an implementation of bidiagonalization algorithm whe...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2023
Автор:	Sukharskyi, S.S.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2023
Теми:	singular value decomposition Householder algorithm Givens algorithm GPU computations jCUDA UDC 004.415.2
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/556
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-556
record_format	ojs
resource_txt_mv	ppisoftskievua/eb/2ec8700ff8140c81308a1cb5ffa938eb.pdf
spelling	pp_isofts_kiev_ua-article-5562023-10-23T11:32:59Z A GPU-based singular value decomposition algorithm Алгоритм сингулярного розкладу матриць на графічному процесорі Sukharskyi, S.S. singular value decomposition; Householder algorithm; Givens algorithm; GPU computations; jCUDA UDC 004.415.2 сингулярний розклад; алгоритм Хаусхолдера; алгоритм Ґівенса; обчислення на графічному процесорі; jCUDA УДК 004.415.2 In this research paper we present an implementation of a singular value decomposition algorithm designed specifically for the graphics processing unit. It consists of two parts: orthogonal matrix decomposition and matrix diagonalization. Presented an implementation of bidiagonalization algorithm where we calculate the main bidiagonal matrix and two orthogonal multipliers using a series of House- holder transformations, as well as diagonalization algorithm with the help of Givens rotation matrices. Bothe these parts are implemented in jCUDA environment. Experiments have been conducted, the results of which have been thoroughly investigated on the matter of time consumption and calculations error. We’ve also compared our implementation with alternatives both on central and graphic processors.Prombles in programming 2023; 1: 30-37 У статті представлено реалізацію алгоритму сингулярного розкладу матриці, розроблений для виконання на графічному процесорі, який складається з двох частин: ортогонального розкладання матриці та приведення матриці до діагонального вигляду. Наведено реалізацію зведення до дводіагонального вигляду матриці з обчисленням ортогональних множників за методом Хаусхолдера і діагоналізації із використанням матриці повороту Ґівенса в середовищі jCUDA. Проведено експерименти, результати яких ретельно досліджено на предмет часу обчислень, абсолютної похибки, а також проведено порівняння з альтернативними способами реалізації сингулярного розкладу як на центральному так і на графічних процесорах.Prombles in programming 2023; 1: 30-37 Інститут програмних систем НАН України 2023-04-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/556 10.15407/pp2023.01.030 PROBLEMS IN PROGRAMMING; No 1 (2023); 30-37 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2023); 30-37 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2023); 30-37 1727-4907 10.15407/pp2023.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/556/608 Copyright (c) 2023 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2023-10-23T11:32:59Z
collection	OJS
language	Ukrainian
topic	singular value decomposition Householder algorithm Givens algorithm GPU computations jCUDA UDC 004.415.2
spellingShingle	singular value decomposition Householder algorithm Givens algorithm GPU computations jCUDA UDC 004.415.2 Sukharskyi, S.S. A GPU-based singular value decomposition algorithm
topic_facet	singular value decomposition Householder algorithm Givens algorithm GPU computations jCUDA UDC 004.415.2 сингулярний розклад алгоритм Хаусхолдера алгоритм Ґівенса обчислення на графічному процесорі jCUDA УДК 004.415.2
format	Article
author	Sukharskyi, S.S.
author_facet	Sukharskyi, S.S.
author_sort	Sukharskyi, S.S.
title	A GPU-based singular value decomposition algorithm
title_short	A GPU-based singular value decomposition algorithm
title_full	A GPU-based singular value decomposition algorithm
title_fullStr	A GPU-based singular value decomposition algorithm
title_full_unstemmed	A GPU-based singular value decomposition algorithm
title_sort	gpu-based singular value decomposition algorithm
title_alt	Алгоритм сингулярного розкладу матриць на графічному процесорі
description	In this research paper we present an implementation of a singular value decomposition algorithm designed specifically for the graphics processing unit. It consists of two parts: orthogonal matrix decomposition and matrix diagonalization. Presented an implementation of bidiagonalization algorithm where we calculate the main bidiagonal matrix and two orthogonal multipliers using a series of House- holder transformations, as well as diagonalization algorithm with the help of Givens rotation matrices. Bothe these parts are implemented in jCUDA environment. Experiments have been conducted, the results of which have been thoroughly investigated on the matter of time consumption and calculations error. We’ve also compared our implementation with alternatives both on central and graphic processors.Prombles in programming 2023; 1: 30-37
publisher	Інститут програмних систем НАН України
publishDate	2023
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/556
work_keys_str_mv	AT sukharskyiss agpubasedsingularvaluedecompositionalgorithm AT sukharskyiss algoritmsingulârnogorozkladumatricʹnagrafíčnomuprocesorí AT sukharskyiss gpubasedsingularvaluedecompositionalgorithm
first_indexed	2024-09-12T19:29:57Z
last_indexed	2024-09-12T19:29:57Z
_version_	1815407614506303488
fulltext	30 Методи та засоби комп′ютерного моделювання УДК 004.415.2 http://doi.org/10.15407/pp2023.01.030 С. С. Сухарський АЛГОРИТМ СИНГУЛЯРНОГО РОЗКЛАДУ НА ГРАФІЧНОМУ ПРОЦЕСОРІ У статті представлено реалізацію алгоритму сингулярного розкладу матриці, розроблений для вико- нання на графічному процесорі, який складається з двох частин: ортогонального розкладання матриці та приведення матриці до діагонального вигляду. Наведено реалізацію зведення до дводіагонального вигляду матриці з обчисленням ортогональних множників за методом Хаусхолдера і діагоналізації із використанням матриці повороту Ґівенса в середовищі jCUDA. Проведено експерименти, результати яких ретельно досліджено на предмет часу обчислень, абсолютної похибки, а також проведено по- рівняння з альтернативними способами реалізації сингулярного розкладу як на центральному так і на графічних процесорах. Ключові слова: сингулярний розклад, алгоритм Хаусхолдера, алгоритм Ґівенса; обчислення на графіч- ному процесорі, jCUDA. Вступ Сучасний світ дуже зав’язаний на обчислення. З розвитком Big Data, штучно- го інтелекту та інших популярних сьогодні сфер, потреба в швидкісних та ефективних обчисленнях стала одним із найважливіших завдань сьогодення. Саме з такою метою протягом останніх понад десяти років ак- тивно розвивається галузь обчислень на гра- фічних процесорах, які містять тисячі ядер. Однією з передових платформ для цього є технологія розроблена NVIDIA, під назвою CUDA. Саме з цією технологією пов’язане дане дослідження, а точніше, з реалізацією SVD алгоритму з використанням потужнос- ті відеокарт, який є одним із основних мето- дів роботи прогресивних рекомендаційних систем; вирішує багато завдань лінійної ал- гебри та може бути застосований для розви- тку штучного інтелекту. А графічні проце- сори дозволяють виконувати значно більше обчислень за одиницю часу, а також зміню- ють підхід до побудови суперкомп’ютерів. Свідченням цього також є нещодавній про- рив у сфері суперкомп’ютерів, де вперше вдалося досягти ефективності в один екзаф- лопс саме за рахунок поєднання централь- ного та чотирьох графічних процесорів у вузол, яких суперкомп’ютер Frontier налі- чує близько 9.5 тисяч [9]. Метою дослідження є розробка та реалізація алгоритму SVD для виконання на графічному процесорі. Попередні дослі- дження [2, 4] вже довели ефективність ві- деокарт та перевагу над центральними про- цесорами, а також продемонстрували про- блеми поточних підходів. Також ціллю є до- сягнення можливості роботи з матрицями великих розмірів за рахунок ефективнішого використання наявної на графічному проце- сорі великої кількості ядер та для того, щоб у майбутньому можна було інтегруватися з великим комплексом бібліотек для пара- лельного програмування Mathpartner [7] та середовищем виконання ДАП [8], було об- рано середовище JCUDA. Загальні означення та бідіагоналізація Нехай А – матриця над полем комп- лексних (або дійсних) чисел розміру m × n. Її розклад у добуток трьох матриць (1) де A – будь-яка матриця розміру m × n, U – матриця m × m та ортогональна, V – матриця n × n та ортогональна і Ʃ – діагональна m × n матриця із впорядкованими за спаданням невід’ємними елементами на діагоналі, на- зивається сингулярним розкладом (Singular Value Decomposition). Перетворення Хаусхолдера (відо- браження Хаусхолдера) – це лінійне пере- творення векторного простору, яке викорис- товується в лінійній алгебрі для обрахунків ортогональних розкладів: © С. С. Сухарський, 2023 ISSN 1727-4907. Проблеми програмування. 2023. №1 31 Методи та засоби комп′ютерного моделювання (2) де Q, V, U – ортогональні (унітарні для поля комплексних чисел) матриці, R – права трикутна, а D дводіагональна матриці [5, 6]. Теорема Хаусхолдера. Для ненульо- вих векторів з однаковою нормою ( ) існує ор- тогональна симетрична матриця P, така, що (3) Детальніше про бідіагоналізацію та алгоритм приведення матриці до дводіаго- нального виду можна прочитати в нашій попередній праці [1] на цю тему. Щодо по- кращень у поточній роботі було проведено оптимізацію у роботі з пам’яттю, а також додано кернел для віднімання, щоб не вико- ристовувати вбудоване рішення з додаван- ням та множенням на -1. Крім того, замість власних кернелів зчитування рядків на гра- фічному процесорі та їх запис в вектори, використано стандартні методи бібліотеки Cublas – cublasDcopy використовуючи зсу- ви, що також дало пришвидшення. Діагоналізація За основу було взято ідею ітератив- ного опрацювання отриманої на попере- дньому етапі матриці для обнулення рядка над або під головною діагоналлю. Розгляне- мо на прикладі, як відбувається сам процес. Нехай маємо матрицю A, отриману з функ- ції biDiagonalize. (4) Перші дві ітерації стосуватимуться першого та другого квадратів матриці. Ми говоримо одразу про дві ітерації, оскільки вони пов’язані між собою спільним елемен- том, а тому не можуть бути виконані одно- часно. (5) Рис 1. Обчислення матриці L. 32 Методи та засоби комп′ютерного моделювання Побудувавши матрицю поворту на А1, ми обнулимо елемент ud1, проте зіпсуємо еле- мент під d1. Значення d1 також зміниться, як і значення d2. Відповідно нова матриця набуде такого вигляду: (6) Далі ми виконуватимемо аналогічні операції і до наступних блоків (квадратів), по- вторюючи цей процес зверху донизу діагона- лі, допоки усі значення над та під діагоналлю не будуть обнулені. Упродовж цього процесу ми також обчислюємо матриці L та R, які на початку є одиничними, а далі змінюються від застосувань до них матриці повороту Гівенса. На проміжному етапі алгоритму це обчислен- ня виглядає так: Як бачимо, зоною впливу в цьому ви- падку є відповідно перші два рядки матриці L. Для матриці ж R ситуація відрізнятиметь- ся тим, що там під впливом множення будуть змінюватись стовпчики: Рис 2. Обчислення матриці R. Наведені приклади були зроблені в системі MathPartner [7]. У процесі виконання алгоритму, матриця G також буде змінювати- ся, відповідно до поточних елементів. Паралелізм та роботу з пам’яттю дода- но за схемою, яка була запропонована в роботі [2], де паралельно обробляються N / 2 блоків, а N - це розмір квадратної матриці. Приклад блоків, які можна опрацьовувати паралельно: (7) Відповідно ми використовуємо N / 2 головних потоків. Спочатку роботу починає перший потік, а далі з кроком у два блоки свою роботу починає наступний і так повто- рюємо поки є вільні потоки. Щодо обчислень матриць L та R, то за рахунок того, що потоки працюють із різницею в два кроки, нема по- треби синхронізувати значення цих матриць між різними потоками, а тому є можливість так само паралельно обчислювати їх у кожно- му з них. Проте в [2] було помітно, що пришвид- шення незначне, оскільки один потік хоч і пра- цював з невеликим блоком головної матриці, але має опрацьовувати велику частину матри- ці L або R. Відповідно страждала швидкодія. Тому, було розширено цю ідею, ввівши понят- тя допоміжних потоків. Ідея полягає в тому, що кожному з N / 2 головних потоків дається ще X допоміжних потоків порівну так, щоб загальна кількість потоків уміщалася в межах одного блоку. Наприклад, якщо ми працюємо з матрицею 128 x 128 та використовуємо 64 головних потоки, а максимальна кількість по- токів у межах блоку 1024, тоді використову- ється не просто 64 потоки, а 64 групи по 16 потоків. Цей підхід дозволяє також розділити між ними роботу, необхідну для виконання обчислень із матрицями L та R. Водночас, до- дано перевірки, які дії варто виконувати тіль- ки головному потоку, а які залишити для всіх. Наприклад, застосування матриці повороту до матриці A виконує лише головний потік, а інші на це час не витрачають. Такий підхід проде- монстрував значне пришвидшення. Проте, ве- лика кількість потоків також викликає певні затримки з часом завершення програми (по- 33 Методи та засоби комп′ютерного моделювання трібно чекати, поки усі потоки завершать роботу), а також постає питання оптималь- ного вибору кількості потоків та блоків, на яких має запускатися обчислення. Експерименти Експерименти виконано для кожної частини окремо та для всієї програми, де ці частини працюють одна за одною, причому перша зберігає результат на відеокарті, а на- ступна одразу його опрацьовує. Ці дані до- сліджено щодо залежності часу обчислень від розміру матриць, а також оцінено та до- сліджено точність обчислень. Крім цього, досліджувалась залежність часу від точнос- ті для ітераційної частини алгоритму. Також проведено порівняння з послідовним алго- ритмом на центральному процесорі. Усі обчислення проводились на гра- фічному процесорі GIGABYTE RTX 3070 GAMING OC з характеристиками, наведе- ними в таблиці 1. Таблиця 1 Характеристики графічного процесора Графічний процесор GA104-300-A1 Архітектура Ampere Пам’ять 8 GB типу GDDR6; 256 bit; 448.0 GB/s Кількість CUDA ядер 5888 Спільна пам’ять блоку 48 KB Максимальна кількість потоків 1024 Інші характеристики системи наве- дено в таблиці 2 Таблиця 2 Загальні характеристики системи Центральний процесор Intel Core i5-12600K 3.7 GHz Оперативна пам’ять G.Skill 16 GB (2x8 GB) DDR4 3600 MHz Накопичувач WD SN850 SSD 1 TB Обчислення виконувалися на опе- раційній системі Windows 11 Pro 21H2 x64 (build 22000.739). Насамперед було проведено експе- рименти для оцінки часу виконання алго- ритму та оцінки похибки обчислень. Для цього генерувались матриці різних розмі- рів з діапазоном значень від 0 до 100 типу Double. Для кожної згенерованої матриці здійснювалося по два запуски, оцінювався час виконання кожної частини алгоритму та загальний час, а також брався середній час і діапазон відхилень. У цей час враховується весь процес обчислень, та не враховується процес перевірки похибки обчислень. Такі ж метрики проводились для похибки об- числень. У таблиці 3 наведено детальні дані щодо часу обчислень. Час наведено в секун- дах. Щоб наочніше оцінити залежність часу виконання від розміру матриці, роз- глянемо декілька графіків. На рисунку 3 ми спостерігаємо плавне зростання часу зі збільшенням розміру матриці. Також мо- жемо зазначити, що процес бідіагоналіза- ції відбувається досить швидко – квадратна матриця розміру 1024 обчислюється менше секунди. Щодо відхилення у часі прогонів, то для бідіагоналізації воно зовсім мале, а для діагоналізації незначне. Таблиця 3 Оцінка часу виконання Розмір матриці 128 256 512 1024 2048 Бідіагоналізація 0.060 0.103 0.216 0.873 6.557 Відхилення (+/- t) 0.005 0.009 0.022 0.009 0.008 Діагоналізація 0.131 0.338 1.280 11.886 64.122 Відхилення (+/- t) 0.016 0.022 0.076 0.802 2.677 Алгоритм 0.191 0.441 1.496 12.759 70.679 34 Методи та засоби комп′ютерного моделювання Рис 3.Час бідіагоналізації. Розглянемо тепер графік залежнос- ті часу діагоналізації від розміру матриці. Як бачимо з таблиці 3, цей процес складає переважну частину усього алгоритму, тому для порівняння побудуємо графік одразу з двома кривими. Рис 4. Час діагоналізації та всього алгорит- му Рисунок 4 дуже добре демонструє, наскільки близькі за часом ці криві – друга повністю перекриває першу. Сама залеж- ність часу дещо різкіша, ніж для бідіагона- лізації, проте загальна тенденція схожа. А от різниця в часі виконання велика – при- близно в 6 разів для матриць 512 x 512 та більше ніж в 12 разів на розмірі 1024 x 1024. Що цікаво, зі збільшенням розміру з 512 до 1024 час обчислень зріс у 8.5 разів. Це по- гано, але зі збільшенням з 1024 до 2048 час збільшився в 5.53 разів. Це покращення досягнуто за рахунок того, що матриця роз- міру 2048 виконується на більшій кількості блоків, відповідно більше потоків працю- ють з частиною матриці, але втрачається час на синхронізації значень. Щодо похибки обчислень, то, ана- лізуючи детальні дані наведені в таблиці 4, помітно, що абсолютна похибка обчислень досить повільно змінюється залежно від розміру матриці. Але на більших розмірах матриці відбувається певний стрибок у по- хибці діагоналізації, коли ми використову- ємо багато блоків. Особливо повільні змі- ни відбуваються під час бідіагоналізації. Проте, варто зазначити, що діагоналізацію можна налаштувати так, щоб алгоритм пра- цював, поки не буде досягнуто бажаної точ- ності, або не настане момент, коли краще вже не можна порахувати. Ми здійснили дослідження для ква- дратних матриць розміру 128 та 256, запо- внених числами типу Double в діапазоні від 0 до 100, як і для програми, що викону- валась на графічному процесорі, і порівня- ли результати, щоб розуміти ефективність таких обчислень на GPU. В таблиці 5 наве- дено результати експериментів, а саме, час виконання (в секундах) всього алгоритму SVD на GPU, CPU та визначене пришвид- шення. Таблиця 4 Оцінка абсолютної похибки обчислень Розмір матриці 128 256 512 1024 2048 Бідіагоналізація 4.47E-13 3.69E-13 5.33E-13 1.28E-12 1.78E-12 Відхилення (+/- err) 1.065E-13 4.25E-14 4.28E-14 1.17E-14 1.03E-13 Діагоналізація 5.28E-11 4.51E-11 1.73E-5 5.44E-5 5.45E-6 Відхилення (+/- err) 7.22E-13 6.16E-12 8.35E-6 7.56E-6 3.2E-6 Алгоритм 7.007E-12 8.64E-12 2.63E-6 2.18E-4 1.06E-6 35 Методи та засоби комп′ютерного моделювання Таблиця 5 Розмір матриці 128 256 CPU 110.291 1802.114 GPU 0.191 0.441 Пришвидчення в n разів 577,43 4086,42 Порівняння часу обчислень на CPU та GPU Наведена вище таблиця підтверджує, що один графічний процесор має дуже вели- кі потужності для паралельних та інтенсив- них обчислень. Навіть на невеликій матриці розміру 128 нам знадобиться дуже добре реалізована програма і потужний процесор з великою кількістю ядер, щоб зрівнятись із можливостями відеокарти. На матриці біль- шого розміру різниця взагалі колосальна. Також проведено порівняння з CUDA API [10]. Були виконані експерименти з точ- ністю 10E-10 та матрицями з числами типу Double з діапазоном значень від 0 до 100. Як бачимо з даних у таблиці 6, різниця поки дуже серйозна. Якщо на матрицях невели- кого розміру різниця ще відносно невелика і її легко подолати за рахунок оптимізації виділення блоків та потоків, то на матри- цях великого розміру стає дуже помітною проблема, коли із використанням декількох блоків потрібно навчитися використовувати групи допоміжних (додаткових) потоків до тих, що працюють над множеннями правої та лівої матриць. Висновки У даній праці досліджено та реалі- зовано алгоритм сингулярного розкладу матриць на графічному процесорі. Перша частина алгоритму використовує метод Ха- усхолдера для приведення матриці до дво- діагонального вигляду та показує чудові ре- зультати із швидкості й точності обчислень. Підхід трансформацій покращено та опти- мізовано під виконання на відеокарті для зменшення кількості запису та зчитувань з пристрою й відповідно максимальної ефек- тивності обчислень. У другій частині алгоритму застосо- вано новий підхід у реалізації стандартно- го ітераційного процесу, який вдало вико- ристовує присутні в графічному процесорі ресурси, адаптуючись під конкретні пара- метри конкретного пристрою. Також запро- поновано підхід до пришвидшення та опти- мізації обчислень лівої та правої матриць. Здійснено ретельне дослідження з детальним описом умов та способів оцінки часу виконання та визначення точності об- числень. Результати показали колосальне пришвидшення відносно виконання цьо- го алгоритму на центральному процесорі. Також вони підтвердили, що ідея виділен- ня групи потоків у кожному блоці є дуже перспективною, адже швидкість обчислень помітно зростає із застосуванням оптималь- них параметрів. Але, як показали порівнян- ня з альтернативними способами реалізації, цей підхід з групами потоків потрібно по- ліпшувати для декількох блоків, оскільки саме на великих матрицях з’являється по- мітне відставання за часом обчислень по- рівняно з CUDA API, а також падає точність обчислень. Тому далі потрібно знайти ви- рішення проблеми ефективної паралельної роботи багатьох блоків, а також окремо досліджувати оптимальний підбір їхнього Таблиця 6 Порівняння з CUDA API Розмір матриці 128 256 512 1024 2048 SVD 0.191 0.441 1.496 12.759 70.679 Похибка 7.007E-12 8.64E-12 2.63E-6 2.18E-4 1.06E-6 CUDA API SVD 0.038 0.113 0. 335 1.224 7.462 Похибка 1.36E-11 2.04E-11 2.02E-11 2.07E-11 2.72E-11 Пришвидшення в n разів 5.02 3.9 4.46 10.42 9.47 36 Методи та засоби комп′ютерного моделювання розміру та кількості. Отже, запропонований підхід пока- зав чудові результати, але ще залишає за со- бою простір для покращень та оптимізації в майбутніх дослідженнях. Література 1. Малашонок Г.І., Cухарський С.С. Алго- ритм обчислення дводіагональної матриці ортогональним розкладанням на графічно- му процесорі. Наукові записки НаУКМА. Комп’ютерні науки. 2021. Том 4. [Елек- тронний ресурс]. – режим доступу: http:// nrpcomp.ukma.edu.ua/article/view/246581. Дата звернення: 2022.06.14 2. Малашонок Г.І., Семилітко М.Ю. Пара- лельний SVD алгоритм для тридіагональ- ної матриці на відеокарті з використанням архітектури Nvidia CUDA. Наукові запис- ки НаУКМА. Комп’ютерні науки. 2021. Том 4. [Електронний ресурс]. – режим до- ступу: http://nrpcomp.ukma.edu.ua/article/ view/246582. Дата звернення: 2022.06.14 3. Малашонок Г. І., Савченко С. О., “Матричні алгоритми розбиття множин для рекомен- даційних систем”. НаУКМА, 2019. 4. S. Lahabar and P. J. Narayanan, “Singular value decomposition on GPU using CUDA,” 2009 IEEE International Symposium on Paral- lel & Distributed Processing, 2009, pp. 1-10, doi: 10.1109/IPDPS.2009.5161058. [Елек- тронний ресурс]. – режим доступу: https:// ieeexplore.ieee.org/document/5161058/citatio ns?tabFilter=papers#citations. Дата звертан- ня: 2022.06.12 5. Persson, “Householder Reflectors and Givens Rotations”, MIT 18.335J / 6.337J Introduc- tion to Numerical Methods. [Електронний ресурс]. – режим доступу: https://math.dart- mouth.edu/~m116w17/Householder.pdf. Дата звертання: 2022.06.05 6. Cornell University, “Numerical linear alge- bra and matrix factorizations”, [Електро- нний ресурс]. – режим доступу: http:// pi.math.cornell.edu/~web6140/TopTenAlgo- rithms/Householder.html. Дата звертання: 2022.06.12 7. Система комп’ютерної алгебри MathPart- ner [Електронний ресурс]. - http://mathpar. ukma.edu.ua/. Дата звернення: 2022.06.13 8. Malaschonok, G.I., Sidko, A.A. Supercomputer Environment for Recursive Matrix Algorithms. Program Comput Soft 48, 90–101 (2022). https://doi.org/10.1134/S0361768822020086 9. Новинний ресурс Nauka.ua [Електронний ресурс]. – режим доступу: https://nauka.ua/ news/superkompyuter-vpershe-dosyag-efek- tivnosti-v-odin-ekzaflops. Дата звернення: 2022.06.14 10. CUDA API SVD. [Електронний ресурс]. – режим доступу: https://github.com/ NVIDIA/CUDALibrarySamples/blob/master/ cuSOLVER/gesvdj/cusolver_gesvdj_example. cu . Дата звернення: 2022.07.01 References 1. Malashonok H. I., Sukharskyi S. S. A GPU-based orthogonal matrix factoriza- tion algorithm that produces a two-diago- nal shape. NaUKMA. Computer Science. 2021. retrieved from http://nrpcomp. ukma.edu.ua/article/view/246581. 2. Malashonok H. I., Semylitko М.Y. Parallel SVD algorithm for a three-diagonal matrix on a video card using the Nvidia CUDA architecture. NaUKMA. Computer Sci- ence. 2021. retrieved from http://nrpcomp. ukma.edu.ua/article/view/246582. 3. Malashonok H. I., Savchenko S. O., “Matrychni alhorytmy rozbyttia mnozhyn dlia rekomendatsiinykh system”. NaUKMA, 2019. 4. S. Lahabar and P. J. Narayanan, «Singular value decomposition on GPU using CUDA,» 2009 IEEE International Symposium on Parallel & Distributed Processing, 2009, pp. 1-10, retrieved from http://doi. org/10.1109/IPDPS.2009.5161058. 5. Persson, “Householder Reflectors and Givens Rotations”, MIT 18.335J / 6.337J Introduction to Numerical Methods. retrieved from https://math.dartmouth. edu/~m116w17/Householder.pdf. 6. Cornell University, “Numerical lin- ear algebra and matrix factorizations”, retrieved from http://pi.math.cornell. edu/~web6140/TopTenAlgorithms/House- holder.html. 7. Computer Algebra System MathPartner retrieved from http://mathpar.ukma.edu. ua/. 8. Malaschonok, G.I., Sidko, A.A. Supercomputer Environment for Recursive Matrix Algorithms. Program Comput Soft 37 Методи та засоби комп′ютерного моделювання 48, 90–101 (2022). https://doi.org/10.1134/ S0361768822020086 9. News resource Nauka.ua retrieved from https://nauka.ua/news/superkompyuter- vpershe-dosyag-efektivnosti-v-odin-ekza- flops. 10. CUDA API SVD. retrieved from h t t p s : / / g i t h u b . c o m / N V I D I A / CUDALibrarySamples/blob/master/ cuSOLVER/gesvdj/cusolver_gesvdj_ example.cu . Одержано: 14.12.22 Про авторів: Сухарський Сергій Сергійович, Магістр, аспірант Кількість публікацій в українських видан- нях: 1 Кількість публікацій в зарубіжних індексо- ваних виданнях: 0 ORCID: 0000-0002-5873-984X Місце роботи: Інститут Програмних Систем НАН України Адреса: м. Тернопіль, вул. Збаразька 37

A GPU-based singular value decomposition algorithm

Репозитарії

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