Tuffy, the thirsty dog


A friendly pocket monster

CSC 726, Parallel Algorithms
QR Factorization

This page contains a list of examples and helpful code fragments for running your QR factorization code.

Recall that our linear system is:

g = H f

where f is a vector size n*n by 1, H is an matrix size 2*n*n by n*n, and g is a vector size 2*n*n by 1. Note that the system is over determined, so you will need to compute least-squares solution. QR factoriziation is an important method for least squares problems such as this one. A summary of the method and how it applies to least squares problems is linked here.

The vector f contains the pixel values of an n by n, image stacked by columns. Similarly, g contains the stacked pixel values for two images. The vector g represents two observations, and the matrix H represents the blurring operator for both observations. The inverse problem posed here is to find f. For the following files, use your code to compute an estimate of f using g and H. In the example files below, n = 16. For purposes of code validation, the original vector f is also provided. Your solution should be very close to the given f. Later, you will have the opportunity to solve problems for which f is not available.

The following ".dat" files contain big-endian binary data. Note on file format: These are binary files. The first 4 bytes form a big-endian integer M, representing the number of rows in the object. The second 4 bytes form a big-endian integer N, representing the number of columns in the object. The next M * N * sizeof(double) bytes are big-endian double precision values in column-major order. A sample seqential C routine to read this format is included here. Sample sequential C++ code is here.

Also, you will want to convert matricies to a graphics format for viewing. A sequential program named dat2ppm to convert to the PPM graphics format is compiled and (currently) installed in /var/tmp/bin on genesis.cs.wfu.edu. The program dat2ppm takes two options for controlling the colormap: dat2ppm -gray filename.dat produces a gray-scale image; dat2ppm -jet filename.dat produces a pseudo-color image using a colormap similar to Matlab's "jet" colormap.

You can view PPM graphics files on genesiswith the display command from the ImageMagick software package (already installed on genesis).

Sample Input Data for QR Factorization
A small problem for getting things tested and working.

  • g.dat , a simulated observation (512 x 1)
  • h.dat , a simulated blurring operator (512 x 256)
  • f.dat , the unknown. (256 x 1)

What do these images look like ? The vector f is un-stacked into a square 16 x 16 image. The vector g is split into the top and bottom regions g1 and g2, and each is un-stacked into a square 16 x 16 image. For illustration purposes, each image is enlarged (via block replication). Then, we have:

    f     g1     g2

The matrix h is illustrated in the 'jet' colormap below. Blues and cool tones indicate low values; oranges, reds and warm tones indicate high values. The top and bottom halves of h are structured: they are block circulant with circulant blocks.

      Matrix h
A somewhat larger problem.
Now that your code is working smoothly, try a slightly larger problem, based on an image size 32 x 32.

For the 2048 x 1024 matrix "h_32.dat" above, what does the QR factorization look like ?



A more interesting problem.
You can also try a larger problem, based on an image size 64 x 64.


An ill-conditioned, spatially varying problem.
Finally, we have arrived at our first real problem. The following files present an ill-conditioned simulated spatially-varying blur on 64x64 images. You will need to include regularization to produce an acceptable restoration.

Images:
g_0    
g_1    
f    




The data above is also available in little-endian byte order