A Parallel QR Method Using Fast Givens' Rotations.

Abstract

Given a prescribed order in which to introduce zeroes, and constraints on the architecture it is shown how to develop a parallel QR factorization based on fast Givens' rotations for a rectangular array of processors, suitable to VLSI implementation. Unlike designs based on standard Givens' transformations, the present one requires no square root computations. Assuming each processor performs the elementary operations (+,*,/), less than O(w sub 2) processors can achieve the decomposition of a w-banded, order n matrix in time O(n). Application is made to a variant of Bareiss' G-Algorithm for the solution of weighted multiple linear least squares problems. Given k different right hand side vectors, (w sub 2) processors compute the factorization in O(n + k) steps. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1984
Accession Number
ADA139184

Entities

People

  • I. C. F. Ipsen

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Bandwidth
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Decomposition
  • Equations
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Military Research
  • Optimization
  • Rotation
  • Simplex Method
  • Square Roots
  • Standards

Fields of Study

  • Engineering

Readers

  • Linear Algebra
  • Parallel and Distributed Computing.