On relaxed nested factorization and combination preconditioning

The efficient solution of block tridiagonal linear systems arising from the discretization of convection–diffusion problem is considered in this paper. Starting with the classical nested factorization, we propose a relaxed nested factorization preconditioner. Then, several combination preconditioners are developed based on relaxed nested factorization and a tangential filtering preconditioner. Influence of the relaxation parameter is numerically studied, the results indicate that the optimal relaxation parameter should be close to but less than 1. The number of iteration counts exhibit an extremely sensitive behaviour. This phenomena resembles the behaviour of relaxed ILU preconditioner. For symmetric positive-definite coefficient matrix, we also show that the proposed combination preconditioner is convergent. Finally, numerous test cases are carried out with both additive and multiplicative combinations to verify the robustness of the proposed preconditioners.     

An approach for structural static reanalysis with unchanged number of degrees of freedom

This paper presents an approach for structural static reanalysis with unchanged number of degrees of freedom. Preconditioned conjugate gradient method is employed, and a new preconditioner is constructed by updating the Cholesky factorization of the initial stiffness matrix with little cost. The proposed method preserves the ease of implementation and significantly improves the quality of the results. In particular, the accuracy of the approximate solutions can adaptively be monitored. Numerical examples show that the condition number of preconditioned system using the new preconditioner is much smaller than that using the initial stiffness matrix as the preconditioner. Therefore, the fast convergence and accurate results can be obtained by the proposed approach.     

Application of the incomplete Cholesky factorization preconditioned Krylov subspace method to the vector finite element method for 3-D electromagnetic scattering problems

The incomplete Cholesky (IC) factorization preconditioning technique is applied to the Krylov subspace methods for solving large systems of linear equations resulted from the use of edge-based finite element method (FEM). The construction of the preconditioner is based on the fact that the coefficient matrix is represented in an upper triangular compressed sparse row (CSR) form. An efficient implementation of the IC factorization is described in detail for complex symmetric matrices. With some ordering schemes our IC algorithm can greatly reduce the memory requirement as well as the iteration numbers. Numerical tests on harmonic analysis for plane wave scattering from a metallic plate and a metallic sphere coated by a lossy dielectric layer show the efficiency of this method.     

MultiGrid Preconditioners for Mixed Finite Element Methods of the Vector Laplacian

Due to the indefiniteness and poor spectral properties, the discretized linear algebraic system of the vector Laplacian by mixed finite element methods is hard to solve. A block diagonal preconditioner has been developed and shown to be an effective preconditioner by Arnold et al. (Acta Numer 15:1–155, 2006). The purpose of this paper is to propose alternative and effective block diagonal and approximate block factorization preconditioners for solving these saddle point systems. A variable V-cycle multigrid method with the standard point-wise Gauss–Seidel smoother is proved to be a good preconditioner for the discrete vector Laplacian operator. The major benefit of our approach is that the point-wise Gauss–Seidel smoother is more algebraic and can be easily implemented as a black-box smoother. This multigrid solver will be further used to build preconditioners for the saddle point systems of the vector Laplacian. Furthermore it is shown that Maxwell’s equations with the divergent free constraint can be decoupled into one vector Laplacian and one scalar Laplacian equation.     

Fully iterative ILU preconditioning of the unsteady Navier–Stokes equations for GPGPU

In this work we investigate the numerical difficulties that arise in optimizing the efficiency of Newtonian fluids simulations on a massively parallel computing hardware like a GPU. In particular, we will concentrate on the resulting algebraic problem. We will present an approximate, fully-iterative, ILU preconditioner and we will show that this solution is very efficient on a GPU if compared with an intrinsic massively parallel preconditioner like the diagonal preconditioner, which indeed goes faster than more robust techniques, like ILU, despite their strong decrease in the number of iterations. We refer to GMRES as the iterative scheme used to solve the linear system. In particular, we will deal with the solution of incompressible flows with variable density and we will investigate the interplay between Reynolds and Atwood numbers. We will show that the numerical simulation at medium–high Reynolds numbers produces linear systems whose matrices can be reasonably preconditioned with the diagonal preconditioner, while at low Reynolds numbers the higher viscosity of the fluid makes the diagonal preconditioner ineffective in the solution time requested from GMRES and, decreasing the Reynolds number, unable to let GMRES converge at all. In this situation, we will show how an adequate iterative approach to the parallel solution of the triangular systems that result from the ILU preconditioning, turns out to be robust and efficient. We will show numerical results for variable-density fluids, discretized with the scheme described in Calgaro et al. (2008), in classical benchmarks and, in particular, in the well-known Rayleigh–Taylor instability.     

Accuracy of preconditioned CG-type methods for least squares problems

The conjugate gradient method with IMGS, an incomplete modified version of Gram-Schmidt orthogonalization to obtain an incomplete orthogonal factorization preconditioner, applied to the normal equations (PCGLS) is often used as the basic iterative method to solve the linear least squares problems. In this paper, a detailed analysis is given for understanding the effect of rounding errors on IMGS and determining the accuracy of computed solutions of PCGLS with IMGS for linear least squares problems in finite precision. It is shown that for a consistent system, the difference between the true residuals and the updated approximate residual vectors generated depends on the machine precision ε, on the maximum growth in norm of the iterates over their initial values, the norm of the true solution, and the condition number of R which is affected by the drop set in incomplete Gram-Schmidt factorization. Similar results are obtained for the difference between the true and computed solution for inconsistent systems. Numerical tests are carried out to confirm the theoretical conclusions.     

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.     

Inherited LU factorization for solving fuzzy system of linear equations

In this paper, we use the inherited LU factorization for solving the fuzzy linear system of equations. Inherited LU factorization is a type of LU factorization which is very faster and simpler than the traditional LU factorization. In this case, we prove some theorems to introduce the conditions that the inherited LU factorization exists for the coefficient matrix of fuzzy linear system. The examples illustrate that the proposed method can be used in order to find the solution of a fuzzy linear system simply.     

Approximate polynomial preconditionings applied to biharmonic equations

Applying a finite difference approximation to a biharmonic equation results in a very ill conditioned system of equations. This paper examines the conjugate gradient method used with polynomial preconditioning techniques for solving such linear systems. A new approach using an approximate polynomial preconditioner is described. The preconditioner is constructed from a series approximation based on the Laplacian finite difference matrix. A particularly attractive feature of this approach is that the Laplacian matrix consists of far fewer non-zero entries than the biharmonic finite difference matrix. Moreover, analytical estimates and computational results show that this preconditioner is more effective (in terms of the rate of convergence and the computational work required per iteration) than the polynomial preconditioner based on the original biharmonic matrix operator. The conjugate gradient algorithm and the preconditioning step can be efficiently implemented on a vector super-computer such as the CDC CYBER 205.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada Grant U0375; and in part by NASA (funded under the Space Act Agreement C99066G) while the author was visiting ICOMP, NASA Lewis Research Center.The work of this author was supported by an Izaak Walton Killam Memorial Scholarship.     

A reduced unconstrained system for the cloth dynamics solver

Modern direct solvers have been more and more widely used by computer graphics community for solving sparse linear systems, such as those that arise in cloth simulation. However, external constraints usually prevent a direct method from being used for cloth simulation due to the singularity of the constrained system. This paper makes two major contributions towards the re-introduction of direct methods for cloth dynamics solvers. The first one is an approach which eliminates all the constrained variables from the system so that we obtain a reduced, nonsingular and unconstrained system. As alternatives to the well-known MPCG algorithm, not only the original, unmodified PCG method, but also any direct method can be used to solve the reduced system at a lower cost. Our second contribution is a novel direct-iterative scheme applied for the reduced system, which is basically the conjugate gradient method using a special preconditioner. Specifically, we use the stiff part of the coefficient matrix, which we call the matrix core, as the preconditioner for the PCG. The inverse of this preconditioner is computed by any eligible direct solver. The direct-iterative method has proved to be more efficient than both direct and iterative methods. Our experiments show a factor of two speedup over direct methods when stiff springs are used, even greater improvements over the MPCG iterative method.     

Efficient Preconditioning of <Emphasis Type="Italic">hp</Emphasis>-FEM Matrices by Hierarchical Low-Rank Approximations

We introduce a preconditioner based on a hierarchical low-rank compression scheme of Schur complements. The construction is inspired by standard nested dissection, and relies on the assumption that the Schur complements can be approximated, to high precision, by Hierarchically-Semi-Separable matrices. We build the preconditioner as an approximate \(LDM^t\) factorization of a given matrix A, and no knowledge of A in assembled form is required by the construction. The \(LDM^t\) factorization is amenable to fast inversion, and the action of the inverse can be determined fast as well. We investigate the behavior of the preconditioner in the context of DG finite element approximations of elliptic and hyperbolic problems, with respect to both the mesh size and the order of approximation.     

A scaled thickness conditioning for solid- and solid-shell discretizations of thin-walled structures

The numerical discretization of thin shell structures yields ill-conditioned stiffness matrices due to an inherent large eigenvalue spectrum. Finite element parametrization that depends on shell thickness, like relative displacement shells, solid shells and other solid finite elements even add to the ill-conditioning by introducing high eigenmodes.To overcome this numerical issue we present a scaled thickness conditioning (STC) approach, a mechanically motivated preconditioner for thin-walled structures discretized with continuum based element formulations. The proposed approach is motivated by the scaled director conditioning (SDC) method for relative displacement shell elements. In contrast to SDC, the novel STC approach yields a preconditioner for the effective linear system. It is applicable independently of element technology employed, coupling to other physical fields, boundary conditions applied and additional algebraic constraints and can be easily extended to multilayer shell formulations.The effect of the proposed preconditioner on the conditioning of the effective stiffness matrix and its eigenvalue spectrum is studied. It is shown that the condition number of the modified system becomes almost independent from the aspect ratio of the employed elements. The improved conditioning has a positive influence on the convergence behavior of iterative linear solvers. In particular, in combination with algebraic multigrid preconditioners the number of iterations could be decreased by more than 85% for some examples and the computation time could be reduced by about 60%.     

Additive polynomial preconditioners for parallel computers

We present a polynomial preconditioner that can be used with the conjugate gradient method to solve symmetric and positive definite systems of linear equations. Each step of the preconditioning is achieved by simultaneously taking an iteration of the SOR method and an iteration of the reverse SOR method (equations taken in reverse order) and averaging the results. This yields a symmetric preconditioner that can be implemented on parallel computers by performing the forward and reverse SOR iterations simultaneously. We give necessary and sufficient conditions for additive preconditioners to be positive definite.

We find an optimal parameter, ω, for the SOR-Additive linear stationary iterative method applied to 2-cyclic matrices. We show this method is asymptotically twice as fast as SSOR when the optimal ω is used.

We compare our preconditioner to the SSOR polynomial preconditioner for a model problem. With the optimal ω, our preconditioner was found to be as effective as the SSOR polynomial preconditioner in reducing the number of conjugate gradient iterations. Parallel implementations of both methods are discussed for vector and multiple processors. Results show that if the same number of processors are used for both preconditioners, the SSOR preconditioner is more effective. If twice as many processors are used for the SOR-Additive preconditioner, it becomes more efficient than the SSOR preconditioner when the number of equations assigned to a processor is small. These results are confirmed by the Blue Chip emulator at the University of Washington.     

Domain decomposition PCG methods for serial and parallel processing

In this paper two domain decomposition formulations are presented in conjunction with the preconditioned conjugate gradient method (PCG) for the solution of large-scale problems in solid and structural mechanics. In the first approach, the PCG method is applied to the global coefficient matrix, while in the second approach it is applied to the interface problem after eliminating the internal degrees of freedom. For both implementations, a subdomain-by-subdomain (SBS) polynomial preconditioner is employed, based on local information of each subdomain. The approximate inverse of the global coefficient matrix or the Schur complement matrix, which acts as the preconditioner, is expressed by a truncated Neumann series resulting in an additive type local preconditioner. Block type preconditioning, where full elimination is performed inside each block, is also studied and compared with the proposed polynomial preconditioning.     

自顶向下聚集型代数多重网格预条件的边权选择

针对基于图划分的自顶向下聚集型代数多重网格预条件,考察了利用METIS软件包进行多重网格构建的方法,并就该软件包只能处理整型权重,不能处理实型权重的问题,提出了一种将实型边权转化为整型边权的有效方法。之后将这种转化方法应用到METIS图划分软件中的边权选择,并用其给出了对自顶向下聚集型代数多重网格预条件的一种改进算法。通过对二维与三维模型偏微分方程离散所得稀疏线性方程组的数值实验表明,带边权的改进型算法大大提高了多重网格预条件共轭斜量法的迭代效率,特别是对各向异性问题,改进效果更加显著。     

Improving the efficiency of preconditioning for iterative methods

Techniques based on the idea of preconditioning and on the element-by-element concept have significantly improved the efficiency of classical iterative methods in conventional as well as in parallel hardware environment. In this work two preconditioning approaches based on the incomplete Choleski factorization have been further refined, with the result that both storage requirements and solution times have been greatly improved when processing large structural problems. The partial preconditioning method is also employed to develop a framework for constructing a global preconditioner, without the need to store the complete coefficient matrix, for accelerating an iterative element-by-element solution procedure.     

Parallel methods for optimality criteria-based topology optimization

Topology optimization problems require the repeated solution of finite element problems that are often extremely ill-conditioned due to highly heterogeneous material distributions. This makes the use of iterative linear solvers inefficient unless appropriate preconditioning is used. Even then, the solution time for topology optimization problems is typically very high. These problems are addressed by considering the use of non-overlapping domain decomposition-based parallel methods for the solution of topology optimization problems. The parallel algorithms presented here are based on the solid isotropic material with penalization (SIMP) formulation of the topology optimization problem and use the optimality criteria method for iterative optimization. We consider three parallel linear solvers to solve the equilibrium problem at each step of the iterative optimization procedure. These include two preconditioned conjugate gradient (PCG) methods: one using a diagonal preconditioner and one using an incomplete LU factorization preconditioner with a drop tolerance. A third substructuring solver that employs a hybrid of direct and iterative (PCG) techniques is also studied. This solver is found to be the most effective of the three solvers studied, both in terms of parallel efficiency and in terms of its ability to mitigate the effects of ill-conditioning. In addition to examining parallel linear solvers, we consider the parallelization of the iterative optimality criteria method. To tackle checkerboarding and mesh dependence, we propose a multi-pass filtering technique that limits the number of “ghost” elements that need to be exchanged across interprocessor boundaries.     

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.     

Efficient unsteady high Reynolds number flow computations on unstructured grids

Despite the advances in computer power and numerical algorithms over the last decades, solutions to unsteady flow problems remain computing time intensive. Especially for high Reynolds number flows, nonlinear multigrid, which is commonly used to solve the nonlinear systems of equations, converges slowly. The stiffness induced by the high-aspect ratio cells and turbulence is not tackled well by this solution method.In this paper, it is investigated if a Jacobian-free Newton-Krylov (jfnk) solution method can speed up unsteady flow computations at high Reynolds numbers. Preconditioning of the linear systems that arise after Newton linearization is commonly performed with matrix-free preconditioners or approximate factorizations based on crude approximations of the Jacobian. Approximate factorizations based on a Jacobian that matches the target residual operator are unpopular because these preconditioners consume a large amount of memory and can suffer from robustness issues. However, these preconditioners remain appealing because they closely resemble A^-1.In this paper, it is shown that a jfnk solution method with an approximate factorization preconditioner based on a Jacobian that approximately matches the target residual operator enables a speed up of a factor 2.5-12 over nonlinear multigrid for two-dimensional high Reynolds number flows. The solution method performs equally well as nonlinear multigrid for three-dimensional laminar problems. A modest memory consumption is achieved with partly lumping the Jacobian before constructing the approximate factorization preconditioner, whereas robustness is ensured with enhanced diagonal dominance.     

Improving the preconditioning of linear systems from interior point methods

This paper deals with preconditioners for solving linear systems arising from interior point methods, using iterative methods. The main focus is the development of a set of results that allows a more efficient computation of the splitting preconditioner. During the interior point methods iterations, the linear system matrix becomes ill conditioned, leading to numerical difficulties to find a solution, even with iterative methods. Therefore, the choice of an effective preconditioner is essential for the success of the approach. The paper proposes a new ordering for a splitting preconditioner, taking advantage of the sparse structure of the original matrix. A formal demonstration shows that performing this new ordering the preconditioned matrix condition number is limited; numerical experiments reinforce the theoretical results. Case studies show that the proposed idea has better sparsity features than the original version of the splitting preconditioner and that it is competitive regarding the computational time.