したたり算法

3 months ago

skip to main |
skip to sidebar
## 2011-05-24

## 2011-05-03

###
(10) Max determinant problem: Conclusion

###
(9) Max determinant problem: Joachim's improvement

## 2011-05-02

###
(8) Max determinant problem: Algorithm 4, combination

Mathematics, programming, and a little bit of my life.

Conclusion

I and some of my colleagues think about max determinant problem in this article. I don't know there is a better method than combination method. But this algorithm is sufficient to answer the Strang's question, case n=6. In the deep mathematics, people know the max determinant up to 100, at least. The method I show here has nothing compare to them, my method is so primitive. These mathematicians researched on this problem around 1960. I assume they even don't use a computer. I use today's computer, but, I can not have n = 10 case. How they know n = 100? I do like, ``I see the answer is in the one of 10 million, then, I can just write a program to find it.'' I feel having a computer makes me dull.

The following is the timing result on my computer (Core2 Duo P8400@2.26GHz, Linux 2.6.35, Windows Vista). Please note, Joachim's algorithm can reduce the n by 1. I measured Joachim's implementation with the time command on Linux, octave/matlab implementation with tic/toc command. $n<=5$ case, the elapsed time is too small and user time is 0. The ``()'' shows an estimated value.

This time, we implemented the same algorithm with octave, matlab, and C++. If we normalized the result with the number of the determinant computation, C++ implementation is 3.7 times faster than matlab implementation, 55 times faster then octave implementation. How you interpret this number is depends on your point of view. But I am impressed that the matlab implementation is only 3.7 times slower than C++.

Acknowledgements

Thanks to Leo, Joachim, and Marc for the discussion.

I and some of my colleagues think about max determinant problem in this article. I don't know there is a better method than combination method. But this algorithm is sufficient to answer the Strang's question, case n=6. In the deep mathematics, people know the max determinant up to 100, at least. The method I show here has nothing compare to them, my method is so primitive. These mathematicians researched on this problem around 1960. I assume they even don't use a computer. I use today's computer, but, I can not have n = 10 case. How they know n = 100? I do like, ``I see the answer is in the one of 10 million, then, I can just write a program to find it.'' I feel having a computer makes me dull.

The following is the timing result on my computer (Core2 Duo P8400@2.26GHz, Linux 2.6.35, Windows Vista). Please note, Joachim's algorithm can reduce the n by 1. I measured Joachim's implementation with the time command on Linux, octave/matlab implementation with tic/toc command. $n<=5$ case, the elapsed time is too small and user time is 0. The ``()'' shows an estimated value.

This time, we implemented the same algorithm with octave, matlab, and C++. If we normalized the result with the number of the determinant computation, C++ implementation is 3.7 times faster than matlab implementation, 55 times faster then octave implementation. How you interpret this number is depends on your point of view. But I am impressed that the matlab implementation is only 3.7 times slower than C++.

Acknowledgements

Thanks to Leo, Joachim, and Marc for the discussion.

Labels:
linear algebra,
math

Joachim's improvement

Recently, I have an activity to support for recent Japanese disaster. I would like to continue this activity. On the other hand, I have not so much time for my Sunday research.

Meantime, my colleague Joachim R. found a improved method of the combination solution. It's a nice method and I would like to introduce it here.

The basic idea is the following. Determinant doesn't change by elimination, therefore, we can eliminate the first column of {1,-1} matrix. Without loss of generality, we can say a_{1,1} is 1. (Because if it is -1, we can multiply -1 to the first row and switch the sign. In this case, the determinant also altered the sign, but we could always exchange the row to switch back the sign.) Also, from det(A) = det(A^{T}), we can apply the same operation to the first column. At the end, we could have all 1 row at the first row.

Let's write down this procedure.

Where, k is the number of -1 in the first row, j is the number of -1 in the first column. n is the size of the matrix. Therefore, we could know the nxn matrix's max determinant with computing (n-1)x(n-1) {0,1} matrix's max determinant. You can find this rule in http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html, equation (3) α_{n} = 2^{n-1}β_{n-1}. But mathworld did not give us the proof of this equation. This Joachim's method is one of the proof. Since it is simple and comprehensive, I think this might be a standard proof of equation (3).

Again, this Joachim's method can decrease the matrix size by one, we can get enormous speed up. For instance, n = 7 case, we can get 128 times faster.

This is one example that research of mathematics and algorithm is important. It is quite difficult to build a 128 times faster computer. Compare to the first algorithm with the Joachim's improvement, the difference of elapsed time is 100,000. It is quite difficult to build a 100,000 times faster computer. In mathematics or computer science, the word ``guts'' has no meaning, only ``cleverness'' has meaning.

Recently, I have an activity to support for recent Japanese disaster. I would like to continue this activity. On the other hand, I have not so much time for my Sunday research.

Meantime, my colleague Joachim R. found a improved method of the combination solution. It's a nice method and I would like to introduce it here.

The basic idea is the following. Determinant doesn't change by elimination, therefore, we can eliminate the first column of {1,-1} matrix. Without loss of generality, we can say a_{1,1} is 1. (Because if it is -1, we can multiply -1 to the first row and switch the sign. In this case, the determinant also altered the sign, but we could always exchange the row to switch back the sign.) Also, from det(A) = det(A^{T}), we can apply the same operation to the first column. At the end, we could have all 1 row at the first row.

Let's write down this procedure.

Where, k is the number of -1 in the first row, j is the number of -1 in the first column. n is the size of the matrix. Therefore, we could know the nxn matrix's max determinant with computing (n-1)x(n-1) {0,1} matrix's max determinant. You can find this rule in http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html, equation (3) α_{n} = 2^{n-1}β_{n-1}. But mathworld did not give us the proof of this equation. This Joachim's method is one of the proof. Since it is simple and comprehensive, I think this might be a standard proof of equation (3).

Again, this Joachim's method can decrease the matrix size by one, we can get enormous speed up. For instance, n = 7 case, we can get 128 times faster.

This is one example that research of mathematics and algorithm is important. It is quite difficult to build a 128 times faster computer. Compare to the first algorithm with the Joachim's improvement, the difference of elapsed time is 100,000. It is quite difficult to build a 100,000 times faster computer. In mathematics or computer science, the word ``guts'' has no meaning, only ``cleverness'' has meaning.

Labels:
linear algebra,
math

Algorithm 4: combination

Row exchange only changes the sign of determinant. Therefore, we don't need permutation, but only combination is necessary. The row of n by n matrix has n elements. The permutation of {-1,1} is 2^6 = 64. The number of combination of these is _{2^6}C_{6} = 74974368. Because this is just around double of 2^{25}, I expected that this will take only five hours. The implementation of this idea is Program 4.

Program 4

I got the idea using combination immediately after the permutation idea, therefore, I wanted to skip the algorithm 3.5. However, I made a mistake and implemented permutation of rows. What a terrible mistake. The difference of permutation method and combination method is 6! cases. This is 720. I estimated 60 days for the computation time of permutation method. But, the combination method is 720 times faster, it took only two hours.

I got the correct result by this program. Actually, there is a nice side effect. I could not find any concrete matrix that has the max determinant from the Web. So, this is one of the 6x6 matrix that has the max determinant value.

The function gen_combinatorial_matrix() is generating permutation of row. I omit the implementation since it's not substance and very easy to implement anyway.

Row exchange only changes the sign of determinant. Therefore, we don't need permutation, but only combination is necessary. The row of n by n matrix has n elements. The permutation of {-1,1} is 2^6 = 64. The number of combination of these is _{2^6}C_{6} = 74974368. Because this is just around double of 2^{25}, I expected that this will take only five hours. The implementation of this idea is Program 4.

Program 4

function MaxDeterminant = algo_04(matrix_rank) % Introduction to linear algebra Chapter 5. problem 33 % Algorithm 4: combination method % @author Hitoshi if nargin ~= 1; error('Usage: la_chapt5_33_comb_row(matrix_rank).') end MatrixRank = matrix_rank; % generate all the row combination (simple permutation) CombMat = gen_combinatorial_matrix(matrix_rank); comb_mat_size = size(CombMat); CombRowCount = comb_mat_size(1); curChoise = 1:MatrixRank; global MaxDet MaxDetMat MaxDet = 0; MaxDetMat = []; tic while (1) mat = CombMat(curChoise,:); d = det(mat); if d > MaxDet MaxDet = d; MaxDetMat = mat; end find_idx = 0; for i = MatrixRank:-1:1 if curChoise(i) < CombRowCount - (MatrixRank - i) find_idx = i; break end end if find_idx == 0 break % done else start_val = curChoise(find_idx) + 1; curChoise(:,find_idx:MatrixRank) = start_val:(start_val + MatrixRank - find_idx); end end toc MaxDet MaxDeterminant = MaxDetMat; end

I got the idea using combination immediately after the permutation idea, therefore, I wanted to skip the algorithm 3.5. However, I made a mistake and implemented permutation of rows. What a terrible mistake. The difference of permutation method and combination method is 6! cases. This is 720. I estimated 60 days for the computation time of permutation method. But, the combination method is 720 times faster, it took only two hours.

I got the correct result by this program. Actually, there is a nice side effect. I could not find any concrete matrix that has the max determinant from the Web. So, this is one of the 6x6 matrix that has the max determinant value.

The function gen_combinatorial_matrix() is generating permutation of row. I omit the implementation since it's not substance and very easy to implement anyway.

Labels:
linear algebra,
math

Subscribe to:
Posts (Atom)