Programming Practice

1. Let A be an m´n matrix and B be an n´m matrix. B is the transposition matrix of A, i.e., B=A^T, if and only if b_i,j=a_j,i for 0£i<m and 0£j<n, as shown below:

   

   Write a C program to input the size m and n of matrix A and randomly generate element a_i,j. Then, perform matrix transpostion of A to make B=A^T. Output the elements of matrix A and matrix B. Sample output:

   

2. Matrix transposition is a simple algorithm. However, for modern computers with cache memory, this algorithm suffers a serious cache miss problem. To deal with this problem a variation of matrix transposition which divides a n´n square matrix into block sub-matrices b´b as below:

   

   That is, transposition of matrix A is equivalent to transpose all blocks and then transpose the elements of each individual block. Write a C program to input the matrix size n and the block size b, where b is a factor of n, of square matrix A and randomly generate element a_i,j. Then, perform matrix transpostion of A to make B=A^T. Output the elements of matrix A and matrix B. Sample output:

   

3. Matrix transposition B=A^T store the transposed elements in memory location other than A itself. In some applications, the size of A is large and the original matrix may not be used later. In these cases, matrix transposition is usually performed as in-place transformation, AÜA^T, to save memory usage.

   

   Write a C program to input the size r of square matrix A and randomly generate element a_i,j. Then, perform in-place matrix transposition AÜA^T. Output the elements of matrix A before and after transposition. Sample output:

   

4. Let A be an m´n matrix and B be an n´p matrix. Matrix multiplication of A and B is matrix C=A´B defined as the following:

   

   Element C[i][j] is the inner product of the i-th row of matrix A and the j-th column of B. Write a C program to input three integers m, n, and p of matrix size matrix A, B, and C, and randomly generate element a_i,j and b_i,j for matrices A and B. Then, compute matrix multiplication C=A´B. Output matrices A, B, and C. Sample output:

   

5. In some applications, matrices are sparsed, instead of dense. A form of sparse matrix is triangular matrices, as the following figure:

   

   A is a lower triangular matrix with all elements above the diagonal being 0's, B is an upper triangular matrix with all elements below the diagonal being 0's, and C=A´B. Write a C program to input an integer r of square matrix size for matrices A, B, and C, and randomly generate element a_i,j, for i³j, and b_i,j, for i£j, for matrices A and B. Then, compute matrix multiplication C=A´B. Output matrices A, B, and C; do not print the upper triangle for matrix A and lower triangle for matrix B. Sample output:

   

6. A kind of sparse matrix is banded matrix. If square matrix A is of size n´n, a lower band element of bandwidth r is the element a_i,j such that 0<i-j£r and an upper band element of bandwidth s is the element a_i,j such that 0<j-i£s. Only the elements on the diagonal, on the lower band, and on the upper band can be non-zero; all other elements are called off-band elements and they are all zeros. The following is an example of an 8´8 banded matrix with the lower bandwidth r of 2 and the upper bandwidth s of 3:

   

   Let the size of square matrix A, B, and C be n´n. Also, let ra and sa be the lower and upper bandwidth of sqaure matrix A, respectively, and rb and sb be the lower and upper bandwidth of sqaure matrix B, respectively. If C=A´B, then the lower bandwidth of C is ra+rb and the upper bnadwdth of C is sa+sb with the limit of upper bound n-1. The non-zero elements of c_i,j is computed as the following formula:

   

   Write a C program to input an integer n of square matrix size for matrice A, B, and C, and two pairs of integer, ra and sa as the lower and upper bandwidth of matrix A, and rb and sb as the lower and upper bandwidth of matrix B. Randomly generate non-zero a_i,j and b_i,j for matrices A and B. Then, compute matrix multiplication C=A´B. Output matrices A, B, and C; do not output the off-band elements form matrices A, B, and C. Sample output:

   

7. Qaussian elimination is an algorithm for sovling systems of linear equations. A vaiation of Qaussian elimination, knwon as LU-decomposition, is to factorize the n´n coefficient matrix A into two n´n triangular matrices, L and U such that A=L´U, as the following:

   

   Let A^(k) be the (n-k)´(n-k) submatrix of A after removing the first k rows and the first k colums, i.e.,

   

   Starting from A⁽⁰⁾, matrices L and U are generated by comptuting, given A^(k), 0£k£n-1, submatrices A^(k+1) as the following steps:

   1. Compute elements of the k-th row of matrix U:  u_k,j = a_k,j, for k£j£n-1;
   2. Compute elements of the k-th column of matrix L:  l_i,k = a_i,k / a_k,k, for k£i£n-1; (note that, l_k,k==1)
   3. Compute elements of submatrix A^(k+1): a_i,j = a_i,j - l_i,k ´ u_k,j, for k<i, j£n-1.

   Write a C program to input an integer n of square matrix size for matrice A, L, and U, and randomly generate elements a_i,j, 0<a_i,j£1, for matrix A. Then, compute LU-decomposition A=L´U to generate matrices L and U. For the input matrix, keep a copy A1, and check whether A1=L´U to verify correctness of the program. Output matrices A, L, and U. Sample output: