ИССЛЕДОВАНИЕ КЛАСТЕРИЗУЕМОСТИ СТРОК БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ НАД GF(2)

решето числового поля параллельное матрично-векторное умножение разбиение разреженных матриц кластеризация

О ВИЗУАЛИЗАЦИИ ИНФОРМАЦИИ, ЗАДАЧИ ИНТЕГРАЦИИ, ОБРАБОТКИ И ЗАЩИТЫ ИНФОРМАЦИИ В СИТУАЦИОННЫХ ЦЕНТРАХ, ...

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

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт