A Reconfigurable Processing Element Implementation for Matrix Inversion Using Cholesky Decomposition

Authors: Aki Happonen, Adrian Burian, Erwin Hemming

Abstract:

Fixed-point simulation results are used for the performance measure of inverting matrices using a reconfigurable processing element. Matrices are inverted using the Cholesky decomposition algorithm. The reconfigurable processing element is capable of all required mathematical operations. The fixed-point word length analysis is based on simulations of different condition numbers and different matrix sizes.

Keywords: Cholesky Decomposition, Fixed-point, Matrixinversion, Reconfigurable processing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332714

References:

[1] Ki-Il Kum and Wonyong Sung, "Combined word-length optimization and high-level synthesis of digital signal processing systems", IEEE Tran. On Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 8, Aug. 2001, pp. 921-930.
[2] M. J. Juntti, "Performance analysis of linear multisensor multiuser receivers for CDMA in fading channels", IEEE Journal on Selected Areas in Communications, vol. 18 , no. 7 , July 2000, pp. 1221 - 1229.
[3] G. J. Foschini and M. J. Gans, "On limits of wireless communications in a fading environment when using multiple antennas", Wireless Personal Communications, vol. 6, no.3, 1998
[4] R. Baines and D. Pulley, "A Total Cost Approach to Evaluating Different Reconfigurable Architectures for Baseband Processing in Wireless Receivers", IEEE Communication Magazine, January 20003, Page(s): 105-113
[5] R. Hartenstein, "A decade of reconfigurable computing: a visionary retrospective", Design, Automation and Test in Europe, 2001. Conference and Exhibition 2001. Proceedings, 13-16 March 2001, Page(s): 642-649
[6] N.J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996.
[7] P. McCullagh and J.A. Nelder, Generalized Linear Models, Chapmann and Hall, London, 1989.
[8] R. Byers, "Solving the algebraic Riccati equation with matrix sign function", Linear Algebra Applications, vol. 85, 1987, pp. 267-279.
[9] G.W. Stewart, Afternotes on Numerical Analysis, SIAM, Philadelphia, 1996.
[10] M. Cosnard and D. Trystram, Parallel Algorithms and Architectures, Blackwell North America, Inc., 1995.
[11] A. El-Amawy, "A Systolic Architecture for Fast Dense Matrix Inversion", IEEE Trans. Computers, 38, no. 3, pp. 449-455, 1989.
[12] V. Kumar, A. Grama, A. Gupta, and G. Karypis, Introduction to Parallel Computing. Design and Analysis of Algorithms, The Benjamin/Cummings Publishing Company, Inc., 1994.
[13] E. Dekel, D. Nassimi, and S. Sahni, "Parallel Matrix and Graph Algorithms", SIAM J. Computing, vol. 10, pp. 657-673, 1981.
[14] H. Park, H.J. Kim, and V.K. Prasanna, "An O(1) time optimal algorithm for multiplying matrices on reconfigurable mesh", Information Processing Letters, vol. 47, pp. 109-113, 1993.
[15] K. Li and Y. Pan, "Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System", IEEE Trans. Computing, vol. 50, no. 5, pp. 519-525, 2001.
[16] A. Burian, J. Takala, and M. Ylinen, "A fixed-point implementation of matrix inversion using Cholesky decomposition", The 46th International Midwest Symposium On Circuits and Systems, MWSCAS, December 27-30, 2003, Cairo, Egypt.
[17] M. Ylinen, A. Burian, and J. Takala, "Direct versus iterative methods for fixed-point implementation of matrix inversion", Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on , Volume: 3 , 23-26 May 2004, Pages:III - 225-8 Vol.3.
[18] A. Happonen, E. Hemming, and M.J. Juntti, "A novel coarse grain reconfigurable processing element architecture", The 46th International Midwest Symposium On Circuits and Systems, MWSCAS, December 27-30, 2003, Cairo, Egypt.