The givens-batcher reduction algorithm and matrix triangularisation

Megson, Graham M. (1993) The givens-batcher reduction algorithm and matrix triangularisation. International Journal of Computer Mathematics, 47 (3&4). pp. 199-208. ISSN 0020-7160

Full text not available from this repository.
Official URL:


A Givens sequence is any sequence of Givens rotations in which zeroes once created are preserved [3]. Givens rotations are applied to a variety of matrix problems, as a means of producing stable non-pivoting triangularisation, and have become popular recently because they are amenable to parallel and VLSI computing. A Batcher sequence is a sequence of comparisons which can be used to sort an arbitrary list of elements in a way that avoids propagation of exchanges by merging pairs of sorted subsequences. In the former case parallelism is admitted because disjoint rotations can be performed in parallel, in the latter the merging can be achieved by nonoverlapping comparisons. Batcher's method produces a highly parallel sorting network suited to VLSI implementation. In this paper we combine the two ideas to produce a Givens-Batcher sequence which reduces a matrix to triangular form using a number of passes. Batchers sorting network can then be employed as a VLSI array with pipelining and high throughput.

Item Type: Article
Subjects: University of Westminster > Science and Technology > Electronics and Computer Science, School of (No longer in use)
Depositing User: Miss Nina Watts
Date Deposited: 30 Jan 2009 09:58
Last Modified: 19 Oct 2009 15:39

Actions (login required)

Edit Item (Repository staff only) Edit Item (Repository staff only)