|
|||||
|
|
A cost-optimal parallel tridiagonal system solver |
|
| Authors: | Ferng-Ching Lin and Kuo-Liang Chung |
| Affiliation: | Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan 10764, R.O.C. |
| Abstract: | We first show how to transform the solution of an n × n tridiagonal system into suffix computations of continued fractions. Then a parallel substitution scheme is introduced to compute the suffix values. The derived parallel algorithm allows the tridiagonal system to be solved in O(log n) time on an unshuffle network with Θ(n /log n) processors. It is cost-optimal in the sense that processor number times execution time is minimized. Our solver is conceptually simple and easy for implementation. |
| Keywords: | Continued fraction Suffic values Recurrence equations Substitution scheme Tridiagonal system Unshuffle |
| 本文献已被 ScienceDirect 等数据库收录！ | |