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