Solve a linear Toeplitz system
This functionality does not run in MATLAB.
linalg::toeplitzSolve(t, y) returns the solution of the linear Toeplitz system with i = 1, …, n.
linalg::toeplitzSolve(t, y) with t = [tk, …, t0, …, t- k] and y = [y1, …, yn] solves the n×n Toeplitz system
with 2 k + 1 bands.
linalg::toeplitzSolve implements the Levinson algorithm. It uses O(n2) 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:
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).
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.