We study 5 kinds of matrix vector products:
 Row based access of the matrix
 Column based access of the matrix
 Row oriented vector operations
 Column oriented vector operations
 Direct matrix vector product through MATLAB’s call to BLAS
Using the above methods, we compute matrix vectors products with random matrices in four sizes: 10^{1}, 10^{2}, 10^{3}, 10^{4}, each size we run 10 trials and compute the average time spent. Based on a Intel i7 2.7GHz processor with 6MB L3 cache, the results are shown in Table 1 and the loglgo graph is displayed in Figure 1. The code is attached in 4.1. The speed, from fastest to slowest, is:
Table 1. Time taken in Matlab matrix vector products (s)
Size  A  B  C 
D

E 
10^{1}  0.0000  0.0000  0.0000  0.0004  0.0229 
10^{2}  0.0002  0.0002  0.0002  0.0022  0.0002 
10^{3}  0.0339  0.0173  0.0031  0.0331  0.0004 
10^{4}  4.7069  1.6411  0.1472  1.7983  0.0421 
Figure 1. Loglog graph time taken for various matrix sizes for matrix vector products
From Figure 1, we could clearly figure out the following conclusions:
 Rank 1: Direct matrix vector product through Matlab call
 Utilize native C code and roworiented vector. The for loop inside the C code is optimized for better performace.
 Rank 2: Roworiented vector operations.
 Almost the same as native Matlab. A bit slower then #1 since the forloop is not fully optimized.
 The roworiented vector operation takes advantage of data stored columnbycolumn in the memory. Continuous memory can be loaded easier and faster.
 Rank 3: Column based access of the matrix
 It’s the same idea as rank 2. The additional forloop slows it down.
 Rank 4: Column oriented vector operations
 Though there’s only one forloop. The matrix is accessed by row, and the row is not continuous memory blocks. Pointer jumping is slow.
 Rank 5: Row based access of the matrix
 Same idea as Rank 4 with an additional slow forloop.
Conclusion: Native Matlab calls C function is the fastest. Matrix is stored as column vectors in memory. Unnecessary forloop is not optimized and slow.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 
%% Problem 1 % Exploration of cache effects in Matlab matrix vector products. % Compare the time taken for various matrix sizes for matrix vector products % in which the matrix is accessed in the different ways discussed in class. % Submit a single loglog graph with five different labeled/marked curves. % To help you I have provided the Matlab code snippet from the Lecture here. % Discuss your results. % Issues: % 1. Row based access of the matrix % 2. Column based access of the matrix % 3. Row oriented vector operations % 4. Column oriented vector operations % 5. Direct matrix vector product through MATLAB's call to BLAS n = 4; % from 10^1 to 10^5 m = 5; % m methods trials = 10; mvtimes = zeros(n, m); for T = 1 : trials for N = 1 : n M = 10 ^ N; s(N) = M; A = rand(M); b = rand(M, 1); c = zeros(M, M); tic for i = 1 : M for j = 1 : M c(i) = c(i) + A(i,j) * b(j); end end mvtimes(N, 1) = mvtimes(N, 1) + toc; c=zeros(M,1); tic for j = 1 : M for i = 1 : M c(i) = c(i) + A(i, j) * b(j); end end mvtimes(N, 2) = mvtimes(N, 2) + toc; c=zeros(M,1); tic for j = 1 : M c(:) = c(:) + A(:, j) * b(j); end mvtimes(N, 3) = mvtimes(N, 3) + toc; c=zeros(M,1); tic for i = 1 : M c(i) = c(i) + dot(A(i,:), b(:)); % note dot product row times column end mvtimes(N, 4) = mvtimes(N, 4) + toc; c=zeros(M,1); tic c = A * b; mvtimes(N, 5) = mvtimes(N, 5) + toc; end end mvtimes = mvtimes / trials %% Plot for Problem 1 hold on; fontsize = 15; set(0,'DefaultAxesFontName', 'Times New Roman') set(0,'DefaultTextFontname', 'Times New Roman') set(findall(gcf,'type','axes'),'fontsize', fontsize) set(findall(gcf,'type','text'),'fontSize', fontsize) g1 = loglog(mvtimes(:,1), 'g'); g2 = loglog(mvtimes(:,2), 'b'); g3 = loglog(mvtimes(:,3), 'r'); g4 = loglog(mvtimes(:,4), 'c'); g5 = loglog(mvtimes(:,5), 'k'); legend([g1, g4, g2, g3, g5], ... 'Row based access of the matrix', ... 'Column oriented vector operations', ... 'Column based access of the matrix', ... 'Row oriented vector operations', ... 'Direct matrix vector product through MATLAB call to BLAS'); title('Loglog graph for time taken for various matrix sizes for matrix vector products'); ylabel('Log(Time Taken for matrix vector products)'); xlabel('Log(Size of Matrix)'); hold off; 