Scientific Computing, homework assigned Feb 17/20, due in class Mar 3.


This is a programming exercise that concerns elementary sparse matrix
manipulations.  We choose to represent a sparse matrix by storing the
elements in a one-dimensional array in the natural row order detailed
below.  Arrays will be indexed starting at 0 in Fortran and C, and
starting at 1 in Matlab.  The following description applies first to the
indexing that starts at 0; the modifications for the Matlab indexing
convention are indicated in parenthesese.

The indexing and element data that fully specify the sparse matrix A are:

  m (integer): number of rows in the matrix.

  n (integer): number of columns in the matrix.

  nmbelems (integer): number of non-zero elements.

  rowbase ([0:m] integer array).  For 0<=i<=m, rowbase[i] contains the
  number of non-zero elements in rows before row number i.  Therefore,
  for 0<=i<m, rowbase[i] is the starting address for storage of the
  elements from row i, and rowbase[i+1]-rowbase[i] is the number of
  elements of row i.  (In the Matlab context the array rowbase is indexed
  starting at 1, of course, but moreover rowbase[i] contains 1 plus the
  number of non-zero elements in rows before row number i; this makes it
  again the starting address for storage of elements from row i.)

  colind ([0:nmbelems-1] integer array).  For 0<=k<nmbelems, colind[k]
  contains the column index of the non-zero element number k (elements
  numbered sequentially by row starting at 0).  (In the Matlab context
  colind is indexed from 1 and the row and column indices start at 1.)

  elems ([0:nmbelems-1] real/double array).  For 0<=k<nmbelems,
  elems[k] contains the value of non-zero element number k.  (In the
  Matlab context elems is indexed from 1.)

I provide a test matrix for which m=5 and n=4 and which is upper
bidiagonal of order 4x4.  The seven non-zero entries are:

  (  1  -1          )
  (      2  -1      )
  (          3  -1  )
  (              4  )
  (                 )

For this matrix, rowbase=(0,2,4,6,7,7), colind=(0,1,1,2,2,3,3), and
elems=(1,-1,2,-1,3,-1,4).  (In Matlab, rowbase=(1,3,5,7,8,8) and
colind=(1,2,2,3,3,4,4).)

The exercise is to write procedures for three simple sparse matrix
operations.

 1. Compute the 1-norm, defined as the maximum over j of the sum of
    abs values of matrix elements in column j.

 2. Compute the inf-norm, defined as the maximum over i of the sum of
    abs values of matrix elements in row i.

 3. Form the transpose matrix in the same sparse storage format (the
    tranpose matrix has n rows and m columns.

Here are links to contexts for the sparse matrix exercise in Fortran, C
and Matlab.  You are welcome to choose another suitable language if you
wish.  You may also modify the interfaces to the procedures if you find
that desirable (for instance, if you use Fortran you may need to provide
workspace).

Fortran context.

C context.

Matlab context.

The context is a main program and some test functions.  Say you place the
Fortran program in spmat.f and the C program in spmat.c.  On our Sun
system you would compile and link the Fortran with
 % f77 -o spmat spmat.f
and the C with
 % cc -o spmat -L/usr/lib -lm spmat.c
and then execute with
 % ./spmat
The Matlab program would be placed in spmat.m, and then you give the
command 'spmat' from within your Matlab session.  Whatever language you
choose, you first have to supply the missing bodies to the routines that
compute the matrix norms and matrix transpose.