Стр. 8 - Е.Ю. Алехова - Исследование кластеризуемости строк больших разреженных матриц над GF(2)

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012 44
exp
( 1) 1 1 ( 1) 1 1 ( 1)
2 2 2 2
exp
1 ( 1) 1 1 ( 1) 1 1
2 1 1
2 2 2
s k mk
k s mk
k s mk
n l s
R
k s n
k k m m s s
k s k
s l s n n
m
l n
k s
s m m k
s k s n s n l
m
−
≈ ×
⎡ ⎤ ⎛ ⎞
⎢ ⎥ ⎜ ⎟
⎢ ⎥ ⎜ ⎟
− − − ⎛ ⎞
⎢ ⎥ ⎜ ⎟ × + + − + − − − =
⎜ ⎟
⎢ ⎥ ⎛ ⎞ ⎜ ⎟ ⎝ ⎠
⎜ ⎟ ⎢ ⎥ ⎜ ⎟
⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎝ ⎠
⎝ ⎠ ⎣ ⎦
⎡ ⎤ ⎡ ⎤
= ×
⎢ ⎥ ⎢ ⎥
⎣ ⎦ ⎣ ⎦
⎛
⎜
⎜
− − − ⎛ ⎞ ⎛ ⎞
× + − + − − − +
⎜ ⎟ ⎜ ⎟ ⎛ ⎞ ⎝ ⎠ ⎝ ⎠
⎜ ⎟
⎜ ⎟
⎝ ⎠ ⎝
.
⎡ ⎤ ⎛ ⎞⎞
⎢ ⎥ ⎜ ⎟⎟
⎢ ⎥ ⎜ ⎟⎟
⎢ ⎥ ⎜ ⎟ ⎜ ⎟
⎢ ⎥ ⎜ ⎟ ⎜ ⎟
⎢ ⎥ ⎜ ⎟ ⎜ ⎟
⎢ ⎥ ⎜ ⎟ ⎜ ⎟
⎠ ⎝ ⎠ ⎣ ⎦
(25)
Прологорифмировав, получим удобный для расчетов вид:
1
ln ln ( ) ln 2 1 2
( 1) 1 1 ( 1) 1 1
1 .
2 2
l n s
R k s mk s
k s n
m m k
k s s n l
m
− ⎛⎞
= + − + + − +⎜ ⎟
⎝ ⎠
⎛ ⎞ ⎛ ⎞
⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟
− − ⎛ ⎞
⎜ ⎟ ⎜ ⎟ + − − − +
⎜ ⎟ ⎛ ⎞ ⎜ ⎟ ⎝ ⎠ ⎜ ⎟
⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠ ⎝ ⎠
(26)
Формула (26) использовалась для расчета матрицы размером
109 с весом строки m = 140 и распределеним ее строк на 512, 1 024,
2 048, 4 096, 8 192, 16 384 и 32 768 узлах. Для каждого узла было
посчитано, при каком количестве s столбцов с ненулевыми эле-
ментами вероятность нахождения в матрице нужного количества
подходящих строк близка к 1. На рисунке представлены сводные
графики для всех узлов, и для узла 1024 и для узла 2048 в увели-
ченном масштабе.