УДК 519.61; 519.684.6
ПРИВЕДЕНИЕ ПЛОТНЫХ МАТРИЦ С ЭЛЕМЕНТАМИ
ИЗ GF(2) К СТУПЕНЧАТОМУ ВИДУ НА ПЛАТФОРМЕ NVIDIA CUDA.
П. А. Лебедев
МИЭМ НИУ ВШЭ, Москва
e-mail:
Описан подход к реализации на программно-аппаратной платформе NVIDIA
CUDA метода “четырeх русских” приведения плотных матриц с элементами
из GF(2) к ступенчатому виду. Получены оценки времени работы алгоритма
и рекомендации по выбору параметров алгоритма. Показано, что разрабо-
танная реализация алгоритма является самой эффективной по сравнению с
существующими решениями для матриц размера
2
17
×
2
17
.
Ключевые слова
:
приведение матрицы к ступенчатому виду, метод “четырeх
русских”, NVIDIA CUDA.
REDUCING DENSE MATRICES OVER GF(2) TO ROW ECHELON FORM
ON NVIDIA CUDA PLATFORM
P.A. Lebedev
Moscow Institute of Electronics and Mathematics of National Research University
“Higher School of Economics”, Moscow
e-mail:
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
most effective in comparison with the existing solutions for matrices of size
2
17
×
2
17
.
Keywords
:
reducing a matrix to row echelon form, method of four russians, NVIDIA
CUDA.
Введение.
Дадим определение двум особым классам матриц (пря-
моугольных таблиц) с элементами из некоторого поля.
Матрица имеет
ступенчатый вид по строкам
, если
1. все строки, имеющие хотя бы один ненулевой элемент (ненуле-
вые строки), расположены над строками, состоящими из одних
нулевых элементов (нулевыми строками);
2. ведущий (первый ненулевой слева) элемент каждой ненулевой
строки (кроме первой строки матрицы) располагается строго
справа от ведущего элемента предудущей строки.
Матрица имеет
приведенный ступенчатый вид по строкам
, если она
имеет ступенчатый вид по строкам и каждый ведущий элемент явля-
ется единицей, а все остальные элементы в том же столбце — нули.
Приведение матрицы к ступенчатому виду операциями над стро-
ками и столбцами, сохраняющими определенные ee свойства, являет-
ся основой численных методов вычисления рангов и определителей
матриц, нахождения обратных матриц и решения систем линейных
50
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2013. № 1
