Matrix transposition in a computer system

A method for transposing a square matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having M rows and M columns and a size M×M, the method including:

• determining in and p, wherein M=M*p, and wherein M×p represents a block size and wherein M is evenly divisible by p;
• setting a partitioning position at the upper-left corner element of the matrix, said partitioning position having a horizontal position and a vertical position;
• for each column of size p:
• sequentially reading elements row-wise from said partitioning position for p rows, without reading any elements to the left of said horizontal position of said partitioning position, and sequentially writing said elements into the cache;
• sequentially reading elements column-wise from said partitioning position for p columns, without reading any elements above said vertical position of said partitioning position, and sequentially writing said elements row-wise from said partitioning position for p rows, without writing any elements to the left of said horizontal position of said partitioning position;
• sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix column-wise for p columns, without writing any elements above said vertical position of said partitioning position;
• and
• moving said partitioning position p elements down and p elements to the right.

A method for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having M rows and k*M columns and a size M×kM, the method including:

• partitioning said matrix into k square matrices of size M×M;
• determining m and p, wherein M=m*p, and wherein M×p represents a block size and wherein M is evenly divisible by p;
• for each of said k square matrices:
• setting a partitioning position at the upper-left corner element of the matrix, said partitioning position having a horizontal position and a vertical position;
• for each column of size m:
• sequentially reading elements row-wise from said partitioning position for p rows, without reading any elements to the left of said horizontal position of said partitioning position, and sequentially writing said elements into the cache;
• sequentially reading elements column-wise from said partitioning position for p columns, without reading any elements above said vertical position of said partitioning position, and sequentially writing said elements row-wise from said partitioning position for p rows, without writing any elements to the left of said horizontal position of said partitioning position;
• sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix column-wise for p columns, without writing any elements above said vertical position of said partitioning position;
• and
• moving said partitioning position p elements down and p elements to the right;
• converting the matrix into an M×k matrix of vectors of length M;
• and
• applying a permutation vector to said converted matrix.

A method for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having k*N rows and N columns and a size kN×N, the method including:

• treating the matrix as a k×n matrix of vectors of length N;
• applying a permutation vector to said k×n matrix of vectors of length N, achieving a result matrix;
• treating said result matrix of said applying as an N×kN matrix;
• partitioning said N×kN matrix into k contiguous square matrices;
• partitioning said matrix into k square matrices of size M×M, wherein M=N;
• determining m and p, wherein M=m*p, and wherein M×p represents a block size and wherein M is evenly divisible by p;
• for each of said k contiguous square matrices:
• setting a partitioning position at the upper-left corner element of the matrix, said partitioning position having a horizontal position and a vertical position;
• for each column of size m:
• sequentially reading elements row-wise from said partitioning position for p rows, without reading any elements to the left of said horizontal position of said partitioning position, and sequentially writing said elements into the cache;
• sequentially reading elements column-wise from said partitioning position for p columns, without reading any elements above said vertical position of said partitioning position, and sequentially writing said elements row-wise from said partitioning position for p rows, without writing any elements to the left of said horizontal position of said partitioning position;
• sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix column-wise for p columns, without writing any elements above said vertical position of said partitioning position;
• and
• moving said partitioning position p elements down and p elements to the right.

A method for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having k*m rows and k*n columns and a size km×kn, the method including:

• partitioning the matrix into a k×k square matrix of blocks of size m×n;
• for each of said k×k blocks:
• sequentially reading elements within said blocks row-wise and sequentially writing said elements into the cache;
• sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix in the memory in a block of size n×m;
• and
• swapping all of said k×k blocks about the main diagonal.

A computer system for transposing a matrix of numbers, the matrix having M rows and N columns and a size M×N, the system including:

• a processor;
• a memory coupled to the processor, the matrix stored in the memory;
• a cache coupled to the processor;
• a block size determiner coupled to the processor, the memory, and the cache;
• a matrix partitioner coupled to the processor and to the memory;
• a sequential reader/writer coupled to the cache and to the processor;
• and
• a permutation vector applier coupled to the processor and to the memory.

A computer system for transposing a matrix of numbers, the matrix having M rows and M columns and a size M×M, the system including:

• a processor;
• a memory coupled to the processor;
• a cache coupled to the processor;
• a block size determiner coupled to the processor, the memory, and the cache;
• a partitioning position setter coupled to the memory;
• a sequential reader/writer coupled to the cache and the processor;
• and
• a partitioning position mover coupled to the sequential reader/writer and to the cache.

A computer system for transposing a matrix of numbers, the matrix having M rows and k*M columns and a size M×kM, the system including:

• a processor;
• a memory coupled to the processor;
• a cache coupled to the processor;
• a matrix partitioner coupled to the processor and to the memory;
• a block size determiner coupled to the processor, the memory, and the cache;
• a partitioning position setter coupled to the memory;
• a sequential reader/writer coupled to the cache and the processor;
• and
• a partitioning position mover coupled to the sequential reader/writer.

A computer system for transposing a matrix of numbers, the matrix having k*N rows and N columns and a size kN×N, the system including:

• a processor;
• a memory coupled to the processor;
• a cache coupled to the processor;
• a matrix treater coupled to the memory;
• a permutation vector applier coupled to the processor;
• a result matrix treater coupled to the memory;
• a matrix partitioner coupled to the memory;
• a block size determiner coupled to the processor, the memory, and the cache;
• a partition position setter coupled to the memory;
• a sequential reader/writer coupled to the cache and to the processor;
• and
• a partition position mover coupled to the sequential reader/writer and to the cache.

A computer system for transposing a matrix of numbers, the matrix having M rows and M columns and a size M×M, the system including:

• a processor;
• a memory coupled to the processor;
• a cache coupled to the processor;
• a matrix partitioner coupled to the processor;
• a sequential reader/writer coupled to the cache and to the processor;
• and
• a block swapper coupled to the memory.

An apparatus for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having M rows and N columns and a size M×N, the apparatus including:

• means for determining n and q, wherein N=n*q, and wherein M×q represents a block size and
• wherein N is evenly divisible by q;
• means for partitioning said matrix into n columns of size M×q;
• for each column n:
• means for sequentially reading elements within said column n row-wise and sequentially writing said elements into the cache;
• and
• means for sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix in the memory in a column of size q×M;
• and
• means for applying a permutation vector to said matrix.

An apparatus for transposing a square matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having M rows and M columns and a size M×M, the apparatus including:

• means for determining m and p, wherein M=m*p, and wherein M×p represents a block size and wherein M is evenly divisible by p;
• means for setting a partitioning position at the upper-left corner element of the matrix, said partitioning position having a horizontal position and a vertical position;
• for each column of size p:
• means for sequentially reading elements row-wise from said partitioning position for p rows, without reading any elements to the left of said horizontal position of said partitioning position, and sequentially writing said elements into the cache;
• means for sequentially reading elements column-wise from said partitioning position for p columns, without reading any elements above said vertical position of said partitioning position, and sequentially writing said elements row-wise from said partitioning position for p rows, without writing any elements to the left of said horizontal position of said partitioning position;
• means for sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix column-wise for p columns, without writing any elements above said vertical position of said partitioning position;
• and
• means for moving said partitioning position p elements down and p elements to the right.

An apparatus for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having M rows and k*M columns and a size M×kM, the apparatus including:

• means for partitioning said matrix into k square matrices of size M×M;
• means for determining m and p, wherein M=m*p, and wherein M×p represents a block size and wherein M is evenly divisible by p;
• for each of said k square matrices:
• means for setting a partitioning position at the upper -left corner element of the matrix, said partitioning position having a horizontal position and a vertical position;
• for each column of size m:
• means for sequentially reading elements row-wise from said partitioning position for p rows, without reading any elements to the left of said horizontal position of said partitioning position, and sequentially writing said elements into the cache;
• means for sequentially reading elements column-wise from said partitioning position for p columns, without reading any elements above said vertical position of said partitioning position, and sequentially writing said elements row-wise from said partitioning position for p rows, without writing any elements to the left of said horizontal position of said partitioning position;
• means for sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix column-wise for p columns, without writing any elements above said vertical position of said partitioning position;
• and means for moving said partitioning position p elements down and p elements to the right;
• means for convening the matrix into an M×k matrix of vectors of length M;
• and
• means for applying a permutation vector to said converted matrix.

An apparatus for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having k*N rows and N columns and a size kN×N, the apparatus including:

• means for treating the matrix as a k×n matrix of vectors of length N;
• means for applying a permutation vector to said k×n matrix of vectors of length N, achieving a result matrix;
• means for treating said result matrix of said applying as an N×kN matrix;
• means for partitioning said N×kN matrix into k contiguous square matrices;
• means for partitioning said matrix into k square matrices of size M×M, wherein M=N;
• means for determining m and p, wherein M=m*p, and wherein M×p represents a block size and wherein M is evenly divisible by p;
• for each of said k contiguous square matrices:
• means for setting a partitioning position at the upper-left corner element of the matrix, said partitioning position having a horizontal position and a vertical position;
• for each column of size m:
• means for sequentially reading elements row-wise from said partitioning position for p rows, without reading any elements to the left of said horizontal position of said partitioning position, and sequentially writing said elements into the cache;
• means for sequentially reading elements column-wise from said partitioning position for p columns, without reading any elements above said vertical position of said partitioning position, and sequentially writing said elements row-wise from said partitioning position for p rows, without writing any elements to the left of said horizontal position of said partitioning position;
• means for sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix column-wise for p columns, without writing any elements above said vertical position of said partitioning position;
• and
• means for moving said partitioning position p elements down and p elements to the right.

A apparatus for transposing a matrix of numbers using a computer system, said computer system having a processor, a memory, and a cache, the matrix stored in the memory and having k*m rows and k*n columns and a size km×kn, the apparatus including:

• means for partitioning the matrix into a k×k square matrix of blocks of size m×n;
• for each of said k×k blocks:
• means for sequentially reading elements within said blocks row-wise and sequentially writing said elements into the cache;
• means for sequentially reading elements from the cache and sequentially writing them row-wise back into the matrix in the memory in a block of size n×m;
• and
• means for swapping all of said k×k blocks about the main diagonal.