𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Divide and conquer: a parallel algorithm for the solution of a tridiagonal linear system of equations

✍ Scribed by Stefan Bondeli

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
655 KB
Volume
17
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

Bondeli, S_, Divide and conquer: a parallel algorithm for the solution of a tridiagonal linear system of equations, Parallel Computing 17 (1991) 419-434_

We describe a divide and conquer algorithm which solves linear tridiagonal systems with one right-hand side, especially suited for parallel computers. The algorithm is flexible, permits multiprocessing or a combination of vector and multiprocessor implementations, and is adaptable to a wide range of parallelism granularities. This algorithm can also be combined with recursive doubling, cyclic reduction or Wang's partition method, in order to increase the degree of parallelism and vectorizability.

The divide and conquer method will be explained. Some results of time measurements on a CRAY X-MP/28, on an Alliant FX/8, and on a Sequent Symmetry S81b, as well as comparisons with the cyclic reduction algorithm and Gaussian elimination will be presented. Finally, numerical results are given.

πŸ“œ SIMILAR VOLUMES

A BSP Recursive Divide and Conquer Algor
A BSP Recursive Divide and Conquer Algorithm to Compute the Inverse of a Tridiagonal Matrix
✍ Joan-Josep Climent; Leandro Tortosa; Antonio Zamora πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 253 KB

In this paper we discuss a recursive divide and conquer algorithm to compute the inverse of an unreduced tridiagonal matrix. It is based on the recursive application of the Sherman Morrison formula to a diagonally dominant tridiagonal matrix to avoid numerical stability problems. A theoretical study

Parallel Dichotomy Algorithm for solving
Parallel Dichotomy Algorithm for solving tridiagonal system of linear equations with multiple right-hand sides
✍ Andrew V. Terekhov πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 594 KB

A parallel algorithm for solving a series of matrix equations with a constant tridiagonal matrix and different right-hand sides is proposed and studied. The process of solving the problem is represented in two steps. The first preliminary step is calculating some rows of the inverse matrix of system