Reid’s Method

Reid’s Method uses the same main method as the Sparse Bartels-Golub Method execept for the extra call to reidrotate. This is the code within the reidrotate method.

%% Find the singleton rows and columns of the bump

csingles = zeros(bside-lside,1);
cs = 0;

rsingles = zeros(1, bside-lside);
rs = 0;

for z=lside+1:bside
  if (nnz(U(lside:bside, z))) == 1
    cs = cs + 1;
    csingles(cs) = z;
    end;  %if
  if (nnz(U(z-1, lside:bside))) == 1
    rs = rs + 1;
    rsingles(rs) = z-1;
    end;  %if
  end;  %for

%%%% Now, we need to loop until all the singletons have been rotated out.
while (cs ~= 0 & rs ~= 0)

                        %%% Column rotations %%%

   %%%% First see if the top column(s) have been eliminated already %%%%
  if (cs ~= 0)
    while (csingles(cs) == 0)
      cs = cs - 1;
      if (cs == 0)
        break;
        end;  %if
      end;  % while
    end;  %if

  %%%% Then rotate the top column out. %%%%
  if (cs ~= 0)
    top = csingles(cs);

    shift = [1:lside-1 top lside:top-1 top+1:m];
    U = U(shift,shift);
    Qinv = Qinv(shift);
    Ptemp = Ptemp(shift);

    %%%% Update the waiting columns and rows that have been shifted. %%%%
    for z = 1:cs
      if (csingles(z) < top & csingles(z) > 0)
        csingles(z) = csingles(z) + 1;
      elseif (csingles(z) == top)
        csingles(z) = 0;
        end;  %if
      end;  %for
    for z = 1:rs
      if (rsingles(z) < top & rsingles(z) > 0)
        rsingles(z) = rsingles(z) + 1;
      elseif (rsingles(z) == top)
        rsingles(z) = 0;
        end;  %if
      end;  %for

    %%%% Has the column shift created new singleton columns? %%%%
    for z = find(U(lside, lside+2:bside))' + lside + 1
      if (nnz(U(lside+1:bside, z)) == 1)
        csingles(cs) = z;
        cs = cs + 1;
        end;  %if
      end;  %for


    %%%% And has it created OR REMOVED any singleton rows? %%%%
    for z = find(U(lside+1:bside, lside)) + lside
      if (nnz(U(z,lside+1:bside)) == 1)         %%% New row singleton
        rs = rs + 1;
        rsingles(rs) = z;
      elseif (nnz(U(z,lside+1:bside)) == 0)     %%% ELIMINATED singleton
        for y=1:rs
          if (rsingles(y) == z)
            rsingles(y) = 0;
            end;  % if
          end;  % for
        end;  % if
      end;  % for

    cs = cs - 1;
    lside = lside+1;
    end;  %if


                        %%% Row rotations %%%

  %%%% First see if the top row(s) have been eliminated already %%%%
  if (rs ~= 0)
    while (rsingles(rs) == 0)
      rs = rs - 1;
      if (rs == 0)
        break;
        end;  %if
      end;  % while
    end;  %if  

  %%%% Then rotate the top column out. %%%%
  if (rs ~= 0)
    top = rsingles(rs);

    shift = [1:top-1 top+1:bside top bside+1:m];
    U = U(shift,shift);
    Qinv = Qinv(shift);
    Ptemp = Ptemp(shift);

    %%%% Update the waiting columns and rows that have been shifted. %%%%
    for z = 1:cs
      if (csingles(z) > top & csingles(z) > 0)
        csingles(z) = csingles(z) - 1;
      elseif (csingles(z) == top)
        csingles(z) = 0;
        end;  %if
      end;  %for
    for z = 1:rs
      if (rsingles(z) > top & rsingles(z) > 0)
        rsingles(z) = rsingles(z) - 1;
      elseif (rsingles(z) == top)
        rsingles(z) = 0;
        end;  %if
      end;  %for

    %%%% Has the column shift created new singleton rows? %%%%
    for z = find(U(lside:bside-1, bside))' + lside -1
      if (nnz(U(z, lside:bside-1)) == 1)
        rsingles(rs) = z;
        rs = rs + 1;
        end;  %if
      end;  %for

    %%%% And has it created OR REMOVED any singleton columns? %%%%
    for z = find(U(bside, lside:bside-1)) + lside -1
      if (nnz(U(lside:bside-1,z)) == 1)                %%% New row singleton
        cs = cs + 1;
        csingles(cs) = z;
      elseif (nnz(U(lside:bside-1,z)) == 0)    %%% ELIMINATED singleton
        for y=1:cs
          if (csingles(y) == z)
            csingles(y) = 0;
            end;  % if
          end;  % for
        end;  % if
      end;  % for

    rs = rs - 1;
    bside = bside - 1;
    end;  %if

end;  %while