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

Question

我正在使用下面所示的算法来构建特定的矩阵，以便在量子纠错场景中应用代码掺杂。这些矩阵是二进制的，必须遵守一套具体的建筑规则：

1. 必须有带有单个单元条目的p行。该行的其余条目将为null，与矩阵的二进制性质相适应。此外，必须将这些单元条目放置在每一行的不同列中。换句话说，这些p行中的单元条目不能放在同一列中，它们不能重叠。
2. 其余的行必须包含特定数量的单元条目sb_degree。我将在短期内解释，这就是问题所在。
3. 要使矩阵适合于所需的目的(量子LDPC码的掺杂)，每一行和每列必须至少有一个单元条目。基本上，矩阵不能有一个全为零的行或列。

我的代码对于输入算法参数的特定组合相当有效：p (包含单个单元条目的行数)、m1 (M的行数)、N (M的列数)和sb_degree (有多个单元条目的行数)。例如，只要p和sb_degree的值分别不太大或不小，它就不难找到矩阵。然而，由于这些矩阵所要解决的问题的性质，我要求矩阵具有较大的p值(约占m1值的65% )和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

最后，用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