Distributed orthogonal factorization

ABSTRACT

We describe several algorithms for computing the orthogonal factorization on distributed memory multiprocessors. One of the algorithms is based on Givens rotations, two others employ column Householder transformations but with different communication schemes: broadcast and pipelined ring. A fourth algorithm is a hybrid; it uses Househlolder transformations and Givens rotations in separate phases. We present expressions for the arithmetic and communication complexity of each algorithm. The algorithms were implemented on an iPSC-286 and the observed times agree well with our analyses.

REFERENCES

• 1: Alan George and Joseph Liu, Householder reflections versus Givens rotations in sparse orthogonal decomposition, Lin. Alg. Appl., 88(1987), pp. 223--238.
• 2: Alan George , Joseph Liu , Esmond Ng, A data structure for sparse QR and LU factorizations, SIAM Journal on Scientific and Statistical Computing, v.9 n.1, p.100-121, January 1988 [doi>10.1137/0909008]
• 3: W. M. Gentleman, Error analysis of Q decomposition by Givens transformations,
• 4: J. Johnson, A computation array for the QR method, 1982 Conference on Advanced Research in VLSI, MIT Press, 1982, pp. 123--129.
• 5: Alex Pothen, Somesh Jha, and Udaya Vemulapati, Orthogonal factorizat~'on on a distributed memory multiprocessor, In Heath (1987), pp. 587--596.
• 6: Alex Po~ten and Padma Raghavan, Distributed orthogonal factorization: Givens and Househokler algorithms, Report CS-87-24, Deparunent of Computer Science, The Pennsylvania State University, University Park, PA 16802, july 1987.
• 7: A. H. Sameh , D. J. Kuck, On Stable Parallel Linear System Solvers, Journal of the ACM (JACM), v.25 n.1, p.81-91, Jan. 1978 [doi>10.1145/322047.322054]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms