This is machine translation

Translated by Microsoft
Mouseover text to see original. Click the button below to return to the English verison of the page.

Note: This page has been translated by MathWorks. Please click here
To view all translated materals including this page, select Japan from the country navigator on the bottom of this page.


Solve a linear Toeplitz system

MuPAD® notebooks are not recommended. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.


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 = [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.


Note that the Levinson algorithm requires that all principal minors

are non-singular.

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.


Example 1

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:

Example 2

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]))

Example 3

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

Return Values

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.

Was this topic helpful?