Abstract
It takes of the order of N3 operations to solve a set of N linear equations in N unknowns or to invert the corresponding coefficient matrix. When the underlying physical problem has some time- or shift-invariance properties, the coefficient matrix is of Toeplitz (or difference or convolution) type and it is known that it can be inverted with O(N2) operations. However non-Toeplitz matrices often arise even in problems with some underlying time-invariance, e.g., as inverses or products or sums of products of possibly rectangular Toeplitz matrices. These non-Toeplitz matrices should be invertible with a complexity between O(N2) and O(N3). In this paper we provide some content for this feeling by introducing the concept of displacement ranks, which serve as a measure of how 'close' to Toeplitz a given matrix is.
Original language | English (US) |
---|---|
Pages (from-to) | 395-407 |
Number of pages | 13 |
Journal | Journal of Mathematical Analysis and Applications |
Volume | 68 |
Issue number | 2 |
DOIs | |
State | Published - Apr 1979 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Analysis
- Applied Mathematics