Operation Complexity for Integer or RNS Gaussian Elimination.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1994
- Accession Number
- ADA298994
Entities
People
- Barry J. Kirsch
- Peter R. Turner
Organizations
- Naval Air Warfare Center Aircraft Divison