Accession Number : ADA298994

Title :   Operation Complexity for Integer or RNS Gaussian Elimination.

Descriptive Note : Final rept.,

Corporate Author : NAVAL AIR WARFARE CENTER AIRCRAFT DIV WARMINSTER PA

Personal Author(s) : Turner, Peter R. ; Kirsch, Barry J.

PDF Url : ADA298994

Report Date : 01 NOV 1994

Pagination or Media Count : 23

Abstract : This note addresses the question raised by Turner & Kirsch (1994) of the operation counts for the Gauss elimination solution of adaptive beamforming problems using integer arithmetic. Because the covariance matrix is positive definite hermitian, it follows that the multipliers cannot be precomputed and stored for each pair of rows. This has the effect of increasing the number of divisions from 0(N2) to 0(N)3 which for any integer arithmetic (and, especially, RNS arithmetic) may prove to be an unacceptable cost. These results are extended to various degrees of parallelism in the integer or RNS processors and to the use of the L-CRT for scaling in a divisionless algorithm. Scaling using a fractional divider is also considered. The cost of RNS divisions is revisited in the light of newer division algorithms based on the work of Hitz and Kaltofen (1994). The relative cost of the divisions is substantially reduced rendering the RNS approach potentially practical for moderate size problems.

Descriptors :   *BEAM FORMING, *ADAPTIVE SYSTEMS, ALGORITHMS, MATRICES(MATHEMATICS), INTEGER PROGRAMMING, COUNTING METHODS, SOLUTIONS(GENERAL), COVARIANCE, ELIMINATION.

Subject Categories : Theoretical Mathematics
      Radiofrequency Wave Propagation

Distribution Statement : APPROVED FOR PUBLIC RELEASE