next up previous
Next: Implementation of the Left-Looking Up: Sequential Out-Of-Core LU Factorization Previous: Right-Looking Algorithm

Left-Looking Algorithm

  As we shall see, from the standpoint of data access, the left-looking variant is better than the right-looking variant. To begin, we assume that


and that we wish to advance the factorization to the form


Comparing Eqs. 8 and 9 we see that the factorization is advanced by first solving the triangular system


and then performing a matrix-matrix product to update the rest of the middle block column of U,


Next we perform the factorization


and lastly the pivoting


Observe that data accesses all occur to the left of the block column being updated. Moreover, the only write access occurs within this block column. Matrix elements to the right are referenced only for pivoting purposes, and even this procedure may be postponed until needed with a simple rearrangement of the above operations.

In evaluating the I/O cost for the left-looking out-of-core LU factorization algorithm two variants of the left-looking algorithm will be considered. In the first we always store the matrix on disk in unpivoted form at all intermediate phases of the algorithm, writing out the whole matrix in pivoted form only in the last step of the algorithm. In this case pivoting has to be done ``on the fly'' when matrix blocks are read in from disk. In the second version of the algorithm the matrix is stored on disk in pivoted form.

Consider the version in which the matrix is stored in unpivoted form. Whenever a block is read in the whole tex2html_wrap_inline1513 block must be read so that it can be pivoted. Upon completion of a step the newly-factored block is the only block that is written to disk, except in the last step in which we write out all blocks in pivoted form so that the final matrix stored on disk is pivoted (although in some cases these writes may be omitted if an unpivoted matrix is called for - the pivots can always be applied later since they are stored in the pivot vector). At some general step k of the algorithm the I/O cost is


where the first term corresponds to reading and writing the block to be factored in this step and the second term to reading in the blocks to the left. Summing over k and adding in the time to write out all pivoted blocks in the last step, the total cost for this version of the left-looking algorithm is


Thus, to order tex2html_wrap_inline1519 the time to do the writes can be ignored. If we assume that reads and writes take approximately the same time (i.e., tex2html_wrap_inline1521 ), then comparison with Eq. 7 shows that this version of the left-looking algorithm should perform less I/O than the right-looking algorithm.

Now consider the version of the left-looking algorithm in which blocks are always stored on disk in pivoted form. In this case it is no longer necessary to read in all rows of an tex2html_wrap_inline1513 block, but it is necessary to write out partial blocks in each step. This is because the pivoting performed in the factorization of the block column must also be applied to the blocks to the left, which must then be written to disk. In some general step k all of the block to be updated must be read in and written out. The parts of the blocks to the left that must be read in form a stepped trapeziodal shape (see Figure 2(a)), while the parts of the blocks to the left that must be written out after applying the pivots for this step form a rectangle (see Figure 2(b)). Thus for step k>0 the I/O cost is


and for step k=0 the I/O cost is tex2html_wrap_inline1531 . Thus, the total I/O cost is


It is interesting to note that if reads and writes take the same time the two left-looking versions of the algorithm have the same I/O cost, and they both have a lower I/O cost than the right-looking algorithm. We therefore expect a left-looking algorithm to be better than a right-looking algorithm for out-of-core LU factorization.

Figure: This figure pertains to the left-looking LU factorization algorithm that stores the matrix in pivoted form. (a) The shaded blocks show the block columns read from disk in step k=5. The dark shaded block is the block being updated in this step. (b) The shaded blocks show the block columns written to disk in step k=5.

next up previous
Next: Implementation of the Left-Looking Up: Sequential Out-Of-Core LU Factorization Previous: Right-Looking Algorithm

Jack Dongarra
Thu Apr 18 21:51:24 EDT 1996