ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
37
УДК 001.891.573
Е . Ю . А л е х о в а
ИССЛЕДОВАНИЕ КЛАСТЕРИЗУЕМОСТИ СТРОК
БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ НАД GF(2)
Рассмотрены алгоритмы кластеризации больших объемов данных,
которые, как правило, или очень ресурсоемки, или имеют эвристиче-
ские этапы, или и то, и другое одновременно. Перед применением
этих алгоритмов следует оценить по каким-либо известным харак-
теристикам содержание во взятом объеме данных, интересных для
практики кластеров.
E-mail:
0allena0@gmail.com
Ключевые слова:
решето числового поля, параллельное матрич-
но-векторное умножение, разбиение разреженных матриц, кла-
стеризация
В рамках данной работы автор проанализировал специфический
вид данных – строки матриц, образующиеся при факторизации мето-
дами решета числового поля [1, 2]. Исследуемые матрицы имеют
следующие отличительные характеристики: разреженные матрицы
большого размера; каждая строка в них является случайным сильно
разреженным двоичным вектором, причем веса векторов варьируют-
ся достаточно слабо; размер матрицы может достигать 109 столб-
цов/строк, при этом средний вес строк для такой матрицы относи-
тельно невелик, порядка 140 ненулей. Одинаковые строки в матрице
отсекаются специальной процедурой предварительной фильтрации
[3],
поэтому все строки в матрице различны. Метрика близости для
строк следует из задачи минимизации коммуникаций при параллель-
ном матрично-векторном умножении [1, 4] и является количеством
совпадающих столбцов, содержащих ненулевые элементы. В каче-
стве целевых вычислительных комплексов представляют интерес
комплексы с 512–32 768 узлами. Исходя из этого была сформулиро-
вана следующая постановка задачи: какова вероятность
p
,
что в мат-
рице размера
l
×
n
,
каждая строка которой является случайным дво-
ичным вектором с весом
m
,
найдется не менее
k
строк, таких, что все
их единицы содержатся в
s
столбцах.
В работе были рассмотрены следующие диапазоны указанных
выше параметров:
30
2 ;
n
=
(1)
7
8
2
2 ;
m
< <
(2)