Optimal and efficient parallel tridiagonal solvers using direct methods (Q2386702)

The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered. The derivation of lower bounds on running time, and the design and analysis of algorithms is discussed for a wide-range of machines, networks, and clusters. The primary focus is on two direct methods: odd-even cyclic reduction, and prefix summing. The author determines the types of layouts and communication patterns that are needed to achieve efficient and/or optimal running times for a particular direct method. He presents a variety of lower bounds based on assumptions on data layouts. He presents algorithms that are asymptotically optimal to the lower bounds, and gives comparative results for two chosen direct methods.