External Memory Algorithms for a Sparse Direct Solver. |
|
|
|
|
|
|
| The growth of the web has reduced the cost of large memories and disk storage, enabling Gigabyte memories and disks for desktop computers. However, exploiting the larger memories and disks to design efficient sparse solvers is a challenge, since memory and disk access times improve at a slower rate than processor clock cycle times. With the goal of designing external memory sparse direct solvers, we formulate two problems: characterizing the minimum core memory size needed in a factorization in which the matrices are read and written once; and characterizing the minimum traffic between memory and disk in a factorization in which the matrices can be read and written multiple times. We compare the left-looking, right-looking, and multifrontal algorithms with respect to their memory and traffic requirements for several classes of model problems. We have extended OBLIO, our sparse direct solver library, with an external memory multifrontal algorithm. We report the performance of OBLIO on large-scale problems with millions of equations, for both in-core and external memory factorization scenarios. OBLIO is designed to be a flexible, extensible algorithmic laboratory for prototyping algorithmic variants on in-core and external memory computational platforms. For in-core factorization, we compare the performance of left-looking, right-looking, and multifrontal algorithms. |
|
|
algweb@cerfacs.fr Last Update: Jun 6, 2003 |