Research On Transposing Matrices Using In-place Method

Transposition is one of the most basic matrix operations. Especially, as the size of the large-scale matrix over the computer memory, transposition is one of the common operations in scientific computations, such as ADI (Alternating Direction Implicit), FFT(Fast Fourier Transform) and NWP (Numerical Weather Prediction). To improve the efficiency for the transposition of large-scale matrices, it is practical and valuable to solve the problem of large memory and high efficency requirements.Matrix transposing methods can be divided into general transpositon algorithm, In-Place method and Out-of-Core method. General transposition algorithm is usually applicable to matrices of small scale; In-Place method is put forward for the reason that the memory of a single computer is insufficient for special matrix. Out-of-Core method is typically aimed to transpose the large-scale matrices which are stored in the external storage. This paper specifies the fundamental theory and In-Place algorithm for matrix transposition. The key point of this thesis is to explore In-Place matrix transposition algorithm and to introduce some innovations to improve the efficiency of matrix transposition.In this thesis, we will examine the existent In-Place matrix transposition algorithms and deduce the fundamental theory which had been advanced on some open literatures. A shortcoming is found in existent algorithms, that is, the efficiency will drop through the additional memory requirement will decrease. So, we provide an improved In-Place matix transposition to reduce the memory R/W operations. The experiments show that the efficiency can be improved obviously when using the improved algorithm for matrix of size2~m×2~n.After that, the improved 2-D In-Place algorithm is extended to three dimentional arrays, and some theoretic and numerical results are also provided. Furthermore, we develop a new in-place 3-D arrays transposition algorithm. Experimental results show that our algorithm can improve efficiency significantly, compared to some other 3-D array transposition schemes. Furthermore, the parallel implementation technique is introduced for 3-D array transposition.Next, two kinds of applications are addressed based on the matrix transposition algorithm.Finally, we draw the prospection for the research on matrix transposition at the end of this thesis.