RISC JKU
  • @thesis{RISC5916,
    author = {Stefan Amberger},
    title = {{A Parallel, In-Place, Rectangular Matrix Transpose Algorithm}},
    language = {english},
    abstract = {This thesis presents a novel algorithm for Transposing Rectangular matrices In-place and in Parallel (TRIP) including a proof of correctness and an analysis of work, span and parallelism. After almost 60 years since its introduction, the problem of in-place rectangular matrix transposition still does not have a satisfying solution. Increased concurrency in today's computers, and the need for low overhead algorithms to solve memory-intense challenges are motivating the development of algorithms like TRIP. The algorithm is based on recursive splitting of the matrix into sub-matrices, independent, parallel transposition of these sub-matrices, and subsequent combining of the results by a parallel, perfect shuffle. We prove correctness of the algorithm for different matrix shapes (ratios of dimensions), and analyze work and span . Compared to out-of-place algorithms, TRIP, implemented in Cilk, trades work-efficiency for parallelism and for being in-place.},
    year = {2019},
    month = {March},
    translation = {0},
    school = {Research Institute for Symbolic Computatation (RISC), Johannes Kepler University, Linz, Austria},
    keywords = {linear algebra, parallel computation},
    length = {67},
    type = {mathesis}
    }