i-manager Publications

Parallel Singular Value Decomposition Algorithm on Cell Broadband Engine Architecture

Padmaja Kanase*, Ankush Mittal**, Kuldip Singh***

* Department of Electronics and Computer Engineering, Indian Institute of Technology, Roorkee.

** Department of Computer Science, College of Engineering, Roorkee.

*** Department of Electronics and Computer Engineering, Indian Institute of Technology, Roorkee.

Periodicity:October - December'2010
DOI : https://doi.org/10.26634/jse.5.2.1331

Abstract

The singular value decomposition (SVD) is an important technique used for factorization of a rectangular real or complex matrix. But computationally SVD is very expensive in terms of time and space. Multicore processors can be used for such type of problems which are computationally intensive. The Cell Broadband Engine is one such multicore processor consisting of a traditional PowerPC based master core meant to run the operating system, and 8 delegate slave processors built for compute intensive processing. This work introduces a modification on the serial singular value decomposition algorithm. It describes parallel implementation of the modified algorithm on Cell BE and issues involved. Exposure of system level optimization features in Cell BE has been employed on algorithm specific operations to achieve improvements to a great extent. The implementation achieves significant performance, thereby giving about 8 times speedup over sequential implementation.

Keywords

Bidiagonalization,Cell BE,Diagonalization,Gulab-Kahan-Riench SVD, Parallelization,Singular Value Decomposition.

How to Cite this Article?

Padmaja Kanase, Ankush Mittal and Kuldip Singh (2010). Parallel Singular Value Decomposition Algorithm on Cell Broadband Engine Architecture. i-manager’s Journal on Software Engineering, 5(2), 16-25. https://doi.org/10.26634/jse.5.2.1331

References

[1]. Wall, Michael E., Andreas Rechtsteiner, Luis M. Rocha. (2003). "Singular value decomposition and principal component analysis" in A Practical Approach to Microarray Data Analysis. D.P. Berrar, W. Dubitzky, M. Granzow, eds. pp. 91-109, Kluwer: Norwell, MA (2003). LANL LA-UR-02-4001.

[2]. Virginia C. Klema, and Alan J. Laub, (1980). “The Singular Value Decomposition: Its Computation and Some Applications”, IEEE transactions on Automatic Control, Vol. Ac-25, No. 2, April.

[3]. Cell Broadband Engine - An Introduction, (2007). Cell Programming Workshop, IBM Systems and Technology Group, April 14-18.

[4]. Cell Broadband Engine Programming Tutorial v2.0 (2006). http://moss.csc.ncsu.edu/~mueller/cluster /ps3/CBE_Tutorial_v2.0_15December2006.pdf.

[5]. Cell Broadband Engine programming handbook, Version 3.0, (April 2006). htts://www-01.ibm.com/ chips/techlib/techlib.nsf/techdocs/ FC857AE550F7EB838 72571A80061F788/$file/CBE_Programming_Tutorial_v3. 0.pdf.

[6]. Forsythe, G.E., and P. Henrici, (1960). “The cyclic Jacobi method”. Trans. Amer. Math. Soc. 94, 1–23 .

[7]. Gene H. Golub and Charles F. Van Loan. (1993). Matrix Computations. John Hopkins University Press, Baltimore and London, 2nd edition.

[8]. Volker Strumpen, Henry Hoffmann, and Anant Agarwal, (2003). “A Stream Algorithm for the SVD”, Technical Memo, MIT-LCS-TM-64, October 22.

[9]. Magnus R. Hestenes, (1958).“Inversion of Matrices by Biorthogonalization and Related Results” Journal of the Society for Industrial and Applied Mathematics, 6(1):51- 90, March.

[10]. Gene H. Golub and Christian Reinsch, (1971). “Singular Value Decomposition and Least Square Solutions” In J. H. Wilkinson and C. Reinsch, editors, Linear Algebra, volume II of Handbook for Automatic Computations, chapter I/10, pp. 134-151. Springer Verlag.

[11]. W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannary: (1997). “Numerical Recipes in C”, Cambridge University Press, New York.

[12]. J. Kurzak and J.J. Dongarra, (2008). "QR Factorization for the CELL Processor," J. Scientific Programming, special issue on high performance computing on CELL B.E. processors, pp. 1-12.

[13]. http://en.wikipedia.org/wiki/Bidiagonal_matrix

[14]. B. Grosser and B. Lang, (1999). "Efficient Parallel Reduction to Bidiagonal Form," Parallel Computing, Vol. 25, No. 8, pp. 969-986

[15]. N. Bosner and J.L. Barlow, (2007). "Block and Parallel Versions of One-Sided bidiagonalization," SIAM J. Matrix Analysis and Applications, Vol. 29, No. 3, pp. 927-953.

[16]. http://en.wikipedia.org/wiki/Diagonal_matrix

[17]. James Demmel, W. Kahan, (1990). “Accurate Singular Values of Bidiagonal Matrices”, SIAM Journal on Scientific and Statistical Computing, Vol. 11, No. 5, pp. 873-912, September

If you have access to this article please login to view the article or kindly login to purchase the article

Single Article

	North Americas,UK, Middle East,Europe		India	Rest of world
	USD	EUR	INR	USD-ROW
Online	15	15

ADD TO CART

Options for accessing this content:

If you would like institutional access to this content, please recommend the title to your librarian.
If you already have i-manager's user account: Login above and proceed to purchase the article.
New Users: Please register, then proceed to purchase the article.