ISSN:
1572-9125
Keywords:
E.2
;
F.2.1
;
G.4
;
I.1.2
;
Matrix transposition
;
mixed radix notation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract An algorithm is developed and described for transposing a matrix larger than available working storage. If an (n×m)-matrix is stored in row-major order, and blocks ofn elements may be transferred to and from working storage at a time, the algorithm needsw=(5[m/n]+8)·n elements to be present in working storage at a time and requires [log2(2mn/w)] passages over the matrix. The algorithm is as efficient as earlier methods but needs no extra backing storage space. An algebra for mixed radix notation and a generalization of mixed radix notation is introduced for the description and verification of transposition algorithms, and earlier algorithms are briefly certified or disproved.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01932126
Permalink