Title :
Parallel complexity for solving tridiagonal linear systems with multiple right-hand sides on 2-D torus interconnection networks
Author :
Santos, Eunice E. ; Santos, Eugene S. ; Santos, Eugene, Jr.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Lehigh Univ., Bethlehem, PA, USA
Abstract :
Precise upper and lower bounds on running time are derived for the problem of solving tridiagonal linear systems with multiple RHS vectors on 2-dimensional torus interconnection networks. We present various important lower bounds on execution time for solving these systems utilizing odd-even cyclic reduction. Furthermore, algorithms are designed in order to achieve running times that are within a small constant factor of the lower bounds provided.
Keywords :
computational complexity; linear algebra; mathematics computing; multiprocessor interconnection networks; parallel algorithms; 2D torus interconnection networks; execution time; linear algebra; lower bounds; multiple right-hand sides; numerical computing; odd-even cyclic reduction; parallel algorithms; parallel complexity; running time; tridiagonal linear systems solving; upper bounds;
Conference_Titel :
High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on
Conference_Location :
Beijing, China
Print_ISBN :
0-7695-0589-2
DOI :
10.1109/HPC.2000.843505
