Bidiagonalization and symmetric tridiagonalization by systolic arrays
Journal of VLSI signal processing systems for signal, image and video technology - Tập 1 - Trang 279-285 - 1990
Tóm tắt
We give a systolic algorithm and array for bidiagonalization of ann × n matrix inO(n logn) time, usingO(n
2) cells. Bandedness of the input matrix may be effectively exploited. If the matrix is banded, withp nonzero subdiagonals andq nonzero superdiagonals, then 4n ln(p+q)+O(n) clocks and 2n(p+q)+O((p+q)
2+n) cells are needed. This is faster than the best previously reported result by the factor log2
e=1.44.... Moreover, in contrast to earlier systolic designs, which require the matrix to be preloaded into the array and the result matrix extracted after bidiagonalization, the present arrays are pipelined.
Tài liệu tham khảo
Gene H. Golub and Charles F. Van Loan,Matrix Computations, Baltimore: Johns Hopkins, 1983.
L. Johnsson, “A computational array for the QR-method,” In P. Penfield, editor,Proc. Conference on Advanced Research in VLSI, Norwood, MA: Artech House, 1982, pp. 123–129.
S.Y. Kung and R.J. Gal-Ezar, “Eigenvalue, singular value, and least squares solvers via wavefront array processors,” InAlgorithmically Specialized Parallel Computers, L. Snyder et. al., editors. Orlando, FL: Academic Press, 1985, pp. 201–212.
G. Carlsson, H. Sexton, M. Shensa and C. Wright,Algebraic techniques in systolic array design, San Diego, CA: Naval Ocean Systems Center, 1983.
Robert Schreiber, “Computing generalized inverses and the eigenvalues of symmetric matrices using systolic arrays,” InComputing Methods in Applied Sciences and Engineering, R. Glowinski and J.L. Lions, editors, Amsterdam: North-Holland, 1984, pp. 285–295.
A. Bojanczyk and R.P. Brent, “Tridiagonalization of a symmetric matrix on a square array of mesh-connected processors,”Journal of Parallel and Distributed Computing, vol. 2, 1983, pp. 261–276.
I.C.F. Ipsen, “Singular value computations with systolic arrays,”Proc. SPIE Symp. 549 (Real-Time Signal Processing VII), 1984, pp. 13–21.
Don E. Heller and Ilse C.F. Ipsen, “Systolic networks for orthogonal decompositions,”SIAM Journal on Scientific and Statistical Computing, vol. 4, 1983, pp. 261–269.
Tony Chan, “An improved algorithm for computing the singular value decomposition,”ACM Transactions on Mathematical Software, vol. 8, 1982, pp. 72–83.
W.M. Gentleman and H.T. Kung, “Matrix triangularization by systolic array,” In Tian F. Tao, editor,Proc SPIE Symp. 298 (Real-Time Signal Processing IV), 1981, pp. 19–26.
Robert Schreiber, “On systolic array methods for band matrix factorizations,”BIT, vol. 26, 1986, pp. 303–316.
A. Bojanczyk, R.P. Brent, and H.T. Kung, “Numerically stable solution of dense systems of linear equations using mesh-connected processors,”SIAM Journal on Scientific and Statistical Computing, vol. 5, 1984, pp. 95–104.
H. Rutishauser, “On Jacobi rotation patterns,”Proc. Symp. Appl. Math., vol. 15, 1963, pp. 219–239.
Gene H. Golub, Franklin T. Luk, and Michael L. Overton, “A block Lanczos method for computing the singular values and corresponding singular vectors of a matrix,”ACM Transactions on Mathematical Software, vol. 7, 1981, pp. 149–169.
Donald E. Knuth,The Art of Computer Programming. Volume 1: Fundamental Algorithms, Reading, MA: Addison-Wesley, 1969.