An efficient method for transposing large matrices and itsapplication to separable processing of two-dimensional signals

An attempt is made to transpose an arbitrary matrix when the total number of matrix elements is too large to store them all in random-access memory. This problem is often a computational bottleneck in large computed-imaging problems. A simple algorithm for obtaining the transposed matrix using only two read/write passes over the data is derived. This algorithm is efficient for a wide range of practical problems. The first step of the algorithm reorders the data in a form that permits efficient access to the data either by row or by column. Thus, if the only reason for constructing the transpose is to provide efficient access to the data for processing along the slow dimension of a two-dimensional data set, the matrix transpose can be eliminated simply by storing the data in this intermediate form. Furthermore, this reordering can be performed in place with a single read/write pass over the data     

Detecting High-Contrast Seismic Anomalies Using Cross-Borehole Probing

Seismic probing between boreholes is useful for locating high-contrast geophysical anomalies such as an abandoned tunnel. Theoretical studies of continuous wave (CW) seismic wave interaction with a tunnel show that both the signal minima and the phase structure of the received signal can be used for locating the anomaly. The theoretical studies show that as the source and receiver are lowered in separate boreholes straddling the anomaly, the signal minima and the phase structure can be interpreted to yield both the lateral and vertical positions of the anomaly. Plane waves of compressional, horizontally polarized shear, and vertically polarized shear wave types incident on a cylindrical horizontal anomaly have been considered. The total seismic field has been calculated using an exact formulation. The variation of the response is studied as a function of the ratio of anomaly diameter to wavelength. The resulting fields in the receiver borehole are an effective diagnostic when a wavelength in the surrounding medium is less than or equal to the diameter of the anomaly. These results are analogous to the corresponding electromagnetic case which has been studied previously.     

An efficient parallel-processing method for transposing largematrices in place

We have developed an efficient algorithm for transposing large matrices in place. The algorithm is efficient because data are accessed either sequentially in blocks or randomly within blocks small enough to fit in cache, and because the same indexing calculations are shared among identical procedures operating on independent subsets of the data. This inherent parallelism makes the method well suited for a multiprocessor computing environment. The algorithm is easy to implement because the same two procedures are applied to the data in various groupings to carry out the complete transpose operation. Using only a single processor, we have demonstrated nearly an order of magnitude increase in speed over the previously published algorithm by Gate and Twigg (1977) for transposing a large rectangular matrix in place. With multiple processors operating in parallel, the processing speed increases almost linearly with the number of processors. A simplified version of the algorithm for square matrices is presented as well as an extension for matrices large enough to require virtual memory.