块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

基于均值的Toeplitz矩阵填充的子空间算法

本文提出一种基于均值的Toeplitz矩阵填充的子空间算法.通过在左奇异向量空间中对已知元素的最小二乘逼近,形成了新的可行矩阵;并利用对角线上的均值化使得迭代后的矩阵保持Toeplitz结构,从而减少了奇异向量空间的分解时间.理论上,证明了在一定条件下该算法收敛于一个低秩的Toeplitz矩阵.通过不同已知率的矩阵填充数值实验展示了Toeplitz矩阵填充的新算法比阈值增广Lagrange乘子算法在时间上和精度上更有效.     

一类特殊矩阵方程的并行预处理变形共轭梯度算法

研究了求解一类矩阵方程AXB=C,提出了一种并行预处理变形共轭梯度法．该方法给出一种迭代法的预处理模式．首先给出的预处理矩阵是严格对角占优矩阵,构造并行迭代求解预处理矩阵方程的迭代格式,进而使用变形共轭梯度法并行求解．通过数值试验,预处理变形共轭梯度法与直接使用变形共轭梯度法相比较,该算法不仅有效提高了收敛速度,而且具有很高的并行性．     

一类Toeplitz线性代数方程组的预处理GMRES方法

本文研究一类来源于分数阶特征值问题的Toeplitz线性代数方程组的求解.构造Strang循环矩阵作为预处理矩阵来求解该Toeplitz线性代数方程组,分析了预处理后系数矩阵的特征值性质.提出求解该线性代数方程组的预处理广义极小残量法（PGMRES）,并给出该算法的计算量.数值算例表明了该方法的有效性.     

求解大规模Hamilton矩阵特征问题的辛Lanczos算法的误差分析

对求解大规模稀疏Hamilton矩阵特征问题的辛Lanczos算法给出了舍入误差分析.分析表明辛Lanczos算法在无中断时,保Hamilton结构的限制没有破坏非对称Lanczos算法的本质特性.本文还讨论了辛Lanczos算法计算出的辛Lanczos向量的J一正交性的损失与Ritz值收敛的关系.结论正如所料,当某些Ritz值开始收敛时.计算出的辛Lanczos向量的J-正交性损失是必然的.以上结果对辛Lanczos算法的改进具有理论指导意义.     

Toeplitz型矩阵的逆矩阵的快速三角分解算法

针对有关“型”矩阵的三角分解问题 ,提出了一种 Toeplitz型矩阵的逆矩阵的快速三角分解算法 .首先假设给定 n阶非奇异矩阵 A,利用一组线性方程组的解 ,得到 A- 1的一个递推关系式 ,进而利用该关系式得到 A- 1的一种三角分解表达式 ,然后从 Toeplitz型矩阵的特殊结构出发 ,利用上述定理的结论 ,给出了Toeplitz型矩阵的逆矩阵的一种快速三角分解算法 ,算法所需运算量为 O( mn2 ) .最后 ,数值计算表明该算法的可靠性 .     

三对角与五对角Toeplitz矩阵求逆的算法

提出了一种求三对角与五对角Toeplitz矩阵逆的快速算法,其思想为先将Toeplitz矩阵扩展为循环矩阵,再快速求循环矩阵的逆,进而运用恰当矩阵分块求原Toeplitz矩阵的逆的算法.算法稳定性较好且复杂度较低.数值例子显示了算法的有效性和稳定性,并指出了算法的适用范围.     

两个Toeplitz矩阵相乘的一种快速算法

通过将两个Toeplitz矩阵拼凑成两个高阶上下三角形Toeplitz矩阵,构造出一种两个Toeplitz矩阵相乘的快速算法,其乘法运算次数为3n2-3n+1.     

实对称正定Toeplitz矩阵的带位移的Sine预处理子

本文研究了求解实对称正定Toeplitz线性方程组的预处理共轭梯度法.基于实对称Toeplitz矩阵都有一个三角变换分裂(TTS)的事实,我们提出了带位移的Sine预处理子TS,分析了预处理矩阵的谱性质,并讨论了每步迭代的计算复杂度.数值实验表明该预处理子比T.Chan预处理子~([2])更有效.     

几乎各向同性的高维空间分数阶扩散方程的分块快速正则Hermite分裂预处理方法

一类空间分数阶扩散方程经过有限差分离散后所得到的离散线性方程组的系数矩阵是两个对角矩阵与Toeplitz型矩阵的乘积之和.在本文中,对于几乎各向同性的二维或三维空间分数阶扩散方程的离散线性方程组,采用预处理Krylov子空间迭代方法,我们利用其系数矩阵的特殊结构和具体性质构造了一类分块快速正则Hermite分裂预处理子.通过理论分析,我们证明了所对应的预处理矩阵的特征值大部分都聚集于1的附近.数值实验也表明,这类分块快速正则Hermite分裂预处理子可以明显地加快广义极小残量(GMRES)方法和稳定化的双共轭梯度(BiCGSTAB)方法等Krylov子空间迭代方法的收敛速度.     

Preconditioned Lanczos method for generalized Toeplitz eigenvalue problems

We employ the sine transform-based preconditioner to precondition the shifted Toeplitz matrix _An−ρ_Bn$A_n-\rho B_n$ involved in the Lanczos method to compute the minimum eigenvalue of the generalized symmetric Toeplitz eigenvalue problem _Anx=λ_Bnx$A_{n}x=\lambda B_{n}x$, where _An$A_n$ and _Bn$B_n$ are given matrices of suitable sizes. The sine transform-based preconditioner can improve the spectral distribution of the shifted Toeplitz matrix and, hence, can speed up the convergence rate of the preconditioned Lanczos method. The sine transform-based preconditioner can be implemented efficiently by the fast transform algorithm. A convergence analysis shows that the preconditioned Lanczos method converges sufficiently fast, and numerical results show that this method is highly effective for a large matrix.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

A SHIFT-SPLITTING PRECONDITIONER FOR NON-HERMITIAN POSITIVE DEFINITE MATRICES

A shift splitting concept is introduced and, correspondingly, a shift-splitting iteration scheme and a shift-splitting preconditioner are presented, for solving the large sparse system of linear equations of which the coefficient matrix is an ill-conditioned non-Hermitian positive definite matrix. The convergence property of the shift-splitting iteration method and the eigenvalue distribution of the shift-splitting preconditioned matrix are discussed in depth, and the best possible choice of the shift is investigated in detail. Numerical computations show that the shift-splitting preconditioner can induce accurate, robust and effective preconditioned Krylov subspace iteration methods for solving the large sparse non-Hermitian positive definite systems of linear equations.     

THE SINE TRANSFORM OPERATOR IN THE BANACH SPACE OF SYMMETRIC MATRICES AND ITS APPLICATION IN IMAGE RESTORATION

In this paper, we study an operator s which maps every n-by-n symmetric matrix A, to a matrix s(A_n) that minimizes || B_n-A_n || F over the set of all matrices B_n, that can be diagonalized by the sine transform. The matrix s(A_n), called the optimal sine transform preconditioner, is defined for any n-by-n symmetric matrices A_n. The cost of constructing s(A_n) is the same as that of optimal circulant preconditioner c(A_n) which is defined in [8], The s(A_n) has been proved in [6] to be a good preconditioner in solving symmetric Toeplitz systems with the preconditioned conjugate gradient (PCG) method. In this paper, we discuss the algebraic and geometric properties of the operator s, and compute its operator norms in Banach spaces of symmetric matrices. Some numerical tests and an application in image restoration are also given.     

Toeplitz预条件子的统一构造与性能分析

１．引言考虑线性方程组ＴＮｘ＝ｂ（１．１）其中ＴＮ＝（ｔｉ,ｊ）是ＮｘＮ对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵,即ｔｉ,ｊ＝ｔ｜ｉ－ｊ｜（ｉ,ｊ＝０,１,...,Ｎ－１）且ＴＮ的所有特征值均为正数,并表为ＴＮ：＝Ｔ（ｔ。,ｔｉ,...,ｔＮ－１）．如果我们用预条件子共轭梯度法（ＰＣＧ）求解方程组（１．１）,最关健的任务是构造出高效的预条件子．而预条件子最自然的选择似乎其逆矩阵易求且构成矩阵ＴＮ的某种最优逼近．由于循环矩阵ＣＮ的逆矩阵ＣＲ'仍为循环矩阵,因此ＣＮ和ＣＨ'与向量的乘积可通ｉｓ速Ｆｏｕｒｉｅｒ…     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Block ILU Preconditioners for a Nonsymmetric Block-Tridiagonal M-Matrix

We propose block ILU (incomplete LU) factorization preconditioners for a nonsymmetric block-tridiagonal M-matrix whose computation can be done in parallel based on matrix blocks. Some theoretical properties for these block ILU factorization preconditioners are studied and then we describe how to construct them effectively for a special type of matrix. We also discuss a parallelization of the preconditioner solver step used in nonstationary iterative methods with the block ILU preconditioners. Numerical results of the right preconditioned BiCGSTAB method using the block ILU preconditioners are compared with those of the right preconditioned BiCGSTAB using a standard ILU factorization preconditioner to see how effective the block ILU preconditioners are.     

A geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.