ROUTING MESH

Lenstra, Shamir, Tomlinson and Tromer, 2002

While analyzing Bernstein's proposal, the authors came up with an improved linear algebra algorithm based on mesh routing rather than mesh sorting. The general idea is as follows.

General Matrix by Vector multiplication

In sorting mesh, the elements of the vector were put with the elements of the matrix. In case of sparse matrix, routing mesh does the other way round.

Sparse Matrix by Vector multiplication

 

Routing Mesh Algorithm

Step 1: Build an mesh where is approximately the square root of the size of the matrix. Represent the elements of the matrix and vector in the mesh as follows.

Step 2: Perform the routing in the mesh, by communicating the element to the -th subblock of the mesh, which represents the -th column.

Step 3: Each time a packet arrives at the target cell, the bit vector of the packet is xor-ed with the bit vector at the target cell to perform the GF(2) row addition.

Step 4: Read off these node bit values at the end to obtain the nonzero entries of the product matrix. The matrix is ready for the next multiplication.

 

Complexity: For an mesh, this method takes just steps within a single round routing to multiply the matrix with the vector. [12 times faster than Sorting Mesh]