Selecting without comparing: A small theorem in linear algebra and its abstract implementation using the bicategory Span(RGraph)

Adriano Scutellà – 18 August 1999

This is joint work with Domenico Gallo. We present a theorem that states that is possible to select (the maximum) in a vector of numbers withouth comparing its elements, i.e. it is possible to select by using only algebraic operations (addition, multiplication). The theorem lends itself to be implemented as a (possibly parallel) procedure that selects in constant time. Because of some bottlenecks, a circuit-like abstract implementation is provided using the bicategory of Spans of Reflexive Graphs recently studied by Katis et al. The hardaware implementation can constitute the core of many selection alghoritms: for instance we suggest also how to order a vector using the selection procedure.

Back