Expectation Maximization Algorithm is an iterative method frequently mentioned in solving the incomplete data problems since its birth in 1970's. Despite of its capability in data approximation, the method has not been widely used in practice due to the huge amount of data size involved in the intensive matrix-vector multiplication. In this paper we propose a novel technique in speeding up the computation time by better manipulation of the probability matrix. The key idea is to pre-process the input matrix by extracting the non-zero elements along with their index information. The proposed sparse matrix method is made more efficient by both taking advantage of geometrical information of the machine gantry and removing of indirect addressing overheads that is associated with most of the compressed sparse matrix method. Load balancing is also achieved by better distribution scheme implemented in the pre-processing phase of the algorithm.We have tested the algorithm on IBM SP2 machine for its performance. Significant amounts of computation time reductions are found in our study on various density information of the matrix. The new algorithm has the advantage of having minimum overhead and no new constraint on the matrix structure. By using the proposed sparse matrix parallel method, our study demonstrates the promising result for future use of the algorithm.