Title :
Sparse Householder QR factorization on a mesh
Author :
Doallo, Ramón ; Tourino, Juan ; Zapata, Emilio L.
Author_Institution :
Dept. Electron. y Sistemas, Univ. de La Coruna, Spain
Abstract :
We analyze the parallelization of QR factorization by means of Householder transformations. This parallelization is carried out on a machine with a mesh topology (a 2-D torus to be more precise). We use a cyclic distribution of the elements of the sparse matrix M we want to decompose over the processors. Each processor represents the nonzero elements of its part of the matrix by a one-dimensional doubly linked list data structure. Then, we describe the different procedures that constitute the parallel algorithm. As an application of QR factorization, we concentrate on the least squares problem and finally we present an evaluation of the efficiency of this algorithm for a set of test matrices from the Harwell-Boeing sparse matrix collection
Keywords :
data structures; least squares approximations; mathematics computing; matrix decomposition; parallel algorithms; parallel machines; sparse matrices; 2D torus; Harwell-Boeing sparse matrix collection; Householder transformations; cyclic distribution; least squares problem; mesh topology; nonzero elements; one-dimensional doubly linked list data structure; parallel algorithm; sparse Householder QR factorization; sparse matrix; Chemistry; Data structures; Equations; Fluid dynamics; Least squares methods; Matrix decomposition; Parallel algorithms; Sparse matrices; System testing; Topology;
Conference_Titel :
Parallel and Distributed Processing, 1996. PDP '96. Proceedings of the Fourth Euromicro Workshop on
Conference_Location :
Braga
Print_ISBN :
0-8186-7376-1
DOI :
10.1109/EMPDP.1996.500566
