We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very com-mon direct methods : odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data lay-outs commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.
展开▼
