New block triangular preconditioner for linear systems arising from the discretized time-harmonic Maxwell equations

In this paper, based on the preconditioners presented by Rees and Greif [T. Rees, C. Greif, A preconditioner for linear systems arising from interior point optimization methods, SIAM J. Sci. Comput. 29 (2007) 1992-2007], we present a new block triangular preconditioner applied to the problem of solving linear systems arising from finite element discretization of the mixed formulation of the time-harmonic Maxwell equations (k=0) in electromagnetic problems, since linear systems arising from the corresponding equations and methods have the same matrix block structure. Similar to spectral distribution of the preconditioners presented by Rees and Greif, this paper analyzes the corresponding spectral distribution of the new preconditioners considered in this paper. From the views of theories and applications, the presented preconditioners are as efficient as the preconditioners presented by Rees and Greif to apply. Moreover, numerical experiments are also reported to illustrate the efficiency of the presented preconditioners.     

On some new approximate factorization methods for block tridiagonal matrices suitable for vector and parallel processors

In this paper, to obtain an efficient parallel algorithm to solve sparse block-tridiagonal linear systems, stair matrices are used to construct some parallel polynomial approximate inverse preconditioners. These preconditioners are suitable when the desired goal is to maximize parallelism. Moreover, some theoretical results concerning these preconditioners are presented and how to construct preconditioners effectively for any nonsingular block tridiagonal H-matrices is also described. In addition, the validity of these preconditioners is illustrated with some numerical experiments arising from the second order elliptic partial differential equations and oil reservoir simulations.     

Variants of the deteriorated PSS preconditioner for saddle point problems

Two new preconditioners, which can be viewed as variants of the deteriorated positive definite and skew-Hermitian splitting preconditioner, are proposed for solving saddle point problems. The corresponding iteration methods are proved to be convergent unconditionally for cases with positive definite leading blocks. The choice strategies of optimal parameters for the two iteration methods are discussed based on two recent optimization results for extrapolated Cayley transform, which result in faster convergence rate and more clustered spectrum. Compared with some preconditioners of similar structures, the new preconditioners have better convergence properties and spectrum distributions. In addition, more practical preconditioning variants of the new preconditioners are considered. Numerical experiments are presented to illustrate the advantages of the new preconditioners over some similar preconditioners to accelerate GMRES.     

New preconditioners for systems of linear equations with Toeplitz structure

In this paper, we consider applying the preconditioned conjugate gradient (PCG) method to solve system of linear equations $T x = \mathbf b $ where $T$ is a block Toeplitz matrix with Toeplitz blocks (BTTB). We first consider Level-2 circulant preconditioners based on generalized Jackson kernels. Then, BTTB preconditioners based on a splitting of BTTB matrices are proposed. We show that the BTTB preconditioners based on splitting are special cases of embedding-based BTTB preconditioners, which are also good BTTB preconditioners. As an application, we apply the proposed preconditioners to solve BTTB least squares problems. Our preconditioners work for BTTB systems with nonnegative generating functions. The implementations of the construction of the preconditioners and the relevant matrix-vector multiplications are also presented. Finally, Numerical examples, including image restoration problems, are presented to demonstrate the efficiency of our proposed preconditioners.     

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.     

A Decoupled Preconditioning Technique for a Mixed Stokes–Darcy Model

We propose an efficient iterative method to solve the mixed Stokes–Darcy model for coupling fluid and porous media flow. The weak formulation of this problem leads to a coupled, indefinite, ill-conditioned and symmetric linear system of equations. We apply a decoupled preconditioning technique requiring only good solvers for the local mixed-Darcy and Stokes subproblems. We prove that the method is asymptotically optimal and confirm, with numerical experiments, that the performance of the preconditioners does not deteriorate on arbitrarily fine meshes.     

On a class of row preconditioners for solving linear systems

The purpose of this paper is to give comparison results for a class of row preconditioners. Convergence and monotone properties for the classical iterative methods associated with these preconditioners are analysed. In the final section, numerical results are presented.     

Large scale micro finite element analysis of 3D bone poroelasticity

In this paper, a solver for poroelasticity problems related to osteoporotic human bones is discussed. Osteoporosis is a major health problem that compromises the integrity of bones. A good understanding of the disease requires an accurate simulation of the physics. For that purpose, a finite element solver based on Biot’s consolidation equations has been developed. A mixed formulation is used to discretize the geometries taken from medical imaging. The resulting indefinite linear systems are solved by Krylov space methods supplemented by variants of Schur complement-based block preconditioners.     

A robust preconditioner for fluid–structure interaction problems

Two preconditioners are presented for equation systems of strongly coupled fluid–structure interaction computations where the structure is modeled by shell elements. These preconditioners fall into the general category of incomplete LU factorization. The two differ mainly in whether the coefficient matrix is factorized node by node or variable-by-variable. In the variable-wise preconditioner, a modified Schur complement system for pressure is solved approximately with a few iterations using a special preconditioner. The efficiencies of the two preconditioners are compared for different finite element formulations of the fluid mechanics part, including formulations with SUPG and PSPG stabilizations.     

Two augmentation preconditioners for nonsymmetric and indefinite saddle point linear systems with singular (1, 1) blocks

In this paper, two preconditioners based on augmentation are introduced for the solution of large saddle point-type systems with singular (1, 1) blocks. We study the spectral characteristics of the preconditioners, show that all eigenvalues of preconditioned matrices are strongly clustered. Finally, numerical experiments are also reported for illustrating the efficiency of the presented preconditioners.     

Parallel algebraic multilevel Schwarz preconditioners for a class of elliptic PDE systems

Algebraic multilevel preconditioners for algebraic problems arising from the discretization of a class of systems of coupled elliptic partial differential equations (PDEs) are presented. These preconditioners are based on modifications of Schwarz methods and of the smoothed aggregation technique, where the coarsening strategy and the restriction and prolongation operators are defined using a point-based approach with a primary matrix corresponding to a single PDE. The preconditioners are implemented in a parallel computing framework and are tested on two representative PDE systems. The results of the numerical experiments show the effectiveness and the scalability of the proposed methods. A convergence theory for the twolevel case is presented.     

Conditioning analysis of separate displacement preconditioners for some nonlinear elasticity systems

Separate displacement preconditioners are studied in the context of outer–inner iterations for a model in 3D nonlinear elasticity. Such a preconditioner, already known to be efficient for linear models, arises as the discretization of three independent Laplacian operators. In this paper the resulting condition number is investigated with focus on independence of parameters. Estimates are given which show that the condition number is uniformly bounded w.r.t. both the studied Newton iterate and the chosen discretization. Finally, it is sketched that ill-conditioning caused by nearly incompressible material parameters can be handled by a suitable mixed formulation.     

Multilevel Schwarz methods for elliptic partial differential equations

We investigate multilevel Schwarz domain decomposition preconditioners, to efficiently solve linear systems arising from numerical discretizations of elliptic partial differential equations by the finite element method. In our analysis we deal with unstructured mesh partitions and with subdomain boundaries resulting from using the mesh partitioner. We start from two-level preconditioners with either aggregative or interpolative coarse level components, then we focus on a strategy to increase the number of levels. For all preconditioners, we consider the additive residual update and its multiplicative variants within and between levels. Moreover, we compare the preconditioners behaviour, regarding scalability and rate of convergence. Numerical results are provided for elliptic boundary value problems, including a convection–diffusion problem when suitable stabilization becomes necessary.     

A class of approximate inverse preconditioners for solving linear systems

Some preconditioners for accelerating the classical iterative methods are given in Zhang et al. [Y. Zhang and T.Z. Huang, A class of optimal preconditioners and their applications, Proceedings of the Seventh International Conference on Matrix Theory and Its Applications in China, 2006. Y. Zhang, T.Z. Huang, and X.P. Liu, Modified iterative methods for nonnegative matrices and M-matrices linear systems, Comput. Math. Appl. 50 (2005), pp. 1587–1602. Y. Zhang, T.Z. Huang, X.P. Liu, A class of preconditioners based on the (I+S(α))-type preconditioning matrices for solving linear systems, Appl. Math. Comp. 189 (2007), pp. 1737–1748]. Another kind of preconditioners approximating the inverse of a symmetric positive definite matrix was given in Simons and Yao [G. Simons, Y. Yao, Approximating the inverse of a symmetric positive definite matrix, Linear Algebra Appl. 281 (1998), pp. 97–103]. Zhang et al. ’s preconditioners and Simons and Yao's are generalized in this paper. These preconditioners are all of low construction cost, which all could be taken as approximate inverse of M-matrices. Numerical experiments of these preconditioners applied with Krylov subspace methods show the effectiveness and performance, which also show that the preconditioners proposed in this paper are better approximate inverse for M-matrices than Simons’.     

Two-Level Additive Schwarz Preconditioners for a Weakly Over-Penalized Symmetric Interior Penalty Method

We propose and analyze several two-level additive Schwarz preconditioners for a weakly over-penalized symmetric interior penalty method for second order elliptic boundary value problems. We also report numerical results that illustrate the parallel performance of these preconditioners.     

Accelerating iterative linear solvers using multiple graphical processing units

In this paper, we develop, study and implement iterative linear solvers and preconditioners using multiple graphical processing units (GPUs). Techniques for accelerating sparse matrix–vector (SpMV) multiplication, linear solvers and preconditioners are presented. Four Krylov subspace solvers, a Neumann polynomial preconditioner and a domain decomposition preconditioner are implemented. Our numerical tests with NVIDIA C2050 GPUs show that the SpMV kernel can be sped over 40 times faster using four GPUs. Our linear solvers and preconditioners have similar speedup.     

Parallel Performance of Block ILU Preconditioners for a Block-tridiagonal Matrix

The parallelizable block ILU (incomplete LU) factorization preconditioners for a block-tridiagonal matrix have been recently proposed by the author. In this paper, we describe a parallelization of Krylov subspace methods with the block ILU factorization preconditioners on distributed-memory computers such as the Cray T3E, and then parallel performance results of a preconditioned Krylov subspace method are provided to evaluate the effectiveness and efficiency of the block ILU preconditioners on the Cray T3E.     

面向大规模高速数字及射频混合信号测量方法

针对大规模高速数字及射频混合信号的测量问题,提出了一种基于综合测量系统的解决方案,通过融合了柔性测试、并行测试和基于TestStand引擎的自动化测试等先进测试技术的综合测量系统,结合总分总以及自底而上的测试方法,实现大规模高速数字和射频混合信号的高效及全面的测试.经过实测,验证了该套系统及方法,为面向大规模高速数字及射频混合信号的测量提供了一个行之有效的解决方案.     

On Hybrid Multigrid-Schwarz Algorithms

J. Lottes and P. Fischer (J. Sci. Comput. 24:45–78, [2005]) studied many smoothers or preconditioners for hybrid Multigrid-Schwarz algorithms for the spectral element method. The behavior of several of these smoothers or preconditioners are analyzed in the present paper. Here it is shown that the Schwarz smoother that best performs in the above reference, is equivalent to a special case of the weighted restricted additive Schwarz, for which convergence analysis is presented. For other preconditioners which do not perform as well, examples and explanations are presented illustrating why this behavior may occur. S. Loisel and D.B. Szyld are supported in part by the U.S. Department of Energy under grant DE-FG02-05ER25672.     

Distributed block independent set algorithms and parallel multilevel ILU preconditioners

We present a class of parallel preconditioning strategies utilizing multilevel block incomplete LU (ILU) factorization techniques to solve large sparse linear systems. The preconditioners are constructed by exploiting the concept of block independent sets (BISs). Two algorithms for constructing BISs of a sparse matrix in a distributed environment are proposed. We compare a few implementations of the parallel multilevel ILU preconditioners with different BIS construction strategies and different Schur complement preconditioning strategies. We also use some diagonal thresholding and perturbation strategies for the BIS construction and for the last level Schur complement ILU factorization. Numerical experiments indicate that our domain-based parallel multilevel block ILU preconditioners are robust and efficient.