Adaptive matrix multiplication for various degree of sparsity using tensorflow

Abstract

Matrix multiplication is a fundamental operation used in many problems, and many matrix multiplication algorithms are proposed for many computing environments. TensorFlow is a machine learning platform with many mathematic library functions including matrix multiplication. TensorFlow provides two methods, tf.matmul and tf.sparse_matmul, for matrix multiplication. It is suggested that tf.matmul should be used for dense matrices, and tf.sparse_matmul should be used for sparse matrices. In this work, an approach is proposed to improve the efficiency of matrix multiplication in TensorFlow. The proposed approach divides each matrix into four submatrices, and chooses either tf.matmul or tf.sparse_matmul for the multiplication of each pair of submatrices, based on the density of the submatrices. We found that it is faster than both tf.matmul and tf.sparse_matmul for input matrices that have uneven distribution of non-zero values. For other inputs, it is almost as fast as the faster one between tf.matmul and tf.sparse_matmul. However, this approach can only be used for CPUs because tf.sparse_matmul is supported only on CPUs but not GPUs.