Almost Linear Time Matrix Operations On The Connection Machine
L. Magnus Ewerbring, Franklin T. Luk · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1988
Four matrix operations: matrix multiplication, the QR decomposition, the singular value decomposition, and the generalized singular value decomposition, form the basic tools for modern signal processing. This paper discusses their implementation on the 65,536-processor Connection Machine, and presents results showing that for n X n matrices, where n <256, an almost linear time performance is obtained. Our other major result is a novel method for computing the generalized singular value decomposition.