Algorithm 1: permutation method

Since the component of matrix is limited to -1 or 1, we can generate all the permutation of 6x6 matrix and compute their determinant, then find the max determinant value. Program 1 shows the implementation.

Program 1

function algo_01(mat_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 1: generate all the combination and test method. % @author Hitoshi if nargin ~= 1; error('Usage: algo_01(mat_rank)') end % possible element set A_i = {-1, 1} SetA = [-1 1]; cand_mat = zeros(1, mat_rank * mat_rank); global MAXDET global MAXDET_MAT % We know det I = 1, therefore, it is a good initial value. MAXDET = 1; MAXDET_MAT = zeros(1, mat_rank * mat_rank); gen_comb_set(SetA, cand_mat, mat_rank, 1); MAXDET_MAT fprintf(1, 'max detderminant = %d.\n', MAXDET); end %%---------------------------------------------------------------------- % Execute depth num_set loop by recursion to generate matrix candidates. % % \param SetA element candidate set % \param cand_mat current candidates % \param mat_rank rank of matrix (not exactly the rank, size of n) % \param loopdepth parameter to simulate for-loop depth by recursion. function gen_comb_set(SetA, cand_mat, mat_rank, loopdepth) global MAXDET; global MAXDET_MAT; num_set = mat_rank * mat_rank; num_cand = size(SetA); szSetA = size(SetA); % This should be assert(sum(szSetA == [1 2]) == 2) if sum(szSetA == [1 2]) ~= 2 error('Not assumed set candidate matrix (should be 1x2)') end if loopdepth > num_set MA = reshape(cand_mat, mat_rank, mat_rank); det_a = det(MA); if det_a > MAXDET MAXDET = det_a; MAXDET_MAT = MA; end else for j = 1:szSetA(2) cand_mat(loopdepth) = SetA(j); gen_comb_set(SetA, cand_mat, mat_rank, loopdepth + 1); end end end

I just ran this program on Intel Core2 2.26GHz machine's octave. But it doesn't stop after an hour. I switched to 5x5 matrix, it took two hours and j10 minutes. I should have first thought how large is the combination. In 5x5 matrix case, it is 2^{25}, which means, 33554432, 3.3 * 10^{7}. In 6x6 case, it is $2^\{36\}$, which means 68719476736, 6.8 * 10^{10}. If I run this program on my machine, it took more than 2200 hours, i.e., 92 days, almost three months. This is too much time for just a practice problem. I suspect there is a better way.

## No comments:

Post a Comment