2011-05-03

(10) Max determinant problem: Conclusion

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.

No comments: