A SYSTOLIC ARRAY FOR SVD UPDATING

被引：16

作者：

MOONEN, M ^{[1
]}

VANDOOREN, P ^{[1
]}

VANDEWALLE, J ^{[1
]}

机构：

[1] UNIV ILLINOIS, DEPT ELECT & COMP ENGN, URBANA, IL 61801 USA

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 1993年 / 14卷 / 02期

关键词：

SINGULAR VALUE DECOMPOSITION; PARALLEL ALGORITHMS; RECURSIVE LEAST SQUARES;

D O I：

10.1137/0614025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In an earlier paper, an approximate SVD updating scheme has been derived as an interlacing of a QR updating on the one hand and a Jacobi-type SVD procedure on the other hand, possibly supplemented with a certain re-orthogonalization scheme. This paper maps this updating algorithm onto a systolic array with 0(n2) parallelism for 0(n2) Complexity, resulting in an 0(n0) throughput. Furthermore, it is shown how a square root-free implementation is obtained by combining modified Givens rotations with approximate SVD schemes.

引用

页码：353 / 371

页数：19

共 14 条

[1] SCALED GIVENS ROTATIONS FOR THE SOLUTION OF LINEAR LEAST-SQUARES PROBLEMS ON SYSTOLIC ARRAYS [J].

BARLOW, JL ;

IPSEN, ICF .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1987, 8 (05) :716-733

[2] THE SOLUTION OF SINGULAR-VALUE AND SYMMETRIC EIGENVALUE PROBLEMS ON MULTIPROCESSOR ARRAYS [J].

BRENT, RP ;

LUK, FT .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1985, 6 (01) :69-84

[3]

Gentleman W. M., 1973, Journal of the Institute of Mathematics and Its Applications, V12, P329

[4]

GENTLEMAN WM, 1981, P SOC PHOTO-OPT INST, V298, P19

[5]

GILL PE, 1974, MATH COMPUT, V28, P505, DOI 10.1090/S0025-5718-1974-0343558-6

[6]

Hammarling S., 1974, Journal of the Institute of Mathematics and Its Applications, V13, P215

[7] COMPUTING THE SINGULAR VALUE DECOMPOSITION OF A PRODUCT OF 2 MATRICES [J].

HEATH, MT ;

LAUB, AJ ;

PAIGE, CC ;

WARD, RC .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1986, 7 (04) :1147-1159

[8]

Kogbetliantz, 1955, Q APPL MATH, V13, P123, DOI 10.1090/qam/88795

[9]

Luk F. T., 1987, Proceedings of the SPIE - The International Society for Optical Engineering, V826, P152

[10] A TRIANGULAR PROCESSOR ARRAY FOR COMPUTING SINGULAR-VALUES [J].

LUK, FT .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1986, 77 :259-273

← 1 2 →