algorithm tips: Sparse Matrix Multiplication Package (SMMP)

UNDERWRITING... Matrix operation is very useful for improving computing speed of our codes. For this operation, python has very popular packages such as numpy and scipy. In this article, I show sample code to calculate dot product using sparse matrix and vector with numpy and scipy.

import scipy
import numpy
from scipy.sparse import *
from numpy.random import *

vec = create_vec(N)
mat = create_mat(N,M)
ans = mat.dot(vec)

In above code, mat.dot(vec) calculates dot product. This method implements sparse matrix multiplication pacakage called SMMP which computational complexity is : O(n_row*K^2 + max(n_row,n_col))  where n_row is # of matrix rows, n_col is # of matrix columns, K is the maximum index for nonzero value in a row of A and column of B.