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)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)
“We recognize caste in dogs because we rank ourselves by the familiar dog system, a ladderlike social arrangement wherein one individual outranks all others, the next outranks all but the first, and so on down the hierarchy. But the cat system is more like a wheel, with a high-ranking cat at the hub and the others arranged around the rim, all reluctantly acknowledging the superiority of the despot but not necessarily measuring themselves against one another.”
—Elizabeth Marshall Thomas. “Strong and Sensitive Cats,” Atlantic Monthly (July 1994)