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

Adriano Scutellà (18/8/99)

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 to titles of seminars.

---

Steve Lack

Last modified: Wed Aug 18 10:23:20 EST 1999