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]