A method for computing large-scale two-dimensional transform without transposing data matrix

A fast algorithm is presented for a two-dimensional transform of a data matrix such as Fourier or Hadamard transforms. It can be applied to a matrix, which is too large for the main storage and is stored sequentially rowwise in an auxiliary storage. The size of the matrix may be of R^mrows and of arbitrary number of columns. Whenever R rows of working area are available in the main storage, the matrix is read out, processed, and stored back m times. This new algorithm does not require the presently used method of transposing the data matrix.