A fast algorithm for block Toeplitz systems with tensor structure
Consider a block Toeplitz system \(Tx= b\) with \(T= T_1\otimes T_2\otimes\cdots\otimes T_m\), where the \(T_i\) are \(n\times n\) Toeplitz matrices. To solve this system of size \(n^m\) by the preconditioned conjugate gradient method, a tensor product circulant preconditioner \(C= C_1\otimes C_2\otimes\cdots\otimes C_m\) is used, where \(C_i\) is the Chan preconditioner for \(T_i\). This means that \(C_i\) minimizes the Frobenius distance to \(T_i\) among the circulant matrices. To solve the preconditioned system, a sequence of \(m\) simplified systems of the form \((I_n\otimes\cdots\otimes I_n\otimes C^{-1}_k T_k\otimes I_n\otimes\cdots \otimes I_n) y_{k- 1}= y_k\) have to be solved. This can be done in \(O(mn^m\log n)\) operations, which is a fast algorithm. As an application of this kind of systems, an inverse heat problem in \(\mathbb{R}^m\) is described. No numerical results are included.
- A Family of Block Preconditioners for Block Systems
- A Proposal for Toeplitz Matrix Calculations
- An Optimal Circulant Preconditioner for Toeplitz Systems
- Circulant and Skewcirculant Matrices for Solving Toeplitz Matrix Problems
- Circulant Preconditioners for Toeplitz Matrices with Positive continuous Generating Functions
- scientific article; zbMATH DE number 3650737 (Why is no real title available?)
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- Numerical Methods Based on Whittaker Cardinal, or Sinc Functions
- Numerical solutions for the inverse heat problems in \({\mathbb{R}{}}^ N\)
- Partial differential equations. 4th ed
- The circulant operator in the Banach algebra of matrices
- Toeplitz Equations by Conjugate Gradients with Circulant Preconditioner
This page was built for publication: A fast algorithm for block Toeplitz systems with tensor structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908238)
