Among the several methods for solving linear matrix equations, the Hessenberg-Schur method is one of the most efficient sequential algorithms. In a previous work, we developed parallel algorithms, based on this method, for solving the Sylvester matrix equation. In this work we propose a modification of our algorithm which reduces the cost by reordering a special coefficient matrix that has to be triangularized. The defined reordering allows a regular distribution of the data in the parallel algorithm. Both a complexity analysis and an experimental study of the algorithm are also presented.