algorithm - 如何提高掺杂矩阵构造算法的速度

Question

我正在使用下面显示的算法构建特定矩阵，以在量子纠错场景中应用代码掺杂。矩阵是二进制的，必须遵守一组特定的构造法则:

1. 必须有 p 行具有单个单元条目。该行的其余条目将为空，这符合矩阵的二进制性质。此外，这些单位条目必须放在每一行的不同列中。也就是说，这p行的单元条目不能放在同一列，不能重叠。

2. 其余行必须包含特定数量的单位条目，sb_degree。正如我将很快解释的那样，这就是问题所在。

3. 为了满足所需目的(掺杂量子 LDPC 代码)的矩阵，每一行和每一列都必须至少有一个单位条目。本质上，矩阵不能有全零行或全零列。

我的代码对于输入算法参数的特定组合工作得相当好:p(单个单元条目的行数)，m1(M 的行数)、N(M 的列数)和sb_degree(行中具有多个单元条目的个数)。例如，只要 p 和 sb_degree 的值分别不太大或不太小，它就可以轻松找到矩阵。然而，由于这些矩阵旨在解决的问题的性质，我需要具有较大 p 值(大约 m1 值的 65%)和 a 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

Answer 1

我不是随机放置值直到所有列都有一个条目，而是将一行分配给所有列，然后填充 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

最后，用 sb_degree 行填充 loc 行。

% 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