A Reconfigurable Processing Element Implementation for Matrix Inversion Using Cholesky Decomposition
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:55925", author = "Aki Happonen and Adrian Burian and Erwin Hemming", title = "A Reconfigurable Processing Element Implementation for Matrix Inversion Using Cholesky Decomposition ", 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.", volume = "1", number = "3", pages = "604-4", }
