Householder transformation

In linear algebra, a Householder transformation (also known as a Householder reflection or elementary reflector) is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. The Householder transformation was used in a 1958 paper by Alston Scott Householder. Its analogue over general inner product spaces is the Householder operator. The reflection hyperplane can be defined by its normal vector, a unit vector (a vector with length ) that is orthogonal to the hyperplane. The reflection of a point about this hyperplane is the linear transformation: where is given as a column unit vector with conjugate transpose . The matrix constructed from this transformation can be expressed in terms of an outer product as: is known as the Householder matrix, where is the identity matrix. The Householder matrix has the following properties: it is Hermitian: , it is unitary: , hence it is involutory: . A Householder matrix has eigenvalues . To see this, notice that if is orthogonal to the vector which was used to create the reflector, then , i.e., is an eigenvalue of multiplicity , since there are independent vectors orthogonal to . Also, notice , and so is an eigenvalue with multiplicity . The determinant of a Householder reflector is , since the determinant of a matrix is the product of its eigenvalues, in this case one of which is with the remainder being (as in the previous point). In geometric optics, specular reflection can be expressed in terms of the Householder matrix (see ). Householder transformations are widely used in numerical linear algebra, for example, to annihilate the entries below the main diagonal of a matrix, to perform QR decompositions and in the first step of the QR algorithm. They are also widely used for transforming to a Hessenberg form. For symmetric or Hermitian matrices, the symmetry can be preserved, resulting in tridiagonalization.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (2)

Concepts associés (18)

Cours associés (6)

Séances de cours associées (85)

MOOCs associés (9)

A Householder-Based Algorithm For Hessenberg-Triangular Reduction

Daniel Kressner, Zvonimir Bujanovic

The QZ algorithm for computing eigenvalues and eigenvectors of a matrix pencil A - lambda B requires that the matrices first be reduced to Hessenberg-triangular (HT) form. The current method of choice for HT reduction relies entirely on Givens rotations regrouped and accumulated into small dense matrices which are subsequently applied using matrix multiplication routines. A nonvanishing fraction of the total flop-count must nevertheless still be performed as sequences of overlapping Givens rotations alternately applied from the left and from the right. The many data dependencies associated with this computational pattern leads to inefficient use of the processor and poor scalability. In this paper, we therefore introduce a fundamentally different approach that relies entirely on (large) Householder reflectors partially accumulated into block reflectors, by using (compact) WY representations. Even though the new algorithm requires more floating point operations than the state-of-the-art algorithm, extensive experiments on both real and synthetic data indicate that it is still competitive, even in a sequential setting. The new algorithm is conjectured to have better parallel scalability, an idea which is partially supported by early small-scale experiments using multithreaded BLAS. The design and evaluation of a parallel formulation is future work.

SIAM PUBLICATIONS2018

A block algorithm for computing antitriangular factorizations of symmetric matrices

Daniel Kressner, Zvonimir Bujanovic

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by Mastronardi and Van Dooren, the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia.

Springer2016

Householder transformation

Valeur propre, vecteur propre et espace propre

En mathématiques, et plus particulièrement en algèbre linéaire, le concept de vecteur propre est une notion algébrique s'appliquant à une application linéaire d'un espace dans lui-même. Il correspond à l'étude des axes privilégiés, selon lesquels l'application se comporte comme une dilatation, multipliant les vecteurs par une même constante. Ce rapport de dilatation est appelé valeur propre, les vecteurs auxquels il s'applique s'appellent vecteurs propres, réunis en un espace propre.

Décomposition d'une matrice en éléments propres

En algèbre linéaire, la décomposition d'une matrice en éléments propres est la factorisation de la matrice en une forme canonique où les coefficients matriciels sont obtenus à partir des valeurs propres et des vecteurs propres. Un vecteur non nul v à N lignes est un vecteur propre d'une matrice carrée A à N lignes et N colonnes si et seulement si il existe un scalaire λ tel que : où λ est appelé valeur propre associée à v. Cette dernière équation est appelée « équation aux valeurs propres ».

Algèbre Linéaire (Partie 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algèbre Linéaire (Partie 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algèbre Linéaire (Partie 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

The microstructure of many alloys and ceramics are constituted of very fine intricate domains (variants) created by diffusive or displacive phase transformations. The course introduces the crystallogr

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.

The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

Transformations linéaires : Injectives et Surjectives

Explore les transformations linéaires injectables et surjectives, le noyau, l'image et les opérations matricielles.

Hermite Forme normale MATH-115(a): Advanced linear algebra II

Couvre la forme normale hermite, une méthode pour transformer une matrice en une forme spécifique.

Changement de base : Motivation MOOC: Algèbre Linéaire (Partie 1)

Explore la motivation derrière le changement de base dans l'algèbre linéaire, soulignant l'importance de choisir la bonne base.