Documentation |
Solve a linear Toeplitz system
This functionality does not run in MATLAB.
linalg::toeplitzSolve(t, y)
linalg::toeplitzSolve(t, y) returns the solution of the linear Toeplitz system with i = 1, …, n.
linalg::toeplitzSolve(t, y) with t = [t_{k}, …, t_{0}, …, t_{- k}] and y = [y_{1}, …, y_{n}] solves the n×n Toeplitz system
with 2 k + 1 bands.
linalg::toeplitzSolve implements the Levinson algorithm. It uses O(n^{2}) elementary operations to solve the Toeplitz system. The memory requirements are O(n). For dense Toeplitz systems, it is faster than the general solver solve and the linear solvers linsolve, numeric::linsolve, linalg::matlinsolve and numeric::matlinsolve.
If linalg::toeplitzSolve does not manage to find the solution due to this limitation, or if the system is very sparse with k smaller than , we recommend to generate the corresponding Toeplitz matrix via linalg::toeplitz and compute the solution via linalg::matlinsolve or numeric::matlinsolve, respectively. Cf. Example 2
linalg::toeplitzSolve can solve Toeplitz systems over arbitrary coefficient rings. Just make sure that both the Toeplitz entries t as well as the components of the 'right hand side' y are elements of the desired coefficient ring. Cf. Example 3.
The Toeplitz entries t and the right hand side y of the linear system are entered as row vectors:
t := matrix([4, 2, 1, 3, 5]): y := matrix([y1, y2, y3]):
The solution of the Toeplitz system is returned as a vector of the same type as the input vector y:
x := linalg::toeplitzSolve(t, y): x, domtype(x)
If the input vector is a list, the output is a list, too:
x := linalg::toeplitzSolve(t, [y1, y2, y3]): x, domtype(x)
delete t, y, x:
The Levinson algorithm cannot solve the following Toeplitz system because the first principal minor of the Toeplitz matrix (the central element of the Toeplitz entries) vanishes:
linalg::toeplitzSolve([1, 0, 1], [y1, y2, y3, y4])
This does not necessarily imply that the Toeplitz system is not solvable. We generate the corresponding Toeplitz matrix and use a generic linear solver such as linalg::matlinsolve:
T := linalg::toeplitz(4, 4, [1, 0, 1])
linalg::matlinsolve(T, matrix([y1, y2, y3, y4]))
We solve a Toeplitz system over the field ℤ_{7} (the integers modulo 7) represented by the domain Dom::IntegerMod(7):
R := Dom::IntegerMod(7): t := [R(5), R(3), R(2), R(5), R(1)]: y := [R(1), R(2), R(3)]: linalg::toeplitzSolve(t, y)
delete R, t, y:
t |
A vector or a list with 2 k + 1 elements. (A vector is a (2 k + 1)×1 or a 1 ×(2 k + 1) matrix of category Cat::Matrix). |
y |
A vector or a list with n elements |
Vector or list with n elements of the same domain type as the elements of y. FAIL is returned if the algorithm does not succeed in finding a solution.