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

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.

Name thesis:degree_name

Master of Science - MSc

Level thesis:degree_level

master's

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of British Columbia

Year dc:date

1993

Author dc:creator

• Song, Yan

Statement dc:rights

• 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.

Language dc:language

eng

Handle dc:identifier

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

OAI identifier oai:identifier

oai:circle.library.ubc.ca:2429/2584