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