Two-dimensional fast transforms applied to memory limited disk operating computers.

Abstract

Two-dimensional transform algorithms are usually impractical to small machines which cannot handle N2 real (or complex) data points in core when N is large. Storing the input data in N disk records and computing two sequential one-dimensional transforms requires N(N + 3) disk access and 2 N applications of the one-dimensional procedure. Expanding the fast one-dimensional algorithm it is suggested that only 2 N log2N disk accesses are needed whereas the one-dimensional procedure is activated only N times.