A Reconfigurable Processing Element for Cholesky Decomposition and Matrix Inversion
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:52725", author = "Aki Happonen and Adrian Burian and Erwin Hemming", title = "A Reconfigurable Processing Element for Cholesky Decomposition and Matrix Inversion", 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.", volume = "1", number = "11", pages = "521-6", }
