ITERATIVE ILU PRECONDITIONERS FOR LINEAR SYSTEMS AND EIGENPROBLEMS

Iterative ILU factorizations are constructed,analyzed and applied as preconditioners to solve both linear systems and eigenproblems.The computational kernels of these novel Iterative ILU factorizations are sparse matrix-matrix multiplications,which are easy and efficient to implement on both serial and parallel computer architectures and can take full advantage of existing matrix-matrix multiplication codes.We also introduce level-based and threshold-based algorithms in order to enhance the accuracy of the proposed Iterative ILU factorizations.The results of several numerical experiments illustrate the efficiency of the proposed preconditioners to solve both linear systems and eigenvalue problems.     

Mixed finite element analysis of semi-coercive unilateral contact problems with given friction

A unilateral contact 2D-problem is considered provided one of two elastic bodies can shift in a given direction as a rigid body. Using Lagrange multipliers for both normal and tangential constraints on the contact interface, we introduce a saddle point problem and prove its unique solvability. We discretize the problem by a standard finite element method and prove a convergence of approximations. We propose a numerical realization on the basis of an auxiliary “ bolted” problem and the algorithm of Uzawa.     

Structured preconditioners for nonsingular matrices of block two-by-two structures

For the large sparse block two-by-two real nonsingular matrices, we establish a general framework of practical and efficient structured preconditioners through matrix transformation and matrix approximations. For the specific versions such as modified block Jacobi-type, modified block Gauss-Seidel-type, and modified block unsymmetric (symmetric) Gauss-Seidel-type preconditioners, we precisely describe their concrete expressions and deliberately analyze eigenvalue distributions and positive definiteness of the preconditioned matrices. Also, we show that when these structured preconditioners are employed to precondition the Krylov subspace methods such as GMRES and restarted GMRES, fast and effective iteration solvers can be obtained for the large sparse systems of linear equations with block two-by-two coefficient matrices. In particular, these structured preconditioners can lead to efficient and high-quality preconditioning matrices for some typical matrices from the real-world applications.

     

Two-level Additive Schwarz Preconditioners for Nonconforming Finite Element Methods

Two-level additive Schwarz preconditioners are developed for the nonconforming P1 finite element approximation of scalar second-order symmetric positive definite elliptic boundary value problems, the Morley finite element approximation of the biharmonic equation, and the divergence-free nonconforming P1 finite element approximation of the stationary Stokes equations. The condition numbers of the preconditioned systems are shown to be bounded independent of mesh sizes and the number of subdomains in the case of generous overlap.

     

Monotone Comparative Statics: Geometric Approach

We consider the comparative statics of solutions to parameterized optimization problems. A geometric method is developed for finding a vector field that, at each point in the parameter space, indicates a direction in which monotone comparative statics obtains. Given such a vector field, we provide sufficient conditions under which the problem can be reparameterized on the parameter space (or a subset thereof) in a way that guarantees monotone comparative statics. A key feature of our method is that it does not require the feasible set to be a lattice and works in the absence of the standard quasi-supermodularity and single-crossing assumptions on the objective function. We illustrate our approach with a variety of applications. We are grateful to Kenneth Arrow, Darrell Duffie, David Luenberger, Paul Milgrom, John Quah, and Pete Veinott for helpful comments. Research in part supported by a David Morgenthaler II Faculty Scholar Award.     

Approximate,limiting and generalized trajectories of feedback differential systems

In view of possible applications in Optimal Control, Differential Games and other fields, we obtain certain invariant characterizations of the limiting Euler trajectories and of the limiting Krassovskii‐Subbotin trajectories of large classes of feedback differential systems defined as parameterized differential inclusions. We prove that these limiting trajectories are Carathéodory solutions of certain associated u.s.c.‐convexified differential inclusions which contain their generalized tangent and contingent directions. In particular, we give a counterexample to a conjecture of Krassovskii and Subbotin (1974) and provide a proof of its correct variant. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An iterative implementation of the Uzawa algorithm for 3-D fluid flow problems

A new iterative algorithm for the solution of the three-dimensional Navier–Stokes equations by the finite element method is presented. This algorithm is based on a combination of the Uzawa and the Arrow–Hurwicz algorithms and uses a preconditioning technique to enhance convergence. Numerical tests are presented for the cubic cavity problem with two elements, namely the linear brick Q₁?P₀ and the enriched linear brick Q₁⁺ ? P₁. It is shown that the proposed methodology is optimal with the enriched element and that the CPU time varies as NEQ^1·44, where NEQ is the number of equations.     

Alternating oblique projections for coupled linear systems

In this work we propose the use of alternating oblique projections (AOP) for the solution of the saddle points systems resulting from the discretization of domain decomposition problems. These systems are called coupled linear systems. The AOP method is a descent method in which the descent direction is defined by using alternating oblique projections onto the search subspaces. We prove that this method is a preconditioned simple gradient (Uzawa) method with a particular preconditioner. Finally, a preconditioned conjugate gradient based version of AOP is proposed. AMS subject classification 65F10, 65N22, 65Y05     

Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations

Time harmonic Maxwell equations in lossless media lead to a second order differential equation for the electric field involving a differential operator that is neither elliptic nor definite. A Galerkin method using Nedelec spaces can be employed to get approximate solutions numerically. The problem of preconditioning the indefinite matrix arising from this method is discussed here. Specifically, two overlapping Schwarz methods will be shown to yield uniform preconditioners.

     

混凝土细观力学分析程序中的快速算法与并行算法设计

针对一套混凝土细观力学分析程序,在分析其计算方法与计算效率的不足之后,提出了采用稀疏矩阵与稀疏向量技术来高效实现有限元刚度矩阵装配过程的算法,并采用双门槛不完全Cholesky分解预条件技术与CG法相结合来高效地求解稀疏线性方程组。之后,从整体上提出了一个将有限单元分布与未知量分布有机结合的并行算法设计方案,并分别针对刚度矩阵装配、双门槛不完全Cholesky分解、稀疏矩阵与稠密向量相乘、稀疏向量相加等核心算法,进行了相应的并行算法设计。最后,在由每节点2 CPU的8个Intel Xeon节点采用千兆以太网连成的机群上,针对两个混凝土数值试样进行了数值实验,第一个试样含44117个网格点与53200个有限单元,第二个试样含71013个网格点与78800个有限单元;对第一个试样,原串行程序进行全程567次加载计算需要984.83小时约41天,采用文中串行算法后,模拟时间减少到22531秒约6.26小时,采用并行算法在16个CPU上的模拟时间进一步降为3860秒约1.07小时。对第二个试样,原串行程序进行全程94次加载计算需要467.19小时约19.5天,采用文中串行算法后,模拟时间减少到11453秒约3.18小时,采用并行算法在16个CPU上的模拟时间进一步降为1704秒约28.4分钟。串行算法的改进与并行算法的设计大大缩短了计算时间,对加快混凝土力学性能的分析研究具有重要意义。