Abstract
We propose a parallel algorithm for computing a threshold incomplete LU (ILU) factorization. The main idea is to interleave a parallel fixed-point iteration that approximates an incomplete factorization for a given sparsity pattern with a procedure that adjusts the pattern. We describe and test a strategy for identifying nonzeros to be added and nonzeros to be removed from the sparsity pattern. The resulting pattern may be different and more effective than that of existing threshold ILU algorithms. Also in contrast to other parallel threshold ILU algorithms, much of the new algorithm has fine-grained parallelism.
| Original language | English |
|---|---|
| Pages (from-to) | C503-C519 |
| Journal | SIAM Journal on Scientific Computing |
| Volume | 40 |
| Issue number | 4 |
| DOIs | |
| State | Published - 2018 |
Funding
This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under award DE-SC0016513. The first author has been supported by the “Impuls und Vernetzungsfond” of the Helmholtz Association under grant VH-NG-1241. ∗Submitted to the journal’s Software and High-Performance Computing section June 13, 2016; accepted for publication (in revised form) May 7, 2018; published electronically July 12, 2018. http://www.siam.org/journals/sisc/40-4/M107950.html Funding: This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under award DE-SC0016513. The first author has been supported by the “Impuls und Vernetzungsfond” of the Helmholtz Association under grant VH-NG-1241. †Karlsruhe Institute of Technology, Karlsruhe 76131, Germany, and University of Tennessee, Knoxville, TN 37996 ([email protected]). ‡School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA 30332 ([email protected]). §School of Computer Science, University of Manchester, Manchester M139PL, UK, Oak Ridge National Laboratory, Oak Ridge, TN 37830, and University of Tennessee, Knoxville, TN 37996 ([email protected]).
| Funders | Funder number |
|---|---|
| U.S. Department of Energy Office of Science | |
| Advanced Scientific Computing Research | DE-SC0016513 |
| Helmholtz-Gemeinschaft | |
| Helmholtz Association | VH-NG-1241 |