Приведение плотных матриц с элементами из GF(2) к ступенчатому виду на платформе 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