Как увеличить скорость алгоритма построения легирующей матрицы

Я использую алгоритм, показанный ниже, для построения определенных матриц для применения легирования кода в сценарии квантовой коррекции ошибок. Матрицы являются бинарными и должны подчиняться определенному набору законов построения:

  1. Должно быть p строк с одним элементом. Остальные элементы этой строки будут нулевыми, как и подобает бинарной природе матриц. Кроме того, эти записи единиц должны быть помещены в разные столбцы для каждой строки. Другими словами, единицы измерения в этих p строках не могут быть помещены в один и тот же столбец, они не могут перекрываться.

  2. Остальные строки должны содержать определенное количество единиц измерения, sb_degree. Как я объясню вкратце, в этом и заключается проблема.

  3. Чтобы матрица подходила для требуемых целей (легирование квантового LDPC-кода), в каждой строке и столбце должна быть хотя бы одна единичная запись. По сути, в матрице не может быть нулевой строки или столбца.

Мой код работает достаточно хорошо для определенных комбинаций входных параметров алгоритма: p (количество строк с одной единичной записью), m1 (количество строк M), N (количество столбцов M) и sb_degree (количество единиц). в строках, содержащих более одной единицы измерения). Например, у него нет проблем с поиском матриц при условии, что значения p и sb_степень не слишком велики или малы соответственно. Однако из-за характера проблемы, которую эти матрицы призваны решить, мне нужны матрицы с большим значением p (около 65% значения m1) и малым значением sb_degree. Это становится проблемой для моего алгоритма, так как малые значения sb_degree делают поиск матрицы, удовлетворяющей второму и третьему требованиям построения, сложной задачей.

В идеале я хотел бы иметь возможность ускорить этот поиск, чтобы я мог получить в свои руки тип матриц, который мне нужен, чтобы помочь в моих исследованиях квантовой коррекции ошибок. Я включил свой код Matlab, чтобы обеспечить контекст того, как я строю матрицы. Я был бы признателен, если бы кто-нибудь из вас мог придумать способ ускорить мой код или придумать другой способ выполнения построения этих матриц.

Алгоритм называется M = Create_Doping_Matrix(m1,N,p,sb_degree) и реализован следующим образом

M = zeros(m1,N);
p_indexes = randperm(m1,p);
all_indexes = 1:m1;
idx = ~ismember(all_indexes,p_indexes);
loc = find(idx~=0);
c_indexes = randperm(N,p);
% Create the rows with a single unit entry
for ii=1:p
    M(p_indexes(ii),c_indexes(ii)) = 1;
end
M_orig = M;
% Create the rows with more than a single unit entry
for jj = 1:length(loc)
    M(loc(jj), randperm(N,sb_degree))=1;
end

while nnz(sum(M,1)) ~= N % Check that there are no all-zero rows
    M = M_orig;
    for jj = 1:length(loc)
        M(loc(jj), randperm(N,sb_degree))=1;
    end
end

matlab algorithm sparse-matrix algebra telecommunication
person Patrick Fuentes    schedule 10.07.2019    source источник
comment
Если ваш код работает правильно, ваш вопрос может быть более адаптирован к обмену стеками просмотра кода.   -  person m.raynal    schedule 10.07.2019

Ответы (1)


arrow_upward
1
arrow_downward

Вместо случайного размещения значений до тех пор, пока во всех столбцах не будет записи, я бы назначил строку всем столбцам, а затем заполнил m1-p строк, пока в каждой из них не будет sb_degree ненулевых записей.

M = zeros(m1,N);
p_indexes = randperm(m1,p);
all_indexes = 1:m1;
idx = ~ismember(all_indexes,p_indexes);
loc = find(idx~=0);
c_indexes = randperm(N,p);
% Create the rows with a single unit entry
for ii=1:p
    M(p_indexes(ii),c_indexes(ii)) = 1;
end

Код такой же до сих пор. Теперь убедитесь, что в каждом столбце есть ровно одна ненулевая запись. Обратите внимание, что этим процессом loc строкам может быть присвоено более одного значения 1, вплоть до sb_degree.

% Add one entry to each unfilled column of M on an unfilled row of M(loc,:)
missing = find(sum(M,1) == 0);

for fillcol = missing
   addtoidx = randi(numel(loc));   % select random row from loc 
   fillrow = loc(addtoidx);   % row number in M
   M(fillrow, fillcol) = 1;
   if (sum(M(fillrow,:)) >= sb_degree)   % this row is now full 
      loc(addtoidx) = [];   % remove it from loc 
   end
end

И, наконец, заполните loc строк sb_degree единицами.

% Fill the rows that need more than a single unit entry
% but still contain less than sb_degree
for jj = 1:length(loc)   
   thisrow = M(loc(jj),:);   % unfilled row from M
   emptycols = find(thisrow == 0);   % indices of columns of thisrow not yet filled
   fillidx = randperm(numel(emptycols), sb_degree - sum(thisrow));
   M(loc(jj), emptycols(fillidx))=1;
end
person beaker    schedule 10.07.2019
comment
Я только что протестировал это решение и должен сказать, что оно значительно лучше исходного кода. Большое вам спасибо за вашу помощь !! - person Patrick Fuentes; 11.07.2019