**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# A Householder-Based Algorithm For Hessenberg-Triangular Reduction

Abstract

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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (2)

Loading

Loading

Related concepts (14)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

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 con

Matrix (mathematics)

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a pr

Rémi Emonet, Jean-Marc Odobez, Jagannadan Varadarajan

This paper introduces a novel probabilistic activity modeling approach that mines recurrent sequential patterns called motifs from documents given as word×time count matrices (e.g., videos). In this model, documents are represented as a mixture of sequential activity patterns (our motifs) where the mixing weights are defined by the motif starting time occurrences. The novelties are multi fold. First, unlike previous approaches where topics modeled only the co-occurrence of words at a given time instant, our motifs model the co-occurrence and temporal order in which the words occur within a temporal window. Second, unlike traditional Dynamic Bayesian Networks (DBN), our model accounts for the important case where activities occur concurrently in the video (but not necessarily in syn- chrony), i.e., the advent of activity motifs can overlap. The learning of the motifs in these difficult situations is made possible thanks to the introduction of latent variables representing the activity starting times, enabling us to implicitly align the occurrences of the same pattern during the joint inference of the motifs and their starting times. As a third novelty, we propose a general method that favors the recovery of sparse distributions, a highly desirable property in many topic model applications, by adding simple regularization constraints on the searched distributions to the data likelihood optimization criteria. We substantiate our claims with experiments on synthetic data to demonstrate the algorithm behavior, and on four video datasets with significant variations in their activity content obtained from static cameras. We observe that using low-level motion features from videos, our algorithm is able to capture sequential patterns that implicitly represent typical trajectories of scene objects.

In this thesis we address the computation of a spectral decomposition for symmetric
banded matrices. In light of dealing with large-scale matrices, where classical dense
linear algebra routines are not applicable, it is essential to design alternative techniques
that take advantage of data properties. Our approach is based upon exploiting the
underlying hierarchical low-rank structure in the intermediate results. Indeed, we study
the computation in the hierarchically off-diagonal low rank (HODLR) format of two
crucial tools: QR decomposition and spectral projectors, in order to devise a fast spectral
divide-and-conquer method.
In the first part we propose a new method for computing a QR decomposition of a
HODLR matrix, where the factor R is returned in the HODLR format, while Q is given
in a compact WY representation. The new algorithm enjoys linear-polylogarithmic complexity and is norm-wise accurate. Moreover, it maintains the orthogonality of the Q factor.
The approximate computation of spectral projectors is addressed in the second part.
This problem has raised some interest in the context of linear scaling electronic structure
methods. There the presence of small spectral gaps brings difficulties to existing algorithms based on approximate sparsity. We propose a fast method based on a variant of
the QDWH algorithm, and exploit that QDWH applied to a banded input generates a
sequence of matrices that can be efficiently represented in the HODLR format. From
the theoretical side, we provide an analysis of the structure preservation in the final
outcome. More specifically, we derive a priori decay bounds on the singular values in
the off-diagonal blocks of spectral projectors. Consequently, this shows that our method,
based on data-sparsity, brings benefits in terms of memory requirements in comparison to
approximate sparsity approaches, because of its logarithmic dependence on the spectral
gap. Numerical experiments conducted on tridiagonal and banded matrices demonstrate
that the proposed algorithm is robust with respect to the spectral gap and exhibits linear-polylogarithmic complexity. Furthermore, it renders very accurate approximations
to the spectral projectors even for very large matrices.
The last part of this thesis is concerned with developing a fast spectral divide-and-conquer
method in the HODLR format. The idea behind this technique is to recursively split the
spectrum, using invariant subspaces associated with its subsets. This allows to obtain
a complete spectral decomposition by solving the smaller-sized problems. Following
Nakatsukasa and Higham, we combine our method for the fast computation of spectral
projectors with a novel technique for finding a basis for the range of such a HODLR
matrix. The latter strongly relies on properties of spectral projectors, and it is analyzed
theoretically. Numerical results confirm that the method is applicable for large-scale
matrices, and exhibits linear-polylogarithmic complexity.