User Tools

Site Tools


gibson:teaching:fall-2014:math445:lab5

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
gibson:teaching:fall-2014:math445:lab5 [2014/11/12 19:16]
gibson
gibson:teaching:fall-2014:math445:lab5 [2015/03/09 13:39] (current)
gibson
Line 50: Line 50:
 </​code>​ </​code>​
  
-or equivalently 
- 
-<​code>​ 
-N=100; 
-p=(G^N)*p; 
-</​code>​ 
  
 After that is complete the elements of ''​p''​ give the probabilities that a random web surfer will end up at the web pages listed in ''​U'',​ and you can rank the pages in ''​U''​ according to their probabilities in ''​p''​. Look up the ''​sort''​ command in the Help menu and find a way to print the list of websites in order of their rank. Turn in the list of the top 10, the fraction of the time a random web surfer would spend in each one of those 10, and your code to complete the Lab.  After that is complete the elements of ''​p''​ give the probabilities that a random web surfer will end up at the web pages listed in ''​U'',​ and you can rank the pages in ''​U''​ according to their probabilities in ''​p''​. Look up the ''​sort''​ command in the Help menu and find a way to print the list of websites in order of their rank. Turn in the list of the top 10, the fraction of the time a random web surfer would spend in each one of those 10, and your code to complete the Lab. 
Line 146: Line 140:
  
  
-Now write a script that tests and times these algorithms on link matrices L of sizes M = 32, 64, 128, 256, 512, and 1024. You can use this Matlab function to produce synthetic data for testing any given value of M+Now write a script that tests and times these algorithms on link matrices L of sizes M = 32, 64, 128, 256, ....up to whatever power of two your computer can handle. It's smart to develop ​and test your code on a smaller set of M, perhaps just M = 32, 64, 128As a starting point, here's the code we developed in class to measure execution time of full versus sparse matrices. 
 + 
 +<code matlab>​ 
 + 
 +% script to compare full versus sparse matrix multiplication 
 + 
 +for n=1:12 
 +   
 +  % set up random M x M Ax=b problem 
 +  m = 2^n;  
 +  A = randomL(m);​ 
 +  x = randn(m,​1);​ 
 + 
 +  % measure execution time of sparse matrix multiplication 
 +  tic; 
 +  b = A*x;    
 +  Tsparse(n) = toc; 
 + 
 +  % measure execution time of full matrix multiplication 
 +  A = full(A); 
 +  tic; 
 +  b = A*x;    
 +  Tfull(n) = toc; 
 + 
 +  M(n) = m; 
 +end   
 +</​code>​ 
 + 
 +You can use this Matlab function to produce synthetic data for testing any given value of M
  
 <code matlab> <code matlab>
Line 155: Line 177:
   L = sparse(M,​M);​   L = sparse(M,​M);​
   ​   ​
-  for j=1:M +  for j=1:M                     
-    i = randi(M, maxlinks, 1); % pick maxlinks ​random ​pages +    i = randi(M, maxlinks, 1); % get vector of random ​numbers between 1 and M 
     for n = 1:maxlinks     for n = 1:maxlinks
-      L(i(n),j) = 1;+      L(i(n),j) = 1;           % create links from page j to the random pages i
     end     end
   end   end
   ​   ​
 end end
-<​code>​+</code>
  
  
gibson/teaching/fall-2014/math445/lab5.1415848585.txt.gz · Last modified: 2014/11/12 19:16 by gibson