We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Parallel algorithms for solving linear systems with sparse triangular matrices.
- Authors
Mayer, Jan
- Abstract
In this article, we present two new algorithms for solving given triangular systems in parallel on a shared memory architecture. Multilevel incomplete LU factorization based preconditioners, which have been very successful for solving linear systems iteratively, require these triangular solves. Hence, the algorithms presented here can be seen as parallelizing the application of these preconditioners. The first algorithm solves the triangular matrix by block anti-diagonals. The drawback of this approach is that it can be difficult to choose an appropriate block structure. On the other hand, if a good block partition can be found, this algorithm can be quite effective. The second algorithm takes a hybrid approach by solving the triangular system by block columns and anti-diagonals. It is usually as effective as the first algorithm, but the block structure can be chosen in a nearly optimal manner. Although numerical results indicate that the speed-up can be fairly good, systems with matrices having a strong diagonal structure or narrow bandwidth cannot be solved effectively in parallel. Hence, for these matrices, the results are disappointing. On the other hand, the results are better for matrices having a more uniform distribution of non-zero elements. Although not discussed in this article, these algorithms can possibly be adapted for distributed memory architectures.
- Subjects
ALGORITHMS; FACTORIZATION; LINEAR systems; BANDWIDTHS; MATRICES (Mathematics)
- Publication
Computing, 2009, Vol 86, Issue 4, p291
- ISSN
0010-485X
- Publication type
Article
- DOI
10.1007/s00607-009-0066-3