Sparse Householder QR factorization on a mesh

Doallo, Ramón; Touriño, Juan; Zapata, Emilio L.

Use this link to cite:

http://hdl.handle.net/2183/22843

Sparse Householder QR factorization on a mesh

Files

R.Doallo_Sparse_Householder_QR_factorization_on_a_mesh_1996.pdf (230.59 KB)

Identifiers

URI: http://hdl.handle.net/2183/22843

DOI: 10.1109/EMPDP.1996.500566

Publication date

1996-01

Authors

Doallo, Ramón

Touriño, Juan

Zapata, Emilio L.

Bibliographic citation

R. Doallo, J. Tourino and E. L. Zapata, "Sparse Householder QR factorization on a mesh," Proceedings of 4th Euromicro Workshop on Parallel and Distributed Processing, Braga, Portugal, 1996, pp. 33-39. doi: 10.1109/EMPDP.1996.500566

Abstract

[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.

Description

This is a post-peer-review, pre-copyedit version of an article published in Proceedings of 4th Euromicro Workshop on Parallel and Distributed Processing. The final authenticated version is available online at: http://dx.doi.org/10.1109/EMPDP.1996.500566.