WestminsterResearch

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: http://dx.doi.org/10.1080/00207169308804177

Abstract

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
Research Community:University of Westminster > Electronics and Computer Science, School of
ID Code:5769
Deposited On:30 Jan 2009 09:58
Last Modified:19 Oct 2009 16:39

Repository Staff Only: item control page