Open Collections

The implementation of sequential and parallel algorithms for solving almost block bidiagonal systems

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2008-10-11

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/2584

Computer Science

University of British Columbia

UBCV

DSpace