Fast Implementation for the Singular Value and Eigenvalue Decomposition Based on FPGA

ZHANG Shuiping; TIAN Xin; XIONG Chengyi; TIAN Jinwen; MING Delie

doi:10.1049/cje.2016.06.033

Volume 26 Issue 1

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2017 > 26(1): 132-136

ZHANG Shuiping, TIAN Xin, XIONG Chengyi, et al., “Fast Implementation for the Singular Value and Eigenvalue Decomposition Based on FPGA,” Chinese Journal of Electronics, vol. 26, no. 1, pp. 132-136, 2017, doi: 10.1049/cje.2016.06.033

Citation:

ZHANG Shuiping, TIAN Xin, XIONG Chengyi, et al., “Fast Implementation for the Singular Value and Eigenvalue Decomposition Based on FPGA,” Chinese Journal of Electronics, vol. 26, no. 1, pp. 132-136, 2017, doi: 10.1049/cje.2016.06.033

Citation:

PDF( 436 KB)

Fast Implementation for the Singular Value and Eigenvalue Decomposition Based on FPGA

doi: 10.1049/cje.2016.06.033

1.
School of Computer Science and Engineering, Wuhan Institute of Technology, Wuhan 430073, China;
2.
School of Electronic Information, Wuhan University, Wuhan 430072, China;
3.
School of Electronic and Information Engineering, South-central University for Nationalities, Wuhan 430074, China;
4.
School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61273279, No.61471400, No.61102064, No.61273241).

More Information

Corresponding author: MING Delie (corresponding author) was born in Hubei Province, China, in 1974. He received the Ph.D. degree in School of Automation, Huazhong University of Science and Technology. His research interests include image analysis and computer vision. (Email:mingdelie@hust.edu.cn)
Received Date: 2014-12-01
Rev Recd Date: 2015-03-16
Publish Date: 2017-01-10

Abstract

Abstract

A fast and efficient hardware implementation for computing the Singular value decomposition (SVD) and Eigenvalue decomposition (EVD) is presented. Considering that the SVD and EVD are complex and expensive operations, to achieve high performance with low computing complexity, our approach takes full advantage of the combination of parallel and sequential computation, which can increase efficiently the hardware utilization. Besides, regarding to EVD, we propose a hardware solution of a simplified Coordinate rotation digital computer (CORDIC)-like algorithm which can obtain higher speed. The performance analysis and comparison results show that the proposed methods can be realized on Filed-programmable gate arrays (FPGAs) with less computation time by using systolic array. It will be shown that the proposed implementation could be an efficient alternative for real-time applications.
- SVD,
- EVD,
- Jacobi,
- CORDIC,
- FPGA

FullText(HTML)

References(17)

References

M. Xu, H. Chen and P.K. Varshney, "Dimensionality reduction for registration of high-dimensional data sets", IEEE Transactions on Image Processing, Vol.22, No.8, pp.3041-3049, 2013.

L.L. Xu, J. Li, Y.M. Shu, et al., "SAR image denoising via clustering-based principal component analysis", IEEE Geoscience and Remote Sensing Letters, Vol.122, No.11, pp.6858-6869, 2014.

T.T. Cai and A.R. Zhang, "Sparse representation of a polytope and recovery of sparse signals and low-rank matrices", IEEE Transactions on Information Theory, Vol.60, No.1, pp.122-132, 2014.

J.Y. Ma, J. Zhao, J.W. Tian, et al., "Regularized vector field learning with sparse approximation for mismatch removal", Pattern Recognition, Vol.46, No.12, pp.3519-3532, 2013.

S. Lahabar and P.J. Narayana, "Singular value decomposition on GPU using CUDA", Proc. of IEEE International Symposium on Parallel & Distributed Processing, Rome, Italy, pp.1-10, 2009.

A. Ahmedsaid, A. Amira and A. Bouridane, "Acceleration MUSIC method on reconfigurable hardware for source localisation", Proc. of the 2004 International Symposium on Circuits and Systems, Vancouver, Canada, Vol.3, pp.369-372, 2004.

W. Tao and P. Wei, "Hardware efficient architectures of improved Jacobi method to solve the eigen problem", Proc. of the 2nd International Conference on Computer Engineering and Technology, Chengdu, China, Vol.6, pp.22-25, 2010.

M. Rahmati, M.S. Sadri and M.A. Naeini, "FPGA based singular value decomposition for image processing applications", Proc. of the International Conference on ApplicationSpecific Systems, Architectures and Processors, Leuven, Belgium, pp.185-190, 2008.

I. Bravo, M. Mazo, J.L. Lazaro, et al., "Novel HW architecture based on FPGAs oriented to solve the eigen problem", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol.16, No.12, pp.1722-1725, 2008.

X.Y. Wang and J. Zambreno, "An efficient architecture for floating-point eigenvalue decomposition", Proc. of IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines, Boston, USA, pp.64-67, 2014.

R.P. Brent, F.T. Luk and V.L. Charles, "Computation of the singular value decomposition using mesh-connected processors", Journal of VLSI and Computer Systems, Vol.1, No.3, pp.242-270, 1983.

W.W. Ma, M.E. Kaye, D.M. Luke, et al., "An FPGA-based singular value decomposition processor", Proc. of Canadian Conference on Electrical and Computer Engineering, Ottawa, Canada, pp.1047-1050, 2006.

J. Srinivasan and S. Rajaram, "FPGA implementation of precoding using low complexity SVD for MIMO-OFDM systems", Proc. of International on Information Communication and Embedded Systems, Chennai, India, pp.1057-1063, 2013.

B. Yang and J.F. Bohme, "Reducing the computation of the singular value decomposition array given by Brent and Luk", SIAM Journal on Matrix Analysis and Applications, Vol.12, No.4, pp.713-725, 1991.

C. Bobda and N. Steenbock, "Singular value decomposition on distributed reconfigurable systems", Proc. of the 12th International Workshop on Rapid System Prototyping, Monterey, USA, pp.38-43, 2001.

E. Doukhnitch, M. Salamah and A. Andreev, "Effective processor architecture for matrix decomposition", Arabian Journal for Science and Engineering, Vol.39, No.3, pp.1797-1804, 2014.

A. Ahmedsiad and A. Amira, "Accelerating SVD on reconfigurable hardware for image denoising", Proc. of International Conference on Image Processing, Singapore, Vol.1, pp.259-262, 2004.

Relative Articles

Supplements(0)

Cited By

Proportional views