Optimal and Superoptimal Circulant Preconditioners
Optimal and Superoptimal Circulant Preconditioners
复制标题
DOI：
10.1137/0613030
复制
发表时间：
1992-04
期刊：
影响因子：
--
通讯作者：
E. Tyrtyshnikov
中科院分区：
文献类型：
--
作者：
E. Tyrtyshnikov
在用迭代法求解矩阵为A的线性代数方程组时，经常要用到预条件子C。研究了两类预条件子：最优预条件子和超优预条件子，前者使$C-AF最小，后者使$I-C ^{ - 1} AF最小.证明了它们都继承了A.本文提出了一种寻找超优预条件子的快速算法，对于任意n阶A，其运算时间为O（n^2 \log_2 n）$，而对于Toeplitz或双Toeplitz A，其运算时间仅为O（n^2 \log_2 n）$.
While applying iterative methods to solve a linear algebraic system with matrix A, one often uses some preconditioner C. Two kinds of preconditioners are investigated: the “optimal” one, which minimizes $\| C - A \|_F$, and the “superoptimal” one, which minimizes $\| I - C^{ - 1} A \|_F $. It is proved that both inherit nonsingularity and positive-definiteness from A. Fast algorithms for finding superoptimal preconditioners are suggested that take $O(n^2 \log _2 n)$ operations in case of arbitrary A of order n, and only $O(n\log _2 n)$ operations in case of Toeplitz or doubly Toeplitz A.