Browse Prior Art Database

Out-of-Core LU Decomposition with Full Partial Pivoting

IP.com Disclosure Number: IPCOM000106652D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 48K

Publishing Venue

IBM

Related People

Mechentel, A: AUTHOR [+2]

Abstract

The problem solved is to factor large real*8 and complex*16 matrices, with full partial pivoting and matrix dimensions 10Kx10K or more. Compared to classical algorithm this method:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Out-of-Core LU Decomposition with Full Partial Pivoting

      The problem solved is to factor large real*8 and complex*16
matrices, with full partial pivoting and matrix dimensions 10Kx10K or
more.  Compared to classical algorithm this method:

1.  uses less real memory

2.  only o(N**2) instead of o(N**3) write operations to disk

3.  performs with super speed and enables efficient overlap of
    computation and i/o.

      The classical approach to LU decomposition is to factor a small
submatrix of A, update the rest entirely, and recur over the reduced
matrix A'.  This method requires o(n**3) reads and o(n**3) writes.
To do full partial pivoting, one requires a complete vertical swath

(a set of contiguous columns) of A to hold the factored columns and
another complete vertical swath to hold the columns to be updated.

      The disclosed method reduces the writes from o(n**3) to o(n**2)
and employes only one vertical swath plus one block of A.  Strassen
matrix multiplication, done on a block basis, optimizes the
performance of the updates of A.

     array stored on disk             real memory

                   J                 A_blk        B

       --------------------          -----      -----

      |  0 |  4 |  8 | 12 |         |     |    |  0  |

      |    |    |    |    |         |     |    |     |

      |----|----|---------|          -----     |-----|

      |  1 |  5 |  9 | 13 |                    |  1  |

      |    |    |    |    |                    |     |

      |----|----|---------|                    |-----|

      |  2 |  6 | 10 | 14 |                    |  2  |

      |    |    |    |    |                    |     |

      |----|----|----|----|   ...