Computational issues on ranking large heterogeneous data via paired comparisons

The paper describes computational aspects of a model for ranking elements of a given set based on pairwise comparisons of the elements when the set is large and the comparisons are unstructured. The model involves a large sparse overdetermined linear system Cx=d, where C is the mxn incidence matrix of a graph with n nodes (elements of the set) and m arcs (paired comparisons) and where d is the vector of observed differences in worth. Under the assumption that the graph has q connected components, simple algorithms are given for computing efficiently the corresponding least squares estimation in terms of a maximum of q nonsingular dense systems the sum of whose dimensions is bounded by n.