Studies on sorting networks and expanders
This thesis examines the explicit construction of Paterson's algorithm. In an attempt to make the algorithm more easily understood, we give the precise definitions for ?-halvers and separators, detailed explanations about some conclusions in Paterson's paper, and the pseudocode for Paterson's algorithm. The idea in Paterson's algorithm is to take an approximate partition of elements, which can be achieved in only a constant number of comparator levels, and then introduce some error-recovery structure into the sorting scheme. In Paterson's algorithm, the approximate partition is implemented with separators. The depth of the Paterson's algorithm is dependent on the depth and parameters of the separator, which is determined by the algorithm that implements it and the depth of an ?-halver. An ?-halver can be constructed through expanders using constant depth. We introduces expanders and the major research results in the area. Ramanujan graphs, which are asymptotically optimal in making the second- eigen-value as small as possible, are used to construct ?-halves. We analyze the construction of ?-halvers through matching in regular graphs. We give a very simple method to construct a balanced regular expander. The second largest eigenvalue of a graph is then used to analyze the expansion of a graph. We analyze the performances of Kahale's result and Tanner's result and point out that the Kahale's result is only effective for very small subsets of the vertices. We adopt the Tanner's result and calculate the depth of the associated ?-halver. We analyze a new kind of separator and give its depth. This separator can achieve fbetter separation without increasing its depth. Finally, we use all our results to analyze the depth of Paterson's algorithm. Through our construction, we achieve sorting networks in less than depth of 947512 log nwith the original separator and depth less than 765544 log nwith the new kind of separator.
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:paterson s algorithm error recovery structure epsilon halver
Date of Publication:01/01/1998