Studies on sorting networks and expanders

by Xie, Hang

Abstract (Summary)
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.
Bibliographical Information:


School:Ohio University

School Location:USA - Ohio

Source Type:Master's Thesis

Keywords:paterson s algorithm error recovery structure epsilon halver


Date of Publication:01/01/1998

© 2009 All Rights Reserved.