Documentation Center

  • Trial Software
  • Product Updates

linalg::toeplitzSolve

Solve a linear Toeplitz system

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

linalg::toeplitzSolve(t, y)

Description

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:   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.

Examples

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:

Parameters

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

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.

See Also

MuPAD Functions

Was this topic helpful?