QR decomposition

Summary

In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix A into a product A = QR of an orthonormal matrix Q and an upper triangular matrix R. QR decomposition is often used to solve the linear least squares problem and is the basis for a particular eigenvalue algorithm, the QR algorithm. Cases and definitions Square matrix Any real square matrix A may be decomposed as : A = QR, where Q is an orthogonal matrix (its columns are orthogonal unit vectors meaning Q^\textsf{T} = Q^{-1}) and R is an upper triangular matrix (also called right triangular matrix). If A is invertible, then the factorization is unique if we require the diagonal elements of R to be positive. If instead A is a complex square matrix, then there is a decomposition A = QR where Q is a unitary matrix (so Q^\dagger = Q^{-1}). I

Official source

https://en.wikipedia.org/wiki/QR_decomposition

About this result

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 publications (7)

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.

EPFL2018

MATHICSE Technical Report : Fast QR decomposition of HODLR matrices

Daniel Kressner, Ana Susnjara

The efficient and accurate QR decomposition for matrices with hierarchical low-rank structures, such as HODLR and hierarchical matrices, has been challenging. Existing structure-exploiting algorithms are prone to numerical instability as they proceed indi- rectly, via Cholesky decompositions or a block Gram-Schmidt procedure. For a highly ill-conditioned matrix, such approaches either break down in finite-precision arithmetic or result in significant loss of orthogonality. Although these issues can sometimes be addressed by regularization and iterative refinement, it would be more desirable to have an algorithm that avoids these detours and is numerically robust to ill-conditioning. In this work, we propose such an algorithm for HODLR matrices. It achieves accuracy by utilizing House- holder reflectors. It achieves efficiency by utilizing fast operations in the HODLR format in combination with compact WY representations and the recursive QR decomposition by Elmroth and Gustavson. Numerical experiments demonstrate that our newly proposed al- gorithm is robust to ill-conditioning and capable of achieving numerical orthogonality down to the level of roundoff error.

MATHICSE2018

In this work we combine the framework of the Reduced Basis method (RB) with the framework of the Localized Orthogonal Decomposition (LOD) in order to solve parametrized elliptic multiscale problems. The idea of the LOD is to split a high dimensional Finite Element space into a low dimensional space with comparably good approximation properties and a remainder space with negligible information. The low dimensional space is spanned by locally supported basis functions associated with the node of a coarse mesh obtained by solving decoupled local problems. However, for parameter dependent multiscale problems, the local basis has to be computed repeatedly for each choice of the parameter. To overcome this issue, we propose an RB approach to compute in an "offline" stage LOD for suitable representative parameters. The online solution of the multiscale problems can then be obtained in a coarse space (thanks to the LOD decomposition) and for an arbitrary value of the parameters (thanks to a suitable "interpolation" of the selected RB). The online RB-LOD has a basis with local support and leads to sparse systems. Applications of the strategy to both linear and nonlinear problems are given.

2015

Related people

No results

Related units

No results

Related concepts (25)

Related concepts

Related courses (28)

Related courses

Related lectures (63)

Related lectures

EPFL2018