DoubleLevinson Type
A Levinson solver for square Toeplitz systems of double type.
This class provides members for inverting the Toeplitz matrix (see DoubleLevinson.GetInverse member), calculating the determinant of the matrix (see DoubleLevinson.GetDeterminant member) and solving linear systems associated with the matrix (see DoubleLevinson.Solve members).
The class implements a UDL decomposition of the inverse of the square Toeplitz matrix. The decomposition is based upon Levinson's algorithm. As a consequence, all operations require approximately N squared FLOPS, where N is the matrix order. This is significantly faster than LU factorization, which requires N cubed FLOPS.
One disadvantage of Levinson's algorithm is that all the leading sub-matrices of the Toeplitz matrix must be non-singular. During the decomposition, sub-matrices are checked to ensure that they are non-singular. When a singular matrix is found the decomposition is halted and an interal flag is set. The DoubleLevinson.IsSingular property may be used to access the flag, to determine if any singular matrices were detected.
A outline of this approach to the UDL decomposition of inverse Toeplitz matrices is found in the following reference:
Sun-Yuan Kung and Yu Hen Hu, A Highly Concurrent Algorithm and Pipelined Architecture for Solving Toeplitz Systems, IEEE Transactions on Acoustics, Speech and Signal Processing, Volume ASSP-31, Number 1, Febuary 1983, pages 66 - 75.
Copyright (c) 2003-2004, dnAnalytics Project. All rights reserved. See http://www.dnAnalytics.net for details.
Adopted to Altaxo (c) 2005 Dr. Dirk Lellinger.
Example
The following simple example illustrates the use of the class:
using System;
using dnA.Exceptions;
using dnA.Math;
using System.IO;
namespace Example_9
{
class Application
{
// format string for matrix/vector elements
private const string frmStr = " 0.000E+000;-0.000E+000";
// application entry point
[STAThread]
public static void Main(string[] args)
{
// create levinson solver
DoubleLevinson dl = new DoubleLevinson(new double[]{10.0, 2.0, 9.0, 5.0}, new double[]{10.0, 0.0, 4.0, 0.0});
// display the Toeplitz matrix
DoubleMatrix T = dl.GetMatrix();
Console.WriteLine("Matrix:: {0} ", T.ToString(frmStr));
Console.WriteLine();
// check if matrix is singular
Console.WriteLine("Singular: {0}", dl.IsSingular);
// get the determinant
Console.WriteLine("Determinant: {0}", dl.GetDeterminant().ToString("E3"));
Console.WriteLine();
// get the inverse
DoubleMatrix Inv = dl.GetInverse();
Console.WriteLine("Inverse:: {0} ", Inv.ToString(frmStr));
Console.WriteLine();
// solve a linear system
DoubleVector X = dl.Solve(1.0, 2.0, 3.0, 4.0);
Console.WriteLine("X:: {0} ", X.ToString(frmStr));
Console.WriteLine();
}
}
}The application generates the following results:
Matrix:: rows: 4, cols: 4
1.000E+001, 0.000E+000, 4.000E+000, 0.000E+000
2.000E+000, 1.000E+001, 0.000E+000, 4.000E+000
9.000E+000, 2.000E+000, 1.000E+001, 0.000E+000
5.000E+000, 9.000E+000, 2.000E+000, 1.000E+001
Singular: False
Determinant: 4.256E+003
Inverse:: rows: 4, cols: 4
1.541E-001, 1.880E-002, -6.015E-002, -7.519E-003
-1.692E-002, 1.504E-001, 1.880E-002, -6.015E-002
-1.353E-001, -4.699E-002, 1.504E-001, 1.880E-002
-3.477E-002, -1.353E-001, -1.692E-002, 1.541E-001
X:: Length: 4
-1.880E-002, 9.962E-002, 2.970E-001, 2.603E-001
Constructors
| Constructor | Description | ||||||
Full Usage:
DoubleLevinson(col, row)
Parameters:
float[]
-
The left-most column of the Toeplitz matrix.
row : float[]
-
The top-most row of the Toeplitz matrix.
|
Constructor with
|
||||||
Full Usage:
DoubleLevinson(col, row)
Parameters:
IReadOnlyList<float>
-
The left-most column of the Toeplitz matrix.
row : IReadOnlyList<float>
-
The top-most row of the Toeplitz matrix.
|
Constructor with
|
Instance members
| Instance member | Description | ||||||
|
Get the diagonal matrix of the UDL factorisation. It is recommended that the DoubleLevinson.IsSingular property be checked to see if the decomposition was completed, before attempting to obtain the diagonal matrix.
|
||||||
Full Usage:
this.GetDeterminant
Returns: float
The determinant
|
Get the determinant of the Toeplitz matrix. It is recommended that the DoubleLevinson.IsSingular property be checked to see if the decomposition was completed, before attempting to obtain the determinant.
|
||||||
|
Get the inverse of the Toeplitz matrix. The class implicitly decomposes the inverse Toeplitz matrix into a UDL factorisation using the Levinson algorithm, before using an extended version of Trench's algorithm to complete the inversion. The extended version of Trench's algorithm requires approximately N squared FLOPS, compared to N cubed FLOPS if we simply multiplied the UDL factors (N is the matrix order).
|
||||||
|
Get a vector that represents the left-most column of the Toplitz matrix.
|
||||||
|
Get a copy of the Toeplitz matrix.
|
||||||
|
Get a vector that represents the top-most row of the Toplitz matrix.
|
||||||
Full Usage:
this.IsSingular
Returns: bool
|
Check if the Toeplitz matrix or any leading sub-matrices are singular. If the Toeplitz matrix or any leading sub-matrices are singular, it is not possible to complete the UDL decomposition using the Levinson algorithm.
|
||||||
|
Get the lower triangle matrix of the UDL factorisation. It is recommended that the DoubleLevinson.IsSingular property be checked to see if the decomposition was completed, before attempting to obtain the lower triangle matrix.
|
||||||
Full Usage:
this.Order
Returns: int
|
Get the order of the Toeplitz matrix.
|
||||||
Full Usage:
this.Solve
Parameters:
IReadOnlyList<float>
-
The right-hand side of the system.
Returns: DoubleVector
The solution vector.
|
Solve a square Toeplitz system with a right-side vector. This member solves the linear system TX = Y, where T is the square Toeplitz matrix, X is the unknown solution vector and Y is a known vector. The class implicitly decomposes the inverse Toeplitz matrix into a UDL factorisation using the Levinson algorithm, before calculating the solution vector.
|
||||||
Full Usage:
this.Solve
Parameters:
float[]
-
The right-hand side of the system.
Returns: DoubleVector
The solution vector.
|
Solve a square Toeplitz system with a right-side array. This member solves the linear system TX = Y, where T is the square Toeplitz matrix, X is the unknown solution vector and Y is a known vector. The class implicitly decomposes the inverse Toeplitz matrix into a UDL factorisation using the Levinson algorithm, before calculating the solution vector.
|
||||||
Full Usage:
this.Solve
Parameters:
IROMatrix<float>
-
The right-side matrix
Returns: DoubleMatrix
The solution matrix.
|
Solve a square Toeplitz system with a right-side matrix. This member solves the linear system TX = Y, where T is a square Toeplitz matrix, X is the unknown solution matrix and Y is a known matrix. The class implicitly decomposes the inverse Toeplitz matrix into a UDL factorisation using the Levinson algorithm, before calculating the solution vector.
|
||||||
|
Get the upper triangle matrix of the UDL factorisation. It is recommended that the DoubleLevinson.IsSingular property be checked to see if the decomposition was completed, before attempting to obtain the upper triangle matrix.
|
Static members
| Static member | Description | ||||||||
Full Usage:
DoubleLevinson.Inverse(col, row)
Parameters:
IReadOnlyList<float>
-
The left-most column of the Toeplitz matrix.
row : IReadOnlyList<float>
-
The top-most row of the Toeplitz matrix.
Returns: DoubleMatrix
The inverse matrix.
|
Invert a square Toeplitz matrix. This static member combines the UDL decomposition and Trench's algorithm into a single algorithm. It requires minimal data storage, compared to the non-static member and suffers from no speed penalty in comparision. Trench's algorithm requires N squared FLOPS, compared to N cubed FLOPS if we simply solved a linear Toeplitz system with a right-side identity matrix (N is the matrix order).
|
||||||||
Full Usage:
DoubleLevinson.Solve(col, row, Y)
Parameters:
IReadOnlyList<float>
-
The left-most column of the Toeplitz matrix.
row : IReadOnlyList<float>
-
The top-most row of the Toeplitz matrix.
Y : IReadOnlyList<float>
-
The right-side vector of the system.
Returns: DoubleVector
The solution vector.
|
Solve a square Toeplitz system with a right-side vector. This method solves the linear system AX = Y. Where T is a square Toeplitz matrix, X is an unknown vector and Y is a known vector. The classic Levinson algorithm is used to solve the system. The algorithm assumes that all the leading sub-matrices of the Toeplitz matrix are non-singular. When a sub-matrix is near singular, accuracy will be degraded. This member requires approximately N squared FLOPS to calculate a solution, where N is the matrix order. This static method has minimal storage requirements as it combines the UDL decomposition with the calculation of the solution vector in a single algorithm.
|
||||||||
Full Usage:
DoubleLevinson.Solve(col, row, Y)
Parameters:
IReadOnlyList<float>
-
The left-most column of the Toeplitz matrix.
row : IReadOnlyList<float>
-
The top-most row of the Toeplitz matrix.
Y : IROMatrix<float>
-
The right-side matrix of the system.
Returns: DoubleMatrix
The solution matrix.
|
Solve a square Toeplitz system with a right-side matrix. This method solves the linear system AX = Y. Where T is a square Toeplitz matrix, X is an unknown matrix and Y is a known matrix. The classic Levinson algorithm is used to solve the system. The algorithm assumes that all the leading sub-matrices of the Toeplitz matrix are non-singular. When a sub-matrix is near singular, accuracy will be degraded. This member requires approximately N squared FLOPS to calculate a solution, where N is the matrix order. This static method has minimal storage requirements as it combines the UDL decomposition with the calculation of the solution vector in a single algorithm.
|