DocumentCode
2009620
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
Volume
2
fYear
2000
fDate
14-17 May 2000
Firstpage
607
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/HPC.2000.843505
Filename
843505
Link To Document