Solving A Toeplitz System
A matrix equation of the form
is called a Toeplitz system if A is a Toeplitz matrix. If A is an Toeplitz matrix, then the system has only 2n−1 degrees of freedom, rather than n2. We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case.
Toeplitz systems can be solved by the Levinson algorithm in Θ(n2) time. Variants of this algorithm have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems). The algorithm can also be used to find the determinant of a Toeplitz matrix in O(n2) time.
A Toeplitz matrix can also be decomposed (i.e. factored) in O(n2) time. The Bareiss algorithm for an LU decomposition is stable. An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.
Algorithms that are asymptotically faster than those of Bareiss and Levinson have been described in the literature.
Read more about this topic: Toeplitz Matrix
Famous quotes containing the words solving a, solving and/or system:
“There are horrible people who, instead of solving a problem, tangle it up and make it harder to solve for anyone who wants to deal with it. Whoever does not know how to hit the nail on the head should be asked not to hit it at all.”
—Friedrich Nietzsche (1844–1900)
“Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
—Ruth Mompati (b. 1925)
“The twentieth-century artist who uses symbols is alienated because the system of symbols is a private one. After you have dealt with the symbols you are still private, you are still lonely, because you are not sure anyone will understand it except yourself. The ransom of privacy is that you are alone.”
—Louise Bourgeois (b. 1911)