Efficient transposition algorithms for large matrices
S. D. Kaushik, Chien‐Hung Huang, R. W. Johnson, Ponnuswamy Sadayappan, Jeremy Russell Johnson · 1993
We p~esent transposition a~gorithms fo?' matrices that do not fit in main memory.Transposition is interpreted m a permutation of the vector obtained by mapping a matriz to linear memoTy.A lgopithms am derived j%om factorization of this perm~tation, using a class of permutations related to the tensor prodwt.Using this formulation of transposition, we jirst obtain seveTal known aigo?'ithms and then we derive a new algorithm which Teduces the number of dish accesses TequiTed.The new algoTithm was compaTed to ezisting algorithms wing an implementation on the Intel iPSC/860.Thti comparison shows the benefits of the new aigoTithm.