Publication

Structure and arithmetic complexity of products and inverses of Toeplitz matrices

Martin Vetterli
1991
Journal Articles

Abstract

We derive a formula for the product of two Toeplitz matrices that is similar to the Trench formula for the inverse of a Toeplitz matrix. We then derive upper and lower bounds for number of multiplications required to compute the inverse or the product of Toeplitz matrices and consider several special cases, e.g., symmetry, as well. The lower bounds for the general cases are in agreement with earlier results, but the specialized lower bounds and all the upper bounds are new. Both upper and lower bounds are O(n2) and differ only in lower order terms.

Official source

https://infoscience.epfl.ch/entities/publication/338dcd18-bfb9-4193-b6fd-6e0b60c6bd66

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Martin Vetterli
1991
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/338dcd18-bfb9-4193-b6fd-6e0b60c6bd66

About this result

Related concepts (32)

Toeplitz matrix

In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix: Any matrix of the form is a Toeplitz matrix. If the element of is denoted then we have A Toeplitz matrix is not necessarily square. A matrix equation of the form is called a Toeplitz system if is a Toeplitz matrix. If is an Toeplitz matrix, then the system has at-most only unique values, rather than .

Block matrix

In mathematics, a block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix with a collection of horizontal and vertical lines, which break it up, or partition it, into a collection of smaller matrices. Any matrix may be interpreted as a block matrix in one or more ways, with each interpretation defined by how its rows and columns are partitioned.

Inverse element

In mathematics, the concept of an inverse element generalises the concepts of opposite (−x) and reciprocal (1/x) of numbers. Given an operation denoted here ∗, and an identity element denoted e, if x ∗ y = e, one says that x is a left inverse of y, and that y is a right inverse of x. (An identity element is an element such that x * e = x and e * y = y for all x and y for which the left-hand sides are defined.

Related publications (4)

Structure and arithmetic complexity of products and inverses of Toeplitz matrices

Chat with Graph Search

A global collaborative accounting network to calculate the resource use of products and services

A Class Of Mean Field Interaction Models for Computer and Communication Systems

Cluster synchronization in three-dimensional lattices of diffusively coupled oscillators