Shifted Kronecker Product Systems

A fast method for solving a linear system of the form $(A^{(p)} \otimes \cdots \otimes A^{(1)} - \lambda I) x = b$ is given where each $A^{(i)}$ is an $n_i$-by-$n_i$ matrix. The first step is to convert the problem to triangular form $(T^{(p)} \otimes \cdots \otimes T^{(1)} - \lambda I) y = c$ by co...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 2007-01, Vol.29 (1), p.184-198
Main Authors: Moravitz Martin, Carla D., Van Loan, Charles F.
Format: Article
Language:English
Subjects:
Applied mathematics
Control theory
Decomposition
Fourier transforms
Linear algebra
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A fast method for solving a linear system of the form $(A^{(p)} \otimes \cdots \otimes A^{(1)} - \lambda I) x = b$ is given where each $A^{(i)}$ is an $n_i$-by-$n_i$ matrix. The first step is to convert the problem to triangular form $(T^{(p)} \otimes \cdots \otimes T^{(1)} - \lambda I) y = c$ by computing the (complex) Schur decompositions of the $A^{(i)}$. This is followed by a recursive back-substitution process that fully exploits the Kronecker structure and requires just $O(N(n_1 + \cdots + n_p))$ flops where $N = n_1 \cdots n_p$. A similar method is employed when the real Schur decomposition is used to convert each $A^{(i)}$ to quasi-triangular form. The numerical properties of these new methods are the same as if we explicitly formed $(T^{(p)} \otimes \cdots \otimes T^{(1)}- \lambda I)$ and used conventional back-substitution to solve for $y$.
ISSN:0895-4798
1095-7162
DOI:10.1137/050631707