Приведение плотных матриц с элементами из GF(2) к ступенчатому виду на платформе NVIDIA CUDA
Авторы: Лебедев П.А. | Опубликовано: 10.06.2013 |
Опубликовано в выпуске: #1(48)/2013 | |
DOI: | |
Раздел: Прикладная математика; методы математического моделирования | |
Ключевые слова: приведение матрицы к ступенчатому виду, метод “четырeх русских”, NVIDIA CUDA |
Описан подход к реализации на программно-аппаратной платформе NVIDIA CUDA метода “четырeх русских” приведения плотных матриц с элементами из GF(2) к ступенчатому виду. Получены оценки времени работы алгоритма и рекомендации по выбору параметров алгоритма. Показано, что разработанная реализация алгоритма является самой эффективной по сравнению с существующими решениями для матриц размера 2^17X2^17.
Литература
[1] Арлазаров В.Л., Диниц Е.А., Кронрод М.А., Фараджев И.А. Об экономном построении транзитивного замыкания ориентированного графа. Докл. АН СССР. – 1970. – Т. 194, № 3. – C. 487–488.
[2] Волков Е.А. Численные методы. – М.: Наука, 1987. – C. 139–150.
[3] Gregory V. Bard . Matrix Inversion (or LUP-Factorization) via the Method of Four Russians, in .(n3 log n)Time. http://www.math.umd.edu/bardg/m4ri.new.pdf
[4] BLAS (Basic Linear Algebra Subprograms). http://www.netlib.org/blas/
[5] The NVIDIA CUDA Basic Linear Algebra Subroutines (cuBLAS) library. http://developer.nvidia.com/cublas
[6] Denise Demirel . Effizientes L.linearerosen Gleichungssysteme uber.GF(2) mit GPUs - 27. September 2010. http://www.cdc.informatik.tudarmstadt.de/reports/reports/Denise_Demirel.diplom.pdf
[7] GAP - Groups, Algorithms, Programming - a System for Computational Discrete Algebra. http://www.gap-system.org/
[8] M4RI - Lienar Algebra over F2. http://m4ri.sagemath.org
[9] M4RI Performance over GF(2). http://m4ri.sagemath.org/performance.html
[10] Magma Computational Algebra System. http://magma.maths.usyd.edu.au/magma/
[11] NTL: A Library for doing Number Theory. http://www.shoup.net/ntl/
[12] NVIDIA Corporation NVIDIA CUDA C Programming Guide Version 4.1 11/18/2011. http://developer.download.nvidia.com/compute/DevZone/docs/html /C/doc/CUDA_C_Programming_Guide.pdf
[13] NVIDIA Corporation CUDA GPU Occupancy Calculator. http://developer.download.nvidia.com/compute/DevZone/docs/html/C/tools/CUDA_Occupancy_Calculator.xls
[14] Jemie Tharaud, Rafa.er.el Laurent. Linear algebra over the field with two elements using GPUs. http://moais.imag.fr/membres/jeanlouis.roch/perso_html/transfert/2009-06-19-IntensiveProjects-M1-SCCI-Reports/ tharaud_laurent_article.pdf