Reducing dense matrices over GF(2) to row echelon form on NVIDIA CUDA platform

An approach is described to implementation of the Method of Four Russians for reducing the dense matrices over GF(2) to row echelon form using the NVIDIA CUDA platform. Estimates of the algorithm running time and recommendations on choosing the algorithm parameters are given. It is shown that the developed implementation is 217 .217 most effective in comparison with the existing solutions for matrices of size 2^17X2^17.

References

[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