This work presents a novel strategy for the parallelization of applications containing sparse matrix references using the data-parallel paradigm. Our approach is a first step to converge to the automatic parallelization by reducing the number of directives on code. We have used the semantical relationship of vectors composing a high-level data structure to enhance the performance of the parallel code, applying a sparse privatization and a multi-loop analysis. We also study the building/updating of a sparse matrix at run-time, solving the problem of using pointers and some levels of indirections on the left hand side. A detailed analysis about several temporary buffers useful for sparse communications is described in this paper. The evaluation of our strategy has been performed on a Cray T3E with sparse matrix transposition algorithm as a case of study.