UBC Theses and Dissertations
The implementation of sequential and parallel algorithms for solving almost block bidiagonal systems Song, Yan
In this thesis, we mainly concentrate on the implementation of sequential and parallel algorithms for solving block bidiagonal linear system arising from the discretization of boundary value problems for linear ordinary differential equations. It consists of two parts. In Part I, several sequential algorithms, the Alternate Row and Column Pivoting Algorithm, the Structured QR Algorithm, the Structured LU Algorithm and the Least Square Algorithm, are implemented and some stability issues of these algorithms are considered. Numerical results are presented. In Part II, the corresponding parallel algorithms, except the Parallel Alternate Row and Column Pivoting Algorithm, are implemented on INMOS T800 Transputers, a microcomputer with multi processors.To abstract the application from the system function calls, we use a template based on a simple software system with master-slave technique as the interface with the application. The description of those parallel algorithms and numerical results are presented. Only the case with separate boundary conditions is considered here. Among all the sequential algorithms, we can say that the Alternate Row and Column Pivoting Algorithm is the most efficient algorithm with no fill-ins, while the Structured QR Algorithm is the most stable algorithm. Though the Structured LU Algorithm is much faster than Structured QR Algorithm in the sequential case if the block size is greater than 3, the absolute run times of both parallel algorithms are almost the same because the Parallel Structured QR Algorithm obtains better speedup.
Item Citations and Data