Parallel inverse QR decomposition

ABSTRACT

This paper describes an algorithm and an associated architecture for the parallel implementation of the least squares problem using the inverse QR decomposition. We developed the architecture as a part of our research on the parallel implementation of multidimensional signal processing algorithms. In this paper, we show that this architecture can also be used to provide a high performance implementation of the least squares problem.

REFERENCES

• 1: A. Bjorck, Least Square Methods, pp. 465-653. North-Holland, Amsterdam, 1989.
• 2: G. J. Bierman, Factorization Methods for Discrete Sequential Estimation. New York: Academic Press, 1977.
• 3: S Haykin, Adaptive filter theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 4: J. Spelser and C. V. Loan, "Besmforming Algorithms using the generalized SVD," in Real- Time Signal proceHing VII, SPIE Peso., 1984.
• 5: J. M. Cioffi and T. Kallath, "Fast RLS transversal filters for adaptive filtering," IEEE 2Vans. on Acoua., Speech, and signal Proc.,, voL ASSP-32, pp. 304-337, 1984.
• 6: S T Alexander, Adaptive signal processing: theory and applications, Springer-Verlag New York, Inc., New York, NY, 1986
• 7: G. Golub and C. V. Loan, Matriz Computations. New York: Johns Hopkins Press, 1983.
• 8: G. H. Golub, Matris Computations and Statistical Calculations, pp. 365-395. Academic Press, New York, 1967.
• 9: Michael Alan Saunders, Large-scale linear programming using the cholesky factorization, 1972
• 10: Charles M. Rader , Allan O. Steinhard, Hyperbolic householder transforms, SIAM Journal on Matrix Analysis and Applications, v.9 n.2, p.269-290, April 1988 [doi>10.1137/0609022]
• 11: A. W. Bojanczyk , R. P. Brent , P. van Dooren , F. R. de Hoog, A note on downdating the Cholesky factorization, SIAM Journal on Scientific and Statistical Computing, v.8 n.3, p.210-221, May 1, 1987 [doi>10.1137/0908031]
• 12: S. Kim , D. P. Agrawal , R. J. Plemmons, Least-squares multiple updating algorithms on a hypercube, Journal of Parallel and Distributed Computing, v.8 n.1, p.80-88, Jan. 1990 [doi>10.1016/0743-7315(90)90072-W]
• 13: C. T. Pan and R. J. Plemmons, "Least squares modifications with inverse factorisations: Parallel implications, m 3. Comp. and Appi. Math., vol. 27, pp. 109-127, 1989.
• 14: Hongyu Xu, BDFA-A Block Data Flow Architecture for Real- Time Signal Proceuing and Matriz Operatiom, PhD thesis, North Carolina State University, 1991.
• 15: Jae Gil Jeong, High Performance Multiprocessot Architecture for Digital Signal Processing, PhD thesis, North Carolina State University, 1991.
• 16: H. Xu and W. E. Alexander, UA high performance architecture for N-D digtial signal processing and matrix operstins", Proceeding of the International Symposium on Circuits and Systems, 1992.

INDEX TERMS

Keywords:
Architecture, QR factorization, block data flow, least square, processor array, system efficiency, system throughput