Sparsity-driven matrix representation to optimize operational and storage efficiency

1. A method of sparsity-driven matrix representation, the method comprising configuring a processor to perform operations including:

determining a sparsity of a result matrix from a planned operation on at least one input matrix, the determining including estimating the sparsity of the result matrix based on an estimated sparsity of the at least one input matrix and a type of the planned operation;

comparing the sparsity to a threshold;

based on the sparsity being greater than the threshold;

selecting a first data structure format; and

allocating a first memory space in a computer memory to store the result matrix in the first data structure format; and

based on the sparsity not being greater than the threshold;

selecting a second data structure format; and

allocating a second memory space in the computer memory to store the result matrix in the second data structure format,

wherein the first memory space is larger than the second memory space.

2. The method of claim 1 , further comprising:

storing the result matrix in the memory in the first data structure format based on the sparsity being greater than the threshold; and

storing the result matrix in the second data structure format based on the sparsity not being greater than the threshold.

3. The method of claim 1 , wherein the first data structure is one of a row-wise order dense one-dimensional (1D) array, a column-wise order 1D array, and a two-dimensional (2D) array.

4. The method of claim 1 , wherein the second data structure is an array that includes fewer columns than rows.

5. The method of claim 4 , further comprising:

determining that an actual number of non-zero values in a column in the result matrix is larger than a capacity of the column as defined in the second data structure;

determining whether an estimated number of non-zero values in the column in the result matrix is larger than the capacity;

increasing the capacity by a first multiplier based on the estimated number of non-zero values in the column being larger than the capacity; and

increasing the capacity by a second multiplier based on the estimated number of non-zero values in the column not being larger than the capacity, wherein the second multiplier is smaller than the first multiplier.

6. The method of claim 1 , wherein the second data structure is an array that includes equal or fewer rows than columns.

7. The method of claim 6 , further comprising:

determining that an actual number of non-zero values in a row in the result matrix is larger than a capacity of the row as defined in the second data structure;

determining whether an estimated number of non-zero values in the row in the result matrix is larger than the capacity;

increasing the capacity by a first multiplier based on the estimated number of non-zero values in the row being larger than the capacity; and

increasing the capacity by a second multiplier based on the estimated number of non-zero values in the row not being larger than the capacity, wherein the second multiplier is smaller than the first multiplier.

8. A computer system for sparsity-driven matrix representation, the computer system comprising:

a memory device, the memory device having computer readable computer instructions; and

a processor for executing the computer readable instructions, the instructions including:

determining a sparsity of a result matrix from a planned operation on at least one input matrix, the determining including estimating the sparsity of the result matrix based on an estimated sparsity of the at least one input matrix and a type of the planned operation;

comparing the sparsity to a threshold;

based on the sparsity being greater than the threshold:

selecting a first data structure format; and

allocating a first memory space in a computer memory to store the result matrix in the first data structure format; and

based on the sparsity not being greater than the threshold:

selecting a second data structure format; and

allocating a second memory space in the computer memory to store the result matrix in the second data structure format,

wherein the first memory space is larger than the second memory space.

9. The computer system of claim 8 , wherein the instructions further include:

storing the result matrix in the memory in the first data structure format based on the sparsity being greater than the threshold; and

storing the result matrix in the second data structure format based on the sparsity not being greater than the threshold.

10. The computer system of claim 8 , wherein the first data structure is a row-wise order dense 1D array.

11. The computer system of claim 8 , wherein the second data structure is an array that includes fewer columns than rows.

12. A computer program product for sparsity-driven matrix representation, the computer program product comprising:

a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

determine a sparsity of a result matrix from a planned operation on at least one input matrix, the determining including estimating the sparsity of the result matrix based on an estimated sparsity of the at least one input matrix and a type of the planned operation;

compare the sparsity to a threshold;

based on the sparsity being greater than the threshold:

select a first data structure format; and

allocate a first memory space in a computer memory to store the result matrix in the first data structure format; and

based on the sparsity not being greater than the threshold:

select a second data structure format; and

allocate a second memory space in the computer memory to store the result matrix in the second data structure format,

wherein the first memory space is larger than the second memory space.

13. The computer program product of claim 12 , wherein the program code is further executable by the processor to:

store the result matrix in the memory in the first data structure format based on the sparsity being greater than the threshold; and

store the result matrix in the second data structure format based on the sparsity not being greater than the threshold.

14. The computer program product of claim 12 , wherein the first data structure is one of a row-wise order dense 1D array, a column-wise order 1D array, and a 2D array.

15. The computer program product of claim 12 , wherein the second data structure is an array that includes fewer columns than rows.

16. The computer program product of claim 15 , wherein the program code is further executable by the processor to:

determine that an actual number of non-zero values in a column in the result matrix is larger than a capacity of the column as defined in the second data structure;

determine whether an estimated number of non-zero values in the column in the result matrix is larger than the capacity;

increase the capacity by a first multiplier based on the estimated number of non-zero values in the column being larger than the capacity; and

increase the capacity by a second multiplier based on the estimated number of non-zero values in the column not being larger than the capacity, wherein the second multiplier is smaller than the first multiplier.

17. The computer program product of claim 12 , wherein the second data structure is an array that includes equal or fewer rows than columns.

18. The computer program product of claim 17 , wherein the program code is further executable by the processor to:

determining that an actual number of non-zero values in a row in the result matrix is larger than a capacity of the row as defined in the second data structure;

determining whether an estimated number of non-zero values in the row in the result matrix is larger than the capacity;

increase the capacity by a first multiplier based on the estimated number of non-zero values in the row being larger than the capacity; and

increase the capacity by a second multiplier based on the estimated number of non-zero values in the row not being larger than the capacity, wherein the second multiplier is smaller than the first multiplier.