Sparse matrix vector multiplication

A system having a single instruction multiple data (SIMD) architecture, the system comprising:

• a plurality of computational units;
• a processor executing instructions for preparing a M×N sparse matrix;
• and
• memory storing processor-executable instructions and elements of the M×N sparse matrix represented by groups of single dimensional sub-arrays,
• the single dimensional sub-arrays including all non-zero elements in a first common dimension of the M×N sparse matrix, each group being sorted with respect to the other groups based on a number of non-zero value elements in the single dimensional sub-arrays in the each group, a number of single dimensional sub-arrays in each group is not more than a number (R) of single dimensional sub-arrays processed in parallel by the plurality of computational units,
• the single dimensional sub-arrays in each group having a common number of matrix elements, at least one group having single dimensional sub-arrays that have been packed to remove zero-value elements so as to arrive at the common number,
• wherein upon execution of the processor-executable instructions, a number (C) of the computational units are configured to multiply, in parallel, C elements of the single dimensional sub-arrays in each group with one or more elements of a vector.

A method in a processor having a single instruction multiple data architecture including a plurality of computational units and memory, the method comprising:

• providing a number (C) of elements of single dimensional sub-arrays of a group to C computational units of the processor, the C elements of the single dimensional sub-arrays stored in the memory,
• the single dimensional sub-arrays including all non-zero value elements in a first common dimension of an M×N sparse matrix, each group being sorted with respect to the other groups based on a number of non-zero value elements in the single dimensional sub-arrays in the each group, a number of single dimensional sub-arrays in each group not more than a number (R) of single dimensional sub-arrays processed in parallel by the plurality of computational units,
• the single dimensional sub-arrays in each group having a common number of matrix elements, at least one group having single dimensional sub-arrays that have been packed to remove zero-value elements so as to arrive at the common number;
• and
• multiplying, in parallel, the C elements of the single dimensional sub-arrays and one or more elements of a vector using the C computational units.