Scientific Computing, homework assigned Mar 10/11, due in class Mar 24.

Part 1.

Do the matrix transpose exercise of homework 4 again.  This time, be sure
that your code is formally efficient in time and space.  You may employ
workspace arrays of size m or n (or of size nmbelems if you believe you
need that), but not of size m*n, m*nmbelems, or n*nmbelems.  Likewise, the
number of operations in your code must not grow faster than nmbelems; it
must not grow as m*n, m*nmbelems, or n*nmbelems.

If you believe that the code you handed in for homework 4 meets those
requirements, just make another copy and hand it in again.

Only formal efficiency counts for this exercise.  In Matlab you can gain
much practical efficiency by using what Van Loan calls "vectorizing"
constructs instead of loops.  For this exercise that is immaterial; feel
free to use loops, and be aware that the formal cost of a vector operation
is usually the size of the vector.

I provide a test matrix that is slightly different than the one supplied
previously with homework 4.  The matrix has m=5 and n=4, and is upper
bidiagonal of order 4x4 plus one additional entry in the lower left
corner.  The eight non-zero entries are:

  (  1  -1          )
  (      2  -1      )
  (          3  -1  )
  ( .5           4  )
  (                 )

For this matrix, in the C context, rowbase=(0,2,4,6,8,8),
colind=(0,1,1,2,2,3,0,3), and elems=(1,-1,2,-1,3,-1,.5,4).  In the Matlab
context rowbase=(1,3,5,7,9,9), colind=(1,2,2,3,3,4,1,4), and
elems=(1,-1,2,-1,3,-1,.5,4).  Your code should be correct for an arbitrary
sparse matrix; not just for the one that is provided as a test case.

Here are links to contexts for the sparse matrix exercise in C and Matlab.
You are welcome to choose another suitable language if you wish.  The
links are to the partial answers for homework 4.  The programs provide
full code for the 1-norm and inf-norm components of that earlier homework,
but the matrix transpose routines have a header only and then an "abort'
or 'error' statement.

C context.

Matlab context.

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