Ames Laboratory, Department of Energy, ISU, Ames, Iowa
next up previous
Next: Massively parallel compiler Up: Future Applications Previous: Strassen products

Buneman-type methods using extra identities

The conventional method for rotating a 2-vector (x, y) by radians is to multiply it by a matrix of the form

to obtain . This requires four multiplications and two additions. This operation is critical, for example, in the Fast Fourier Transform (FFT) algorithm. If the rotation is to be done for many two-vectors, as it is for the FFT, one regards the and values as constants instead of as input variables. Therefore, it is legitimate to consider precomputing alternative constants based on but not consider the effort to do so in the operation count. Buneman [5] discovered a trigonometric identity that accomplishes a two-vector rotation with three multiplications and three additions, assuming zero cost for computing :


A similar approach exists for reducing the number of multiplications for computing a fourth-degree polynomial [18] from 4 to 3, where precomputation of constants based on the polynomial coefficients can be amortized over many evaluations of the polynomial for various arguments.

The Search program described in this paper does not currently have any way of discovering this type of 'trick'. We do not yet see a 'brute force' approach likely to generate such tricks automatically.