Algorithms for Block Bidiagonal Systems on Vector and Parallel Computers

摘要

Parallel algorithms which combine high efficiency with good stability on vector and parallel computers are developed. These algorithms generalise cyclic reduction in several ways: They use Householder-based QR factorisation as basic elimination procedure, they use multiple wrap-around partitioning permutations instead of the odd-even permutations of cyclic reduction and they handle problems of any size. A simple timing model is used to develop optimal permutations. The models (and initial tests) suggest that methods combining tricyclic reduction-like steps with cyclic reduction-like steps lead to good performance. The algorithm is memory efficient.