Extreme Optimization >
User's Guide >
Vector and Matrix Library >
Matrix Decompositions >
The LU Decomposition
Extreme Optimization User's Guide
User's Guide
Up: Matrix Decompositions Next: The QR Decomposition Previous: Matrix Decompositions Contents
The LU Decomposition
The LU decomposition or LU factorization of a matrix
expresses the matrix as the product of a lower triangular matrix
and an upper triangular matrix. The matrix can be of any type, and
of any shape.The LU decomposition is usually written as
A = PLU,
where P is a permutation matrix, L is a
lower-triangular matrix, and U is an upper-triangular
matrix. If A has more rows than columns, then L
is rectangular, and R is square. If A has more
columns than rows, then U is rectangular, and R
is square. The algorithm uses row pivoting.
The LU decomposition is most commonly used in the solution of
systems of simultaneous linear equations. The method is at least
twice as fast as other decomposition algorithms. Unfortunately, the
method has less desirable numerical problems. For ill-conditioned
problems, or when high accuracy is needed, the QR decomposition would be preferred.
In the Extreme Optimization Mathematics Library for
.NET, the LU decomposition is implemented by the
LUDecomposition
class.
The LUDecomposition
class represents the LU decomposition of a matrix. It has
two constructors. The first variant takes a Matrix as
its only parameter.
| C# |  Copy Code |
|---|
GeneralMatrix aLU = new GeneralMatrix(4, 4,
new double[]
{
1.80, 5.25, 1.58, -1.11,
2.88,-2.95, -2.69, -0.66,
2.05,-0.95, -2.90, -0.59,
-0.89,-3.80,-1.04, 0.80
});
LUDecomposition lu = new LUDecomposition(A); |
| Visual Basic | Copy Code |
|---|
Dim aLU As GeneralMatrix = New GeneralMatrix(4, 4, _
New Double() _
{ _
1.8, 5.25, 1.58, -1.11, _
2.88, -2.95, -2.69, -0.66, _
2.05, -0.95, -2.9, -0.59, _
-0.89, -3.8, -1.04, 0.8 _
})
Dim lu As LUDecomposition = New LUDecomposition(A) |
The second constructor takes a GeneralMatrix
as its first parameter. The second parameter is a
Boolean value that specifies whether the contents of
the first parameter should be overwritten by the LU
decomposition. The default is false.
| C# | Copy Code |
|---|
LUDecomposition lu2 = new LUDecomposition(A, true); |
| Visual Basic | Copy Code |
|---|
Dim lu2 As LUDecomposition = New LUDecomposition(A, True) |
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.
You can also calculate the determinant and the inverse of the base
matrix:
| C# | Copy Code |
|---|
GeneralMatrix bLU = new GeneralMatrix(4, 2, new double[]
{
9.52,24.35,0.77,-6.22,
18.47,2.25,-13.28,-6.21
});
Matrix xLU = lu.Solve(bLU);
Console.WriteLine("Ax = b -> x = {0}", xLU);
Console.WriteLine("Inv A = {0}", lu.GetInverse().ToString("F4"));
Console.WriteLine("Det A = {0}", lu.GetDeterminant()); |
| Visual Basic | Copy Code |
|---|
Dim bLU As GeneralMatrix = New GeneralMatrix(4, 2, New Double() _
{ _
9.52, 24.35, 0.77, -6.22, _
18.47, 2.25, -13.28, -6.21 _
})
Dim xLU As Matrix = lu.Solve(bLU)
Console.WriteLine("Ax = b -> x = {0}", xLU)
Console.WriteLine("Inv A = {0}", lu.GetInverse().ToString("F4"))
Console.WriteLine("Det A = {0}", lu.GetDeterminant()) |
The
LowerTriangularFactor and
UpperTriangularFactor properties return
a TriangularMatrix
containing the lower and upper triangular matrices, L and
U, of the decomposition.
| C# | Copy Code |
|---|
Console.WriteLine("L = {0}", lu.UpperTriangularFactor.ToString("F4"))
Console.WriteLine("U = {0}", lu.UpperTriangularFactor.ToString("F4")) |
| Visual Basic | Copy Code |
|---|
Console.WriteLine("L = {0}", lu.UpperTriangularFactor.ToString("F4"));
Console.WriteLine("U = {0}", lu.UpperTriangularFactor.ToString("F4")); |
The permutation matrix P is not available explicitly.
Instead, the ApplyP
method lets you multiply a vector or a matrix by P
directly. GeneralVector
and GeneralMatrix
objects can be overwritten by the result. Other types of vectors
and matrices are always copied first.
| C# | Copy Code |
|---|
Console.WriteLine("Px = {0}", lu.ApplyP(xLU)); |
| Visual Basic | Copy Code |
|---|
Console.WriteLine("Px = {0}", lu.ApplyP(xLU)) |
Band LU Decomposition
The LU decomposition without pivoting of a band matrix
is made up of a lower band matrix with lower bandwidth the same as
the original matrix and an upper band matrix with upper band with
the same as the original matrix. However, pivoting destroys this
band structure to a large degree. The bandwidth of the upper
triangular matrix is the total bandwidth of the original matrix,
and the lower triangular matrix generally doesn't have any band
structure, although the number of nonzero elements in each column
is limited.
As a result, the factors of the decomposition can't be isolated
easily, but the other advantages of the LU decomposition remain. It
is much more efficient to repeatedly solve a system of linear
equations using the LU decomposition than repeating all the
calculations each time.
The band LU decomposition is implemented by the BandLUDecomposition
class. This class has the equivalent functionality as the general
LUDecomposition class, with some limitations.
If a matrix is to be overwritten with its LU decomposition, the
matrix must have enough storage allocated to allow for the upper
band to fill up to its maximum width. This can be achieved by
setting the allocateForLUDecomposition parameter in
the BandMatrix constructor to true.
The other limitation is that the lower triangular factor of the
decomposition is not available.
Up: Matrix Decompositions Next: The QR Decomposition Previous: Matrix Decompositions Contents
Copyright 2004-2008,
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 Visual Studio Logo are registered trademarks of Microsoft Corporation