We propose a novel approach for efficient matrix-matrix-transpose-vector computation. This approach is based on clustering the columns of a rectangular or square unsymmetrical sparse matrix and then permuting its rows and columns into block angular form on which a new computation method is applied. Common approach for this computation is based on two successive sparse matrix-vector product. First y=A^Tx and then z=Ay is computed. An alternative scheme is computing B=AA^T first, which is followed by y=Bx matrix-vector computation. There are very few matrix instances that contain less number of multiplication-addition operations when the latter computation scheme is applied. However, the new hybrid method consists of both computation schemes. Then it exploits the computational reductions in the blocks where the alternative scheme is used.

The problem is modeled using bipartite graph and hypergraph representations of sparse matrices interchangeably. We devise algorithms for preprocessing using data structures built upon compressed storage formats for sparse matrices. The clustering decisions are taken based on the metrics which compute the extra nonzero operations induced and aspect ratios which encourage formation of blocks where proposed multiplication order could be performed. The implementations and results on sparse matrices from various collections are provided. Very promising improvements are obtained where up to 17 percent reductions in the number of multiplication-addition operations are observable.

Keywords: Matrix-matrix-transpose-vector Computation, Matrix Clustering Algorithms, Matrix Preprocessing, Sparse Matrix Data Structures.