Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Householder Reduction, Per Brinch Hansen
Householder Reduction, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial discusses Householder reduction of n linear equations to a triangular form which can be solved by back substitution. The main strengths of the method are its numerical stability and suitability for parallel computing. We explain how Householder reduction can be derived from elementary matrix algebra. The method is illustrated by a numerical example and a Pascal algorithm. We assume that the reader has a general knowledge of vector and matrix algebra but is less familiar with linear transformation of a vector space.
The All-Pairs Pipeline, Per Brinch Hansen
The All-Pairs Pipeline, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
An all-pairs problem is a computation on every possible subset consisting of two elements chosen from a set of n elements. N-body simulation and Householder reduction are all-pairs problems. The paper defines the all-pairs problem concisely by means of precedence matrices and derives a parallel algorithm. The algorithm is presented in both coarse-grain and medium-grain form. The all-pairs paradigm is illustrated by a pipeline for Householder reduction of a matrix to triangular form.