Optimal in-place transposition of rectangular matrices

DOI10.1016/J.JCO.2009.02.008MaRDI QIDQ2272153zbMATH OpenOpenAlexFDO

Authors A. Tret'yakov, E. E. Tyrtyshnikov

Publication date 6 August 2009

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2009.02.008

zbMATH Keywords

data rearrangementin-place algorithmsrectangular matricestransposition

Mathematics Subject Classification ID

Review text

A method is given for transposing (in place) a rectangular \(m\) by \(n\) matrix stored as a two dimensional array. The focus is on minimizing the number of operations and the number of additional memory cells other than used in storing the given matrix. The proposed method uses \(O(mn)\) writes and \(\min(m,n)\) auxiliary memory cells. The algorithm for square matrices (\(m=n\)) is discussed.

Recommendations

• Transposition of large rectangular matrices
• A general transposition method for a matrix on auxiliary store
• Matrix transpose on meshes with buses
• scientific article; zbMATH DE number 1217600
• Matrix transpose on meshes with wormhole and XY routing

Cites work

• scientific article; zbMATH DE number 4037022 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Tensor properties of multilevel Toeplitz and related matrices
• Transposition of a rectangular matrix

Cited in

(7)

• Transposition of large rectangular matrices
• Transposition of an \(\ell \times \ell\) matrix requires \(\Omega\) (log \(\ell)\) reversals on conservative Turing machines
• Highly efficient GPU eigensolver for three-dimensional photonic crystal band structures with any Bravais lattice
• Matrix transposition in a magnetic bubble memory
• scientific article; zbMATH DE number 1217600 (Why is no real title available?)
• scientific article; zbMATH DE number 1984234 (Why is no real title available?)
• A general transposition method for a matrix on auxiliary store

This page was built for publication: Optimal in-place transposition of rectangular matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272153)