Browse Prior Art Database

Transposition Algorithm

IP.com Disclosure Number: IPCOM000042606D
Original Publication Date: 1984-Jun-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Related People

Wagner, EG: AUTHOR

Abstract

Given an nxm matrix A, it is common practice to store it in nm consecutive memory locations, A[i,j] being stored in the ((i-1)*m)+j location. In effect, this is storing the matrix as a vector VA, where VA[((i-1)* m+j] = A[i,j]. Using the same vector representation, we can represent the matrix T (the transpose of A) by a vector VT where VT[((i-1)*n)+j] = T(i,j) = A(j,i). Using this vector notation, we can describe our purpose here as that of transforming VA, step-by-step, into VT. Some Notation: Given integers p and q, let div(p,q) denote the integer part of p/q and rem(p,q) denote the remainder of p/q (i.e., rem(p,q) = p-q*div(p,q) ). It is easily seen that, for any k, i

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

Transposition Algorithm

Given an nxm matrix A, it is common practice to store it in nm consecutive memory locations, A[i,j] being stored in the ((i-1)*m)+j location. In effect, this is storing the matrix as a vector VA, where VA[((i-1)* m+j] = A[i,j]. Using the same vector representation, we can represent the matrix T (the transpose of A) by a vector VT where VT[((i-1)*n)+j] = T(i,j) = A(j,i). Using this vector notation, we can describe our purpose here as that of transforming VA, step-by-step, into VT. Some Notation: Given integers p and q, let div(p,q) denote the integer part of p/q and rem(p,q) denote the remainder of p/q (i.e., rem(p,q) = p-q*div(p,q) ). It is easily seen that, for any k, i<k< VT[k] = VA[1+(rem(k-1,n)*m)+div(k-1,n)] and VA^k^ = VT^1+(rem(k-1,m)*n)+div(k-1,m)^. Let up,down:{1,...,nm}T{1,...,nm} be the functions such that up(k) = 1+(rem(k-1,m)*n)+div(k-1,m) and down(k) = 1+(rem(k-1,n)*m)+div(k-1,n) so that VA[k] = VT[up(k)] and VT[k] = VA[down(k)]. The algorithm is given by the flowchart on the following page.

(Image Omitted)

1

Page 2 of 2

2

[This page contains 4 pictures or other non-text objects]