 Home Geography Direct methods for sparse matrices

# Exercises

• 10.1 By means of a Fortran program that first links all the rows with the same row counts, demonstrate that the rows of a matrix can be ordered in O(n) time so that they are in order of ascending row counts, given that the row counts are already available.
• 10.2 Show how the auxiliary storage in Table 10.2.1 can be reduced from 6n to 5n integers by holding only one header array.
• 10.3 Give Fortran code for removing a row from a chain of rows having tau entries and inserting it into a chain of rows having taul entries.
• 10.4 Give an example where scanning rows and columns in the order given by the algorithm in Section 10.2 does not access entries in order of increasing Markowitz count.
• 10.5 Give an example where the search strategy of Section 10.2 must search more than half the matrix before termination.
• 10.6 Construct code for performing the operations of Figure 10.3.2 in the case where the structure of LU is not known in advance. Assume that the entries in the columns of A are stored in order and that the LU factorization has proceeded to column к — 1.
• 10.7 Write Fortran code to solve a unit upper triangular system where the matrix is stored by rows.
• 10.8 Express the permutation (1,2,3,4,5) ^ (3,5,1,2,4) as a sequence of interchanges and show that the effect of applying them to a vector is the same. Write Fortran code that uses interchanges to reorder a vector in place.
• 10.9 Write code to solve Lx = Pb when L is unit lower triangular and PTL is held by columns.
• 10.10 Write loop-free code for SOLVE for the example in Figure 10.8.1.
• 10.11 Using the operation codes in Figure 10.9.1, write data for the interpretative code for the SOLVE phase for the example in Figure 10.8.1.
• 10.12 Show that convergence of the method outlined in (10.10.6) depends on the spectrum of the matrix (10.10.7).
• (k) (k)
• 10.13 Find a small quantity that when added to the diagonals a(i) and aW ensures
• (k)

positive definiteness, regardless of the values of the other entries, when entry ah) is dropped during the partial factorization of a symmetric positive-definite matrix.

10.14 It may be verified that the matrix is positive definite for a in the range 0.0164 < a < 1. Thus, the two matrices are ‘neighbours’, but A2 is indefinite. If we were to use the cautious drop tolerance approach of Exercise 10.13 with threshold 0.025, what resulting sparse matrix would be used instead of A2?

10.15 In Section 10.7, we advocated switching to full form in the factorization, essentially replacing zeros by entries to take advantage of dense blocks for vectorization and parallelization. In Section 10.10, we advocated replacing small numbers by zero, to gain more sparsity. How might the two potentially conflicting strategies fit together?

 Related topics