A fast algorithm for block Toeplitz systems with tensor structure
type: Item
instance of: scholarly article
title: A fast algorithm for block Toeplitz systems with tensor structure
zbMATH Open document ID: 0842.65017
DOI: 10.1016/0096-3003(94)00243-6
published in: Applied Mathematics and Computation
publication date: 1996-07-24T00:00:00Z
review text: 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.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 65M06
Mathematics Subject Classification ID: 35K05
Mathematics Subject Classification ID: 35R30
zbMATH DE Number: 847549
zbMATH Keywords: Hilbert matrix
zbMATH Keywords: block Toeplitz system
zbMATH Keywords: preconditioned conjugate gradient method
zbMATH Keywords: tensor product circulant preconditioner
zbMATH Keywords: fast algorithm
zbMATH Keywords: inverse heat problem
author: Xiao-Qing Jin
MaRDI profile type: Publication
full work available at URL: 0096-3003(94)00243-6
OpenAlex ID: W2060843933
cites work: Q3359644
cites work: A Proposal for Toeplitz Matrix Calculations
cites work: Q3208805
cites work: Toeplitz Equations by Conjugate Gradients with Circulant Preconditioner
cites work: An Optimal Circulant Preconditioner for Toeplitz Systems
cites work: The circulant operator in the Banach algebra of matrices
cites work: Circulant Preconditioners for Toeplitz Matrices with Positive continuous Generating Functions
cites work: A Family of Block Preconditioners for Block Systems
cites work: Numerical solutions for the inverse heat problems in \({\mathbb{R}{}}^ N\)
cites work: Circulant and Skewcirculant Matrices for Solving Toeplitz Matrix Problems
cites work: Partial differential equations. 4th ed
cites work: Numerical Methods Based on Whittaker Cardinal, or Sinc Functions
description: scientific article; zbMATH DE number 847549