Linear Algebra/Topic: Speed of Calculating Determinants/Solutions

Solutions Most of these problems presume access to a computer. Problem 1 Computer systems generate random numbers (of course, these are only pseudo-random, in that they are generated by an algorithm, but they pass a number of reasonable statistical tests for randomness). <li> Fill a array with random numbers (say, in the range ). See if it is singular. Repeat that experiment a few times. Are singular matrices frequent or rare (in this sense)? <li> Time your computer algebra system at finding the determinant of ten arrays of random numbers. Find the average time per array. Repeat the prior item for arrays, arrays, and arrays. (Notice that, when an array is singular, it can sometimes be found to be so quite quickly, for instance if the first row equals the second. In the light of your answer to the first part, do you expect that singular systems play a large role in your average?) <li> Graph the input size versus the average time. Answer <li> Under Octave, rank(rand(5)) finds the rank of a matrix whose entries are (uniformily distributed) in the interval . This loop which runs the test times octave:1> for i=1:5000 > if rank(rand(5))<5 printf("That's one."); endif > endfor produces (after a few seconds) returns the prompt, with no output. The Octave script function elapsed_time = detspeed (size) a=rand(size); tic(); for i=1:10 det(a); endfor elapsed_time=toc(); endfunction lead to this session. octave:1> detspeed(5) ans = 0.019505 octave:2> detspeed(15) ans = 0.0054691 octave:3> detspeed(25) ans = 0.0097431 octave:4> detspeed(35) ans = 0.017398 <li> Here is the data (rounded a bit), and the graph. (This data is from an average of twenty runs of the above script, because of the possibility that the randomly chosen matrix happens to take an unusually long or short time. Even so, the timing cannot be relied on too heavily; this is just an experiment.) x300px Problem 2 Compute the determinant of each of these by hand using the two methods discussed above. <li> <li> <li> Count the number of multiplications and divisions used in each case, for each of the methods. (On a computer, multiplications and divisions take much longer than additions and subtractions, so algorithm designers worry about them more.) Answer The number of operations depends on exactly how the operations are carried out. <li> The determinant is . To row reduce takes a single pivot with two multiplications ( times plus , and times plus ) and the product down the diagonal takes one more multiplication. The permutation expansion takes two multiplications ( times and times ). <li> The determinant is . Counting the operations is routine. <li> The determinant is . Problem 3 What array can you invent that takes your computer system the longest to reduce? The shortest? Answer One way to get started is to compare these under Octave: det(rand(10));, versus det(hilb(10));, versus det(eye(10));, versus det(zeroes(10));. You can time them as in tic(); det(rand(10)); toc(). Problem 4 Write the rest of the FORTRAN program to do a straightforward implementation of calculating determinants via Gauss' method. (Don't test for a zero pivot.) Compare the speed of your code to that used in your computer algebra system. Answer This is a simple one. DO 5 ROW=1, N PIVINV=1.0/A(ROW,ROW) DO 10 I=ROW+1, N DO 20 J=I, N A(I,J)=A(I,J)-PIVINV*A(ROW,J) 20 CONTINUE 10 CONTINUE 5 CONTINUE Problem 5 The FORTRAN language specification requires that arrays be stored "by column", that is, the entire first column is stored contiguously, then the second column, etc. Does the code fragment given take advantage of this, or can it be rewritten to make it faster, by taking advantage of the fact that computer fetches are faster from contiguous locations? Answer Yes, because the is in the innermost loop.