Parallel complexity for solving tridiagonal linear systems with multiple right-hand sides on 2-D torus interconnection networks

摘要

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.