A Reconfigurable Processing Element for Cholesky Decomposition and Matrix Inversion

Authors: Aki Happonen, Adrian Burian, Erwin Hemming

Abstract:

Fixed-point simulation results are used for the performance measure of inverting matrices by Cholesky decomposition. The fixed-point Cholesky decomposition algorithm is implemented using a fixed-point reconfigurable processing element. The reconfigurable processing element provides all mathematical operations required by Cholesky decomposition. The fixed-point word length analysis is based on simulations using different condition numbers and different matrix sizes. Simulation results show that 16 bits word length gives sufficient performance for small matrices with low condition number. Larger matrices and higher condition numbers require more dynamic range for a fixedpoint implementation.

Keywords: Cholesky Decomposition, Fixed-point, Matrix inversion, Reconfigurable processing.

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

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 2003, 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 Circuits and Systems, Volume: 3 , 23-26 May 2004, pp. 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.
[19] W. Benzing, T. Scherer, W. Jutzi, "Inversion calculation of two dimensional current distributions from their magnetic field",IEEE Transactions on Applied Superconductivity, vol. 3, issue 1, March 1993, pp. 1902-1905.