On preconditioned iterative methods for solving (A−λB)x=0

In this paper a preconditioned iterative method suitable for the solution of the generalised eigenvalue problem is presented. The proposed method in which no change in the structure of the original matrices occurs is suitable for the determination of the extreme eigenvalues and their corresponding eigenvectors of large sparse matrices derived from finite element/difference discretisation of partial differential equations. The new method when coupled with the conjugate gradient algorithm yields a powerful algorithm for this class of problems.     

Extreme eigenvalues of large sparse matrices by Rayleigh quotient and modified conjugate gradients

The extreme eigenvalues of a symmetric positive-definite matrix A may be obtained as the solution to an extremum problem, namely through the minimization or the maximization of the Rayleigh quotient by the conjugate gradients. While this procedure works well for the upper bound λ₁, its rate of convergence proves too slow for the lower bound λ_N. For large sparse matrices the iteration can be extraordinarily accelerated with the aid of a preconditioning matrix derived from the incomplete Cholesky factorization of A. The new scheme has been applied to determine the smallest eigenvalue of finite element matrices of size N, with N between 150 and 2220 taken from the engineering practice. The results show that a good estimate of λ_N is achieved after very few iterations and that the Rayleigh quotient/modified conjugate gradient technique is more than one order of magnitude faster than the reverse power/conjugate gradient algorithm recently developed by the authors for the same problem.     

大规模有限元刚度矩阵存储及其并行求解算法

本文提出一种将有限元单元刚度矩阵直接集成压缩格式的总体刚度矩阵的方法,并针对其线性系统设计了预处理的重启动GMRES(m)并行求解器.集成方法使用了一个“关联结点”的数据结构,它用来记录网格中节点的关联信息,作为集成过程的中间媒介.这种方法能减少大量的存储空间,简单且高效.求解器分别使用Jacobi和稀疏近似逆(SPAI)预条件子.二维和三维弹性力学问题的数值试验表明,在二维情形下,SPAI预条件子具有很好的加速收敛效果和并行效率;在三维情形下,Jacobi预条件子更能减少迭代收敛时间.     

On parameterized matrix splitting preconditioner for the saddle point problems

In this paper, we present a parameterized matrix splitting (PMS) preconditioner for the large sparse saddle point problems. The preconditioner is based on a parameterized splitting of the saddle point matrix, resulting in a fixed-point iteration. The convergence theorem of the new iteration method for solving large sparse saddle point problems is proposed by giving the restrictions imposed on the parameter. Based on the idea of the parameterized splitting, we further propose a modified PMS preconditioner. Some useful properties of the preconditioned matrix are established. Numerical implementations show that the resulting preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as generalized minimal residual method.     

Multi space reduced basis preconditioners for parametrized Stokes equations

We introduce a two-level preconditioner for the efficient solution of large scale saddle-point linear systems arising from the finite element (FE) discretization of parametrized Stokes equations. This preconditioner extends the Multi Space Reduced Basis (MSRB) preconditioning method proposed in Dal Santo et al. (2018); it combines an approximated block (fine grid) preconditioner with a reduced basis (RB) solver which plays the role of coarse component. A sequence of RB spaces, constructed either with an enriched velocity formulation or a Petrov–Galerkin projection, is built. Each RB coarse component is defined to perform a single iteration of the iterative method at hand. The flexible GMRES (FGMRES) algorithm is employed to solve the resulting preconditioned system and targets small tolerances with a very small iteration count and in a very short time. Numerical test cases for Stokes flows in three dimensional parameter-dependent geometries are considered to assess the numerical properties of the proposed technique in different large scale computational settings.     

Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems

In this paper, we propose an efficiently preconditioned Newton method for the computation of the leftmost eigenpairs of large and sparse symmetric positive definite matrices. A sequence of preconditioners based on the BFGS update formula is proposed, for the preconditioned conjugate gradient solution of the linearized Newton system to solve Au=q(u) u, q(u) being the Rayleigh quotient. We give theoretical evidence that the sequence of preconditioned Jacobians remains close to the identity matrix if the initial preconditioned Jacobian is so. Numerical results onto matrices arising from various realistic problems with size up to one million unknowns account for the efficiency of the proposed algorithm which reveals competitive with the Jacobi–Davidson method on all the test problems.     

基于共轭梯度搜索的广义特征对追踪算法

研究广义特征对追踪算法,通过探索基于共轭梯度搜索的标准特征向量追踪算法,将其引入到广义特征对的提取.所提算法具有自适应步长机制,使不同特征搜索方向上的广义瑞利熵达到最优,并适用于提取平稳矩阵束和非平稳矩阵束的广义特征对.数值仿真中将所提算法与多个自适应广义特征向量提取算法进行了比较,实验结果验证了所提算法的有效性.     

Convergence analysis of modified PGSS methods for singular saddle-point problems

Recently, variants of shift-splitting iteration method have been proposed for solving singular saddle-point problems. However, these methods can only be proved to converge to one of the solutions of the consistent singular linear system, not knowing any further information about this solution. In this work, we consider a modified preconditioned generalized shift-splitting (MPGSS) iteration method for solving both consistent and inconsistent singular saddle-point problems. This method is proved to converge to the best least squares solution. Moreover, based on the iteration form, a preconditioner is obtained to accelerate Krylov subspace methods. Theoretical analysis shows that the preconditioned GMRES method also converges to the best least squares solution of the consistent singular saddle-point problem. In addition, numerical results are presented to show the effectiveness and robustness of the proposed iteration method and preconditioner.     

Strang-type preconditioners for solving linear systems from neutral delay differential equations

We study the solution of neutral delay differential equations (NDDEs) by using boundary value methods (BVMs). The BVMs require the solution of nonsymmetric, large and sparse linear systems. The GMRES method with Strang-type block-circulant preconditioner is proposed to solve these linear systems. We show that, if an -stable BVM is used for solving a system of NDDEs, then our preconditioner is invertible and the spectrum of the preconditioned system is clustered. It follows that, when the GMRES method is applied to the preconditioned systems, the method can converge rapidly. Numerical results are given to show that our method is effective. Received: July 2002 / Accepted: December 2002 RID="*" ID="*"The research of this author is supported by research grant No. RG024/01-02S/JXQ/FST from the University of Macau.     

Nonconforming Least-Squares Method for Elliptic Partial Differential Equations with Smooth Interfaces

In this paper a least-squares based method is proposed for elliptic interface problems in two dimensions, where the interface is smooth. The underlying method is spectral element method. The least-squares formulation is based on the minimization of a functional as defined in (4.1). The jump in the solution and its normal derivative across the interface are enforced?(in an appropriate Sobolev norm) in the functional. The solution is obtained by solving the normal equations using preconditioned conjugate gradient method. Essentially the method is nonconforming, so a block diagonal matrix is constructed as a preconditioner based on the stability estimate where each diagonal block is decoupled. A conforming solution is obtained by making a set of corrections to the nonconforming solution as in Schwab (p and h?Cp Finite Element Methods, Clarendon Press, Oxford, 1998) and an error estimate in H ¹-norm is given which shows the exponential convergence of the proposed method.     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

A new matrix splitting preconditioner for generalized saddle point problems

For generalized saddle point problems, we establish a new matrix splitting preconditioner and give the implementing process in detail. The new preconditioner is much easier to be implemented than the modified dimensional split (MDS) preconditioner. The convergence properties of the new splitting iteration method are analyzed. The eigenvalue distribution of the new preconditioned matrix is discussed and an upper bound for the degree of its minimal polynomial is derived. Finally, some numerical examples are carried out to verify the effectiveness and robustness of our preconditioner on generalized saddle point problems discretizing the incompressible Navier–Stokes equations.     

The improvements of the generalized shift-splitting preconditioners for non-singular and singular saddle point problems

ABSTRACT

To solve the saddle point problems with symmetric positive definite (1,1) parts, the improved generalized shift-splitting (IGSS) preconditioner is established in this paper, which yields the IGSS iteration method. Theoretical analysis shows that the IGSS iteration method is convergent and semi-convergent unconditionally. The choices of the iteration parameters are discussed. Moreover, some spectral properties, including the eigenvalue and eigenvector distributions of the preconditioned matrix are also investigated. Finally, numerical results are presented to verify the robustness and the efficiency of the proposed iteration method and the corresponding preconditioner for solving the non-singular and singular saddle point problems.     

GPU-accelerated preconditioned GMRES method for two-dimensional Maxwell's equations

In this study, for two-dimensional Maxwell's equations, an efficient preconditioned generalized minimum residual method on the graphics processing unit (GPUPGMRES) is proposed to obtain numerical solutions of the equations that are discretized by a multisymplectic Preissmann scheme. In our proposed GPUPGMRES, a novel sparse matrix–vector multiplication (SpMV) kernel is suggested while keeping the compressed sparse row (CSR) intact. The proposed kernel dynamically assigns different number of rows to each thread block, and accesses the CSR arrays in a fully coalesced manner. This greatly alleviates the bottleneck of many existing CSR-based algorithms. Furthermore, the vector-operation and inner-product decision trees are automatically constructed. These kernels and their corresponding optimized compute unified device architecture parameter values can be automatically selected from the decision trees for vectors of any size. In addition, using the sparse approximate inverse technique, the preconditioner equation solving falls within the scope of SpMV. Numerical results show that our proposed kernels have high parallelism. GPUPGMRES outperforms a recently proposed preconditioned GMRES method, and a preconditioned GMRES implementation in the AmgX library. Moreover, GPUPGMRES is efficient in solving the two-dimensional Maxwell's equations.     

求解对称带状广义特征值问题的扩展分治算法

提出了分布式环境下计算对称带状广义特征值问题的一种扩展分治算法,给出了特征值分割定理及其证明．算法在扩展分治的基础上,利用二分压缩结合广义Rayleigh商迭代计算广义特征对．理论分析和数值实验表明,对于窄带宽大规模的广义特征值问题,该分治算法明显优于LAPACK软件包．结合并行性好的多分法,在分布式环境下获得了很好的并行效果．     

A parallel fictitious domain multigrid preconditioner for the solution of Poisson’s equation in complex geometries

A parallel multilevel preconditioner based on domain decomposition and fictitious domain methods has been presented for the solution of the Poisson equation in complicated geometries. Rectangular blocks with matching grids on interfaces on a structured rectangular mesh have been used for the decomposition of the problem domain. Sloping sides or curved boundary surfaces are approximated using stepwise surfaces formed by the grid cells. A seven-point stencil based on the central difference scheme has been used for the discretization of the Laplacian for both interior and boundary grid points, and this results in a symmetric linear algebraic system for any type of boundary condition. The preconditioned conjugate gradient method has been used for the solution of this symmetric system. The multilevel preconditioner for the CG is based on a V-cycle multigrid applied to the Poisson equation on a fictitious domain formed by the union of the rectangular blocks used for the domain decomposition. Numerical results are presented for two typical Poisson problems in complicated geometries—one related to heat conduction, and the other one arising from the LES/DNS of incompressible turbulent flow over a packed array of spheres. These results clearly show the efficiency and robustness of the proposed approach.     

The eigenvalue problem (A − λB)x = 0 for symmetric matrices of high order

Vibrational problems of complex structures treated by the method of finite elements lead to the general eigenvalue problem $\text{(A ? λB)x = 0}$, where $\text{A}$ and $\text{B}$ are symmetric and sparse matrices of high order. The smallest eigenvalues and corresponding eigenvectors of interest are usually computed by a variant of the inverse vector iteration. Instead of this, the smallest eigenvalue can be computed as the minimum of the corresponding Rayleigh quotient for instance by the method of the coordinate relaxation of Faddejew/Faddejewa. The slow convergence of this simple algorithm can however be sped up considerably in analogy to the successive overrelaxation method by a systematic overrelaxation. Numerical experiments indicate indeed a rate of convergence of this coordinate overrelaxation as a function of the relaxation parameter which is comparable to that of the usual seccessive overrelaxation for linear equations. In comparison with known procedures for the solution of the general eigenvalue problem there result some important computational advantages with regard to the amount of work. Finally, the higher eigenvalues can be computed successively by minimizing the Rayleigh quotient of a modified eigenvalue problem based on a deflation process.     

A new preconditioner for generalized saddle point matrices with highly singular(1,1) blocks

In this paper, based on the preconditioners presented by Cao [A note on spectrum analysis of augmentation block preconditioned generalized saddle point matrices, Journal of Computational and Applied Mathematics 238(15) (2013), pp. 109–115], we introduce and study a new augmentation block preconditioners for generalized saddle point matrices whose coefficient matrices have singular (1,1) blocks. Moreover, theoretical analysis gives the eigenvalue distribution, forms of the eigenvectors and its minimal polynomial. Finally, numerical examples show that the eigenvalue distribution with presented preconditioner has the same spectral clustering with preconditioners in the literature when choosing the optimal parameters and the preconditioner in this paper and in the literature improve the convergence of BICGSTAB and GMRES iteration efficiently when they are applied to the preconditioned BICGSTAB and GMRES to solve the Stokes equation and two-dimensional time-harmonic Maxwell equations by choosing different parameters.     

Efficient Rearrangement Algorithms for Shape Optimization on Elliptic Eigenvalue Problems

In this paper, several efficient rearrangement algorithms are proposed to find the optimal shape and topology for elliptic eigenvalue problems with inhomogeneous structures. The goal is to solve minimization and maximization of the k-th eigenvalue and maximization of spectrum ratios of the second order elliptic differential operator. Physically, these problems are motivated by the frequency control based on density distribution of vibrating membranes. The methods proposed are based on Rayleigh quotient formulation of eigenvalues and rearrangement algorithms which can handle topology changes automatically. Due to the efficient rearrangement strategy, the new proposed methods are more efficient than classical level set approaches based on shape and/or topological derivatives. Numerous numerical examples are provided to demonstrate the robustness and efficiency of new approach.