It just ain't normal, folks

Second project, Computer Science P573

Notice I've updated the zip file containing the Matlab version, and put it into zip file updated_norms.zip. You can use either of the two, just be sure to fix my mistake on the 2-norm if you use the original version.
Computing the norm of a vector occurs all over the place in scientific computing. The most common case is when an iterative method is making successive approximations to a solution, with an error vector e = x - solution. In this case, a stopping test might be 
        norm(e) < 1.0e-8
Usually you don't know the solution to be able to define e (why on earth compute it, if you already know it?), so you use a different but related vector. For solving linear systems Ax = b where A is an n × n matrix, the stopping test would be 
        norm(b - Ax) < 1.0e-8
where r = b - Ax is the residual vector . Norms are needed for solving least squares problems, nonlinear optimization, and many other places. For finite dimensional Hilbert spaces (like plain old Euclidean spaces) if a sequence of vectors r1 r2 r3, ... have 2-norms that go to zero as you proceed, then all other norms (1-norm, infinity norm, ...) also go to zero. So you are relatively free to choose which one to use.

Time computing three different vector norms, to see which is fastest. A Matlab version for computing the vector norms is in the files norm2.m, norm1.m, and norminf.m, but find out which is best using a compiled language.

The steps are:

  1. Write norm2.xxx, norm1.xxx, and norminf.xxx, where xxx is the appropriate extension for the language you are using. If you do use Fortran, make it .f90, .f95, or .f2k - most compilers treat .f files as Fortran 77 code.
  2. Write a test harness driver.xxx. It will
    1. Read in four integer parameters from a file called "sizes". The parameters are nopers, nmin, nmax, and skip.
    2. For each of the three norms, loop over the values of n from nmin to nmax with stride of skip. The number of repetitions to use depends on the clock resolution and overhead of the machine you are using ... but you know how to find that. For this project, just use nopers = 107 for simplicity.
    3. Write out three plain text (ASCII) files that have the results for the corresponding norms. Name the files norm1results, norm2results, and norminfresults. Each row in a file will have three numbers: The length n of the vector used, the average time to compute its norm, and the rate of computation in million ops per second. Examples of those (with fake data) are in this directory.
  3. Use the Matlab script plotnorms.m to view thne results. You can modify it as you want, just be sure any plots are fully annotated.
  4. Come to some conclusion about which norm is fastest, if any, and write it up in a plain test file. Nothing lengthy is needed, just be sure to also put in the file what machine, compiler options, etc. that were used. Put your name there as well.

The drivenorms.m file gives you a framework that you can follow in your compiled version(s), if it helps. Be sure to put each of the norm functions into a separate file, or some compilers will use IPO and possibly make the timings unrealistic. The m-file that will read in from files and plot the results from your compiled version is plotnorms.m, but feel free to modify it if there's a better way to show the results.

Until you get everything debugged, use some light-weight numbers of the parameters. E.g., let the file "sizes" have 

        1000000  2000  8000 1000
which specify nopers = 1000000, nmin = 2000, nmax = 8000, and a stride of 1000. That would lead to seven timings for each norm, for vector lengths n = 2000, 3000, 4000, 5000, 7000, 8000. Once everything is hunky-dory, ramp up a bit. Use nmax ≥ 100000 and set nmin and skip so that you will have at least 40 timings to plot for each norm. You can choose the parameters however you want to get valid results, subject only to the two requirements on nmax and number of timings per norm.

An easy way to create skip to make sure you have 40 data points is skiptomalou = linspace(nmin, nmax, 40); skip = skiptomalou(2) - skiptomalou(1);

Download the zip file unnormal.zip and read the file "info" and the Matlab scripts provided - they will supply further details.

  1. Started: Mon 21 Sep 2009, 01:40 PM
  2. Modified: Mon 21 Sep 2009, 01:48 PM, to subdue the pre indicators and add on some explanatory bloviation, and to clarify "framework" above
  3. Modified: Mon 21 Sep 2009, 07:11 PM to bloviate further
  4. Modified: Mon 05 Oct 2009, 06:11 PM to add the directory and zip file for updated_norms/updated_norms.zip.
  5. Last Modified: Mon 05 Oct 2009, 06:12 PM