Extreme Optimization™: Complexity made simple.

Math and Statistics
Libraries for .NET

  • Home
  • Features
    • Math Library
    • Vector and Matrix Library
    • Statistics Library
    • Performance
    • Usability
  • Documentation
    • Introduction
    • Math Library User's Guide
    • Vector and Matrix Library User's Guide
    • Data Analysis Library User's Guide
    • Statistics Library User's Guide
    • Reference
  • Resources
    • Downloads
    • QuickStart Samples
    • Sample Applications
    • Frequently Asked Questions
    • Technical Support
  • Blog
  • Order
  • Company
    • About us
    • Testimonials
    • Customers
    • Press Releases
    • Careers
    • Partners
    • Contact us
Introduction
Deployment Guide
Nuget packages
Configuration
Using Parallelism
Expand Mathematics Library User's GuideMathematics Library User's Guide
Expand Vector and Matrix Library User's GuideVector and Matrix Library User's Guide
Expand Data Analysis Library User's GuideData Analysis Library User's Guide
Expand Statistics Library User's GuideStatistics Library User's Guide
Expand Data Access Library User's GuideData Access Library User's Guide
Expand ReferenceReference
  • Extreme Optimization
    • Features
    • Solutions
    • Documentation
    • QuickStart Samples
    • Sample Applications
    • Downloads
    • Technical Support
    • Download trial
    • How to buy
    • Blog
    • Company
    • Resources
  • Documentation
    • Introduction
    • Deployment Guide
    • Nuget packages
    • Configuration
    • Using Parallelism
    • Mathematics Library User's Guide
    • Vector and Matrix Library User's Guide
    • Data Analysis Library User's Guide
    • Statistics Library User's Guide
    • Data Access Library User's Guide
    • Reference
  • Vector and Matrix Library User's Guide
    • Basic Concepts
    • Vectors
    • Matrices
    • Structured Matrix Types
    • Matrix Decompositions
    • Sparse Vectors and Matrices
    • Complex Linear Algebra
    • Single-Precision Linear Algebra
    • Distributed and GPU Computing
  • Matrix Decompositions
    • The LU Decomposition
    • The QR Decomposition
    • The Cholesky Decomposition
    • The Symmetric Indefinite Decomposition
    • The Eigenvalue Decomposition
    • The Generalized Eigenvalue Decomposition
    • The Singular Value Decomposition
    • The Generalized Singular Value Decomposition
    • Non-Negative Matrix Factorization
    • Solving Linear Systems
  • The QR Decomposition

The QR Decomposition

Extreme Optimization Numerical Libraries for .NET Professional

The QR decomposition or QR factorization of a matrix expresses the matrix as the product of an orthogonal matrix and an upper triangular matrix. The matrix can be of any type, and of any shape. The QR decomposition is usually written as

A = QR,

where Q is a square, orthogonal matrix (or a unitary matrix if A is complex), and R is an upper-triangular matrix. The QR algorithm uses orthogonal (or unitary) transformations. This gives the QR decomposition much better numerical stability than the LU decomposition, even though the computation takes twice as long. When the matrix is ill-conditioned, or high accuracy is required, the longer running time is justified.

Working with QR Decompositions

The QR decomposition is implemented by the QRDecompositionT class. It has no constructors. Instead, it is created by calling the GetQRDecomposition method on the matrix. This method has two overloads. The first overload has no arguments. The second overload takes a Boolean value that specifies whether the contents of the matrix may be overwritten by the QR decomposition. The default is .

C#
VB
C++
F#
Copy
var A = Matrix.Create(5, 3, new double[] {
    2.0, 2.0, 1.6, 2.0, 1.2,
    2.5, 2.5,-0.4,-0.5,-0.3,
    2.5, 2.5, 2.8, 0.5,-2.9
}, MatrixElementOrder.ColumnMajor);
var qr = A.GetQRDecomposition();
Dim A = Matrix.Create(5, 3, New Double() {
    2.0, 2.0, 1.6, 2.0, 1.2,
    2.5, 2.5, -0.4, -0.5, -0.3,
    2.5, 2.5, 2.8, 0.5, -2.9
}, MatrixElementOrder.ColumnMajor)
Dim qr = A.GetQRDecomposition()
'

No code example is currently available or this language may not be supported.

let A = Matrix.Create(5, 3,
            [|
                2.0; 2.0; 1.6; 2.0; 1.2;
                2.5; 2.5;-0.4;-0.5;-0.3;
                2.5; 2.5; 2.8; 0.5;-2.9 
            |], MatrixElementOrder.ColumnMajor)
let qr = A.GetQRDecomposition()

The Decompose method performs the actual decomposition. This method copies the matrix if necessary. It then calls the appropriate LAPACK routine to perform the actual decomposition. This method is called by other methods as needed. You will rarely need to call it explicitly.

Once the decomposition is computed, a number of operations can be performed in much less time. You can repeatedly solve a system of simultaneous linear equations with different right-hand sides. If the system is overdetermined, you can use the LeastSquaresSolve method to obtain a least squares solution to an over-determined system. If the matrix is square, you can also calculate the determinant and the inverse of the base matrix:

C#
VB
C++
F#
Copy
var b = Vector.Create(1.1, 0.9, 0.6, 0.0, -0.8);
var x = qr.LeastSquaresSolve(b);
Dim b = Vector.Create(1.1, 0.9, 0.6, 0.0, -0.8)
Dim x = qr.LeastSquaresSolve(b)
'

No code example is currently available or this language may not be supported.

let b = Vector.Create(1.1, 0.9, 0.6, 0.0, -0.8)
let x = qr.LeastSquaresSolve(b)

The OrthogonalFactor property returns orthogonal matrix, Q, of the decomposition. The UpperTriangularFactor property returns a TriangularMatrixT containing the upper triangular matrix, R:

C#
VB
C++
F#
Copy
var Q = qr.OrthogonalFactor;
var R = qr.UpperTriangularFactor;
var R2 = qr.TrimmedUpperTriangularFactor;
Dim Q = qr.OrthogonalFactor
Dim R = qr.UpperTriangularFactor
Dim R2 = qr.TrimmedUpperTriangularFactor
'

No code example is currently available or this language may not be supported.

let Q = qr.OrthogonalFactor
let R = qr.UpperTriangularFactor
let R2 = qr.TrimmedUpperTriangularFactor

The matrix Q is kept in a compact format. Although it is possible to convert it to a regular dense matrix, the calculation is fairly expensive. Fortunately, this is hardly ever necessary. Operations like transposition, multiplication, and solving (which is equivalent to multiplying by the transpose for an orthogonal matrix) avoid the conversion:

C#
VB
C++
F#
Copy
var Qx = Q * x;
var QTx = Q.Transpose() * x;
var QTx2 = Q.Solve(x);
Dim Qx = Q * x
Dim QTx = Q.Transpose() * x
Dim QTx2 = Q.Solve(x)
'

No code example is currently available or this language may not be supported.

let Qx = Q * x
let QTx = Q.Transpose() * x
let QTx2 = Q.Solve(x)

When the number of rows of the matrix A is greater than the number of columns, the triangular matrix R will contain rows of zeros below the diagonal. The columns of Q that are multiplied by these rows in the product QR do not contribute to the product. In this scenario, two further properties may be useful. The TrimmedUpperTriangularFactor property returns the square part of the matrix R, with the zero rows removed. The ThinOrthogonalFactor property returns the orthogonal matrix with the columns that don't contribute to the product removed.

The RQ, QL, and LQ Decompositions

There are several matrix decompositions that are closely related to the QR decomposition. The RQ decomposition factors a matrix into a product RQ, where R is an upper triangular matrix and Q is an orthogonal matrix. The QL decomposition factors a matrix into a product QL, where L is a lower triangular matrix, and the LQ decomposition factors matrix into a product LQ.

These decompositions are implemented by the RQDecompositionT, QLDecompositionT, and LQDecompositionT classes, respectively. They work in exactly the same way as the QR decomposition. There are GetRQDecompositionGetQLDecompositionGetLQDecomposition methods that return the decomposition for a specific matrix. The properties are analogous, including the trimmed and thin versions.

Copyright (c) 2004-2021 ExoAnalytics Inc.

Send comments on this topic to support@extremeoptimization.com

Copyright © 2004-2021, Extreme Optimization. All rights reserved.
Extreme Optimization, Complexity made simple, M#, and M Sharp are trademarks of ExoAnalytics Inc.
Microsoft, Visual C#, Visual Basic, Visual Studio, Visual Studio.NET, and the Optimized for Visual Studio logo
are registered trademarks of Microsoft Corporation.