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
.
Note: Note that the Levinson algorithm requires that all principal minors
are nonsingular. 
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 

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.