Matrix transposition in a computer system
US7031994B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 13, 2002 |
| Grant date | Apr 18, 2006 |
| Priority date | — |
| Expiry date | Apr 4, 2024 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/785
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Improved transposition of a matrix in a computer system may be accomplished while utilizing at most a single permutation vector. This greatly improves the speed and parallelability of the transpose operation. For a standard rectangular matrix having M rows and N columns and a size M×N, first n and q are determined, wherein N=n*q, and wherein M×q represents a block size and wherein N is evenly divisible by p. Then, the matrix is partitioned into n columns of size M×q. Then for each column n, elements are sequentially read within the column row-wise and sequentially written into a cache, then sequentially read from the cache and sequentially written row-wise back into the matrix in a memory in a column of size q×M. A permutation vector may then be applied to the matrix to arrive at the transpose. This method may be modified for special cases, such as square matrices, to further improve efficiency.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.