QR factorization of a dense matrix on a shared-memory multiprocessor
Eleanor Chu, Alan D. George · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1987
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · Office of Scientific and Technical Information · report · 1987
Abstract
A new algorithm for computing an orthogonal decomposition of a rectangular m x n matrix A on a shared-memory parallel computer is described. The algorithm uses Givens rotations, and has the feature that its synchronization cost is low. In particular, for a multiprocessor having p processors, an analysis of the algorithm shows that this cost is O (n/sup 2//p) if m/p greater than or equal to n, and O (mn/p/sup 2/) if m/p < n. Note that in the latter case, the synchronization cost is smaller than O (n/sup 2//p). Therefore, the synchronization cost of the algorithm proposed in this article is bounded by O (n/sup 2//p) when m greater than or equal to n.
This is important for machines where synchronization cost is high, and when m >> n. Analysis and experiments show that the algorithm is effective in balancing the load and producing high efficiency (speed-up). 13 refs.
Open the resolved locator · 10.2172/5928811
Metadata licence: OpenAlex metadata (CC0)