Skoči na glavni sadržaj

Izvorni znanstveni članak

A Completely Parallelizable Algorithm for the Determinant of a Tridiagonal Matrix

A. Mahmood ; School of Electrical Engineering and Computer Science, Washington State University at Tri-Cities, Richland, U.S.A.
D. J. Lynch ; School of Electrical Engineering and Computer Science, Washington State University at Tri-Cities, Richland, U.S.A.
L. D. Philipp ; School of Electrical Engineering and Computer Science, Washington State University at Tri-Cities, Richland, U.S.A.


Puni tekst: engleski pdf 3.627 Kb

str. 15-24

preuzimanja: 374

citiraj


Sažetak

A new parallel algorithm (MIMD-PRAM class) having parallel time complexity of log2 n for computing the determinant of a tridiagonal matrix is developed. The algorithm is based on coupling the determinants of two neighboring submatrix blocks. With each coupling, the block size is increased by a factor of two until the entire determinant of an n x n matrix is found by the final coupling of two n/2 sized blocks. It is shown that the determinant of an n x n tridiagonal matrix can be computed in (3 log2 n - 2) parallel steps with a maximum parallel requirement of 7 ( n/4) + 3 processors. The algorithm achieves linear speedup as the number of processors is increased.

Ključne riječi

Determinant, Tridiagonal Matrix, Parallel Algorithm, MIMD, PRAM

Hrčak ID:

150477

URI

https://hrcak.srce.hr/150477

Posjeta: 492 *