2011-04-21

(6) Max determinant problem: Algorithm 3, min dot product

Algorithm 3: minimal dot product

I extended the geometry idea: if a pair of axes has minimal dot product, it could be a max determinant matrix. Minimal dot product means as perpendicular as possible. I implemented this idea in Program 3.

Program 3
function algo_03(matrix_rank)
% Introduction to linear algebra Chapter 5. problem 33
% Algorithm 3: find minimal dot product vector
% @author Hitoshi
  if nargin ~= 1;
    error('Usage: algor_03(matrix_rank).')
  end
  global MatrixRank;
  MatrixRank = matrix_rank;
  global CombMat;
  CombMat = gen_combinatorial_matrix(matrix_rank);
  % initialize candidate matrix
  cand_mat = zeros(matrix_rank, matrix_rank);
  cand_mat(1,:) = CombMat(1,:);
  comb_mat_size = size(CombMat);
  global CombRowCount;
  CombRowCount  = comb_mat_size(1);

  for i = 2:matrix_rank
    min_dotprod_row_idx = get_min_dotprod_row(cand_mat, i);
    cand_mat(i,:) = CombMat(min_dotprod_row_idx, :);
  end

  cand_mat
  det(cand_mat)
end
%%----------------------------------------------------------------------
% get minimal dotproduct row
% \param[in] cand_mat    candidate matrix
% \param[in] cur_row_idx current last row index
function min_dp_row_idx = get_min_dotprod_row(cand_mat, cur_row_idx)
  global MatrixRank;
  global CombMat;
  global CombRowCount;
  % init dot prod with the large one
  min_dotprod = dot(cand_mat(1,:), cand_mat(1,:)) * MatrixRank;
  min_dotprod_rowidx = 1;

  for i = 2:CombRowCount                % 1 has been used
    check_row = CombMat(i,:);
    % skip the same row if exists
    if check_same_row(cand_mat, check_row, cur_row_idx) == 1
      continue;
    end
    % check min dot product row
    sum_dotprod = 0;
    for j = 1:cur_row_idx
      sum_dotprod = sum_dotprod + abs(dot(cand_mat(j,:), check_row));
    end
    if min_dotprod > sum_dotprod
      min_dotprod = sum_dotprod;
      min_dotprod_rowidx = i;
    end
  end
  min_dp_row_idx = min_dotprod_rowidx;
end
%%----------------------------------------------------------------------
% check the same row exists
% \param[in] cand_mat  candidate matrix
% \param[in] check_row checking row entry
% \param[in] cur_row_idx current row index
% \return 1 when found the row
function ret = check_same_row(cand_mat, check_row, cur_row_idx)
  is_found = 0;
  % check the same entry in the candidate?
  for j = 1:cur_row_idx
    if all(check_row == cand_mat(j,:)) == 1
      is_found = 1;
      break;                       % the same entry found
    end
  end
  ret = is_found;
end


Program 3 generates a matrix that has relative large determinant value. But, they are not always the largest. For example, this program generates 32 when n = 5. But, the correct answer is 48 when n = 5. I could not proof why this doesn't work, if anybody know it, please let me know.

I needed to continue to seek for a better idea.

No comments: