A note on an SOR-like method for augmented systems

Golub et al. (2001, BIT, 41, 71–85) gave a generalizedsuccessive over-relaxation method for the augmented systems.In this paper, the connection between the SOR-like method andthe preconditioned conjugate gradient (PCG) method for the augmentedsystems is investigated. It is shown that the PCG method isat least as accurate (fast) as the SOR-like method. Numericalexamples demonstrate that the PCG method is much faster thanthe SOR-like method.     

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

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

Fastiterative methods for least squares estimations

Least squares estimations have been used extensively in many applications, e.g. system identification and signal prediction. When the stochastic process is stationary, the least squares estimators can be found by solving a Toeplitz or near-Toeplitz matrix system depending on the knowledge of the data statistics. In this paper, we employ the preconditioned conjugate gradient method with circulant preconditioners to solve such systems. Our proposed circulant preconditioners are derived from the spectral property of the given stationary process. In the case where the spectral density functions() of the process is known, we prove that ifs() is a positive continuous function, then the spectrum of the preconditioned system will be clustered around 1 and the method converges superlinearly. However, if the statistics of the process is unknown, then we prove that with probability 1, the spectrum of the preconditioned system is still clustered around 1 provided that large data samples are taken. For finite impulse response (FIR) system identification problems, our numerical results show that annth order least squares estimator can usually be obtained inO(n logn) operations whenO(n) data samples are used. Finally, we remark that our algorithm can be modified to suit the applications of recursive least squares computations with the proper use of sliding window method arising in signal processing applications.Research supported in part by HKRGC grant no. 221600070, ONR contract no. N00014-90-J-1695 and DOE grant no. DE-FG03-87ER25037.     

预优矩阵及其构造技术

为达到预处理共轭梯度法(PCG)提高收敛速度，克服数值不稳定性目的，给出了构造预优矩阵的条件，并构造了三个典型的预优矩阵。它们是不完全Cholesky因子预优矩阵，对角预优矩阵和利用SSOR法导出的预优矩阵，且在PCG中是应用效果很好的预优矩阵。     

Application of a line implicit method to fully coupled system of equations for turbulent flow problems

For unstructured finite volume methods, we present a line implicit Runge–Kutta method applied as smoother in an agglomerated multigrid algorithm to significantly improve the reliability and convergence rate to approximate steady-state solutions of the Reynolds-averaged Navier–Stokes equations. To describe turbulence, we consider a one-equation Spalart–Allmaras turbulence model. The line implicit Runge–Kutta method extends a basic explicit Runge–Kutta method by a preconditioner given by an approximate derivative of the residual function. The approximate derivative is only constructed along predetermined lines which resolve anisotropies in the given grid. Therefore, the method is a canonical generalisation of point implicit methods. Numerical examples demonstrate the improvements of the line implicit Runge–Kutta when compared with explicit Runge–Kutta methods accelerated with local time stepping.     

Generalization of Strang's Preconditioner with Applications to Toeplitz Least Squares Problems

In this paper, we propose a method to generalize Strang's circulant preconditioner for arbitrary n-by-n matrices A_n. The th column of our circulant preconditioner Sn is equal to the th column of the given matrix A_n. Thus if A_n is a square Toeplitz matrix, then Sn is just the Strang circulant preconditioner. When Sn is not Hermitian, our circulant preconditioner can be defined as . This construction is similar to the forward-backward projection method used in constructing preconditioners for tomographic inversion problems in medical imaging. We show that if the matrix A_n has decaying coefficients away from the main diagonal, then is a good preconditioner for An. Comparisons of our preconditioner with other circulant-based preconditioners are carried out for some 1-D Toeplitz least squares problems: min ∥ b - Ax∥₂. Preliminary numerical results show that our preconditioner performs quite well, in comparison to other circulant preconditioners. Promising test results are also reported for a 2-D deconvolution problem arising in ground-based atmospheric imaging.     

一种求解三维热辐射输运方程的整体预处理迭代方法及并行计算

为三维灰体热辐射输运方程的隐式离散纵标方法发展一个整体预处理迭代方法并研制并行程序.该方法采用组装线性代数方程组策略,同时求出所有离散方向上的辐射强度.借助预处理的Krylov子空间迭代法,避免复杂网格上扫描算法可能遇到的死锁问题,能够提高健壮性和计算效率.空间离散上采用一阶迎风有限体积格式.数值实验测试变形六面体网格...     

On block preconditioners for saddle point problems with singular or indefinite (1, 1) block

We discuss a class of preconditioning methods for the iterative solution of symmetric algebraic saddle point problems, where the (1, 1) block matrix may be indefinite or singular. Such problems may arise, e.g. from discrete approximations of certain partial differential equations, such as the Maxwell time harmonic equations. We prove that, under mild assumptions on the underlying problem, a class of block preconditioners (including block diagonal, triangular and symmetric indefinite preconditioners) can be chosen in a way which guarantees that the convergence rate of the preconditioned conjugate residuals method is independent of the discretization mesh parameter. We provide examples of such preconditioners that do not require additional scaling. Copyright © 2010 John Wiley & Sons, Ltd.     

Analysis of Natural Convection During Solidification of a Pure Metal

A numerical study of solidification of gallium in a closed cavity is presented and the influence of natural convection on phase change is investigated.

The mathematical formulation is based on the enthalpy-porosity method, while the equations are discretized on a fixed grid by means of a finite volume technique. Advancing in time is obtained using the SIMPLE algorithm, while the solution of the elliptic equation for pressure correction is obtained by means of a preconditioned BI-CGStab method.

As a test case a square cavity with Ra ranging from 4.68 × 10³ to 9.36 × 10⁵ is adopted. Results will be presented in terms of streamlines, isotherms, solid-liquid interface position and Nu and compared, when possible with available data.     

On the solution of indefinite systems arising in nonlinear programming problems

This work is concerned with the convergence properties and the numerical analysis of the preconditioned conjugate gradient (PCG) method applied to the solution of indefinite linear systems arising in nonlinear optimization. Our approach is based on the choice of quasidefinite preconditioners and of a suitable factorization routine. Some theoretical and numerical results about these preconditioners are obtained. Furthermore, we show the behaviour of the PCG method for different formulations of the indefinite system and we compare the effectiveness of the proposed variants. Copyright © 2007 John Wiley & Sons, Ltd.