Proc. 10-th Int. Conf. on Parallel and Distributed Computing
and Systems (PDCS'98), October 1998, Las Vegas, NV, pp. 186-189.
Ömer Egecioglu
LU Factorization and Parallel Evaluation of Continued Fractions
Abstract.
We consider the parallelization of the LU decomposition part
of the LU Algorithm for an nxn tridiagonal linear system, and the
related problem of evaluation of continued fractions.
Direct application of the parallel prefix algorithm for
parallel evaluation of continued fractions results in a parallel algorithm that
requires O(n^2/log n) processors and takes
O(log^2 n) parallel time.
We show that a suffix product formulation for continued fractions
together with a parallel prefix algorithm
can be used for parallel tridiagonal LU decomposition optimally
in O(log n) time using O(n/log n) processors.
omer@cs.ucsb.edu