h-p Spectral Element Method for Elliptic Problems on Non-smooth Domains Using Parallel Computers

We propose a new h-p spectral element method to solve elliptic boundary value problems with mixed Neumann and Dirichlet boundary conditions on non-smooth domains. The method is shown to be exponentially accurate and asymptotically faster than the standard h-p finite element method. The spectral element functions are fully non-conforming for pure Dirichlet problems and conforming only at the vertices of the elements for mixed problems, and hence, the dimension of the resulting Schur complement matrix is quite small. The method is a least-squares collocation method and the resulting normal equations are solved using preconditioned conjugate gradient method with an almost optimal preconditioner. The algorithm is suitable for a distributed memory parallel computer. The numerical results of a number of model problems are presented, which confirm the theoretical estimates.     

Parallel and Systolic Solution of Normalized Explicit Approximate Inverse Preconditioning

A new class of normalized approximate inverse matrix techniques, based on the concept of sparse normalized approximate factorization procedures are introduced for solving sparse linear systems derived from the finite difference discretization of partial differential equations. Normalized explicit preconditioned conjugate gradient type methods in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of sparse linear systems. Theoretical results on the rate of convergence of the normalized explicit preconditioned conjugate gradient scheme and estimates of the required computational work are presented. Application of the new proposed methods on two dimensional initial/boundary value problems is discussed and numerical results are given. The parallel and systolic implementation of the dominant computational part is also investigated.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

最小二乘有限元法和有限体积法在CFD中的应用比较

为比较最小二乘有限元法（Least Square Finite Element Method,LSFEM）和有限体积法在CFD应用中的优劣,采用最小二乘法离散不可压N-S方程的有限元模型,得到正定对称线性系统,采用高效的预处理共轭梯度法求解方程组;利用LSFEM和基于有限体积法的FLUENT分别计算Kovasznay流动、定常二维和三维后台阶流动以及非定常圆柱绕流等4个实例并比较计算结果.结果表明,LSFEM比有限体积法的收敛性和精确性更好,在CFD领域的应用价值很高.     

An alternative approach to a distributed parameter optimal control problem

The optimization of a class of linear deterministic time-invariant multi-dimonsional distributed parameter control systems is presented. Both unconstrained and constrained, optimizations are formulated as two-point boundary value problems. A conjugate gradient method of solution is proposed. The theory is applied to a two-du(iensional heat conduction system by way of an example.     

A new modified scaled conjugate gradient method for large-scale unconstrained optimization with non-convex objective function

In this paper, according to the fifth-order Taylor expansion of the objective function and the modified secant equation suggested by Li and Fukushima, a new modified secant equation is presented. Also, a new modification of the scaled memoryless BFGS preconditioned conjugate gradient algorithm is suggested which is the idea to compute the scaling parameter based on a two-point approximation of our new modified secant equation. A remarkable feature of the proposed method is that it possesses a globally convergent even without convexity assumption on the objective function. Numerical results show that the proposed new modification of scaled conjugate gradient is efficient.     

Constrained multibody system dynamics an automated approach

The governing equations for constrained multibody systems are formulated in a manner suitable for their automated, numerical development and solution. Specifically, the “closed loop” problem of multibody chain systems is addressed.

The governing equations are developed by modifying dynamical equations obtained from Lagrange's form of d'Alembert's principle. This modification, which is based upon a solution of the constraint equations obtained through a “zero eigenvalues theorem,” is, in effect, a contraction of the dynamical equations.

It is observed that, for a system with n generalized coordinates and m constraint equations, the coefficients in the constraint equations may be viewed as “constraint vectors” in n-dimensional space. Then, in this setting the system itself is free to move in the n−m directions which are “orthogonal” to the constraint vectors.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

On the number of occurrences of all short factors in almost all words

We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k(n) over A as n→∞, provided limsup_n→∞ k(n)/log n<1/log m.

In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where lim_n→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0.     

Variational geometry: A new method for modifying part geometry for finite element analysis

Interactive graphic methods have the potential to significantly reduce the cost associated with pre- and post-processing of finite element analyses. One area of particular importance is the creation and modification of part geometry.

This paper describes a powerful method for modification of geometry for finite element analysis pre-processors. The method, called “Variational Geometry”, uses a single representation to describe the entire family of geometries that share a generic shape.

A solid geometric model of a component is defined with respect to a set of scalar parameters. Dimensions, such as those which appear on a mechanical drawing, are treated as constraints on the permissible values of these parameters. Constraints on the geometry are expressed as a set of non-linear algebraic equations. The values of the parameters and hence the geometry may be determined by solving the set of non-linear constraint equations.

A procedure for minimizing the computational requirements is presented. For a part with n degrees of freedom, the solution time is shown to be O(n).     

Distributed Lagrange multipliers based on fictitious domain method for second order elliptic problems

In this article we further investigate the solution of linear second order elliptic boundary value problems by distributed Lagrange multipliers based fictitious domain methods. The following issues are addressed: (i) Derivation of the fictitious domain formulations. (ii) Finite element approximation. (iii) Iterative solution of the resulting finite dimensional problems (of the saddle-point type) by preconditioned conjugate gradient and Lanczos algorithms.     

k元n方体的条件强匹配排除

为了度量发生故障时k元n方体对其可匹配性的保持能力,通过剖析条件故障下使得k元n方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得k元n方体不可匹配所需的最小故障数。当k ≥ 4为偶数且n ≥ 2时,得出了k元n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当k ≥ 3为奇数且n ≥ 2时,给出了该k元n方体容错性参数的一个可达下界和一个可达上界。结果表明,选取k为奇数的k元n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2n时仍是可匹配的,要使该系统不可匹配至多需要4n-3个故障元。     

Multitasking the conjugate gradient method on the CRAY X-MP/48

We show how to efficiently implement the preconditioned conjugate gradient method on a four processors computer CRAY X-MP/48. We solve block tridiagonal systems using block preconditioners well suited to parallel computation. Numerical results are presented that exhibit nearly optimal speedup and high Mflops rates.     

Block jacobi preconditioning of the conjugate gradient method on a vector processor

The preconditioned conjugate gradient method is well established for solving linear systems of equations that arise from the discretization of partial differential equations. Point and block Jacobi preconditioning are both common preconditioning techniques. Although it is reasonable to expect that block Jacobi preconditioning is more effective, block preconditioning requires the solution of triangular systems of equations that are difficult to vectorize. We present an implementation of block Jacobi for vector computers, especially for the Cray Y-MP/264, and discuss several techniques to improve vectorization. We present these in a progression to show the effect on performance. For the model problem, resulting from a self-adjoint operator, the final implementation of one block Jacobi step uses almost the same amount of time as one point Jacobi step on the Cray Y-MP/264 despite the solution of triangular systems.     

Preconditioned variational methods on rotated finite difference discretisation

Due to their rapid convergence properties, recent focus on iterative methods in the solution of linear system has seen a flourish on the use of gradient techniques which are primarily based on global minimisation of the residual vectors. In this paper, we conduct an experimental study to investigate the performance of several preconditioned gradient or variational techniques to solve a system arising from the so-called rotated (skewed) finite difference discretisation in the solution of elliptic partial differential equations (PDEs). The preconditioned iterative methods consist of variational accelerators, namely the steepest descent and conjugate gradient methods, applied to a special matrix ‘splitting’ preconditioned system. Several numerical results are presented and discussed.     

Multiple search direction conjugate gradient method I: methods and their propositions

In this article, we proposed a new CG-type method based on domain decomposition method, which is called multiple search direction conjugate gradient (MSD-CG) method. In each iteration, it uses a search direction in each subdomain. Instead of making all search directions conjugate to each other, as in the block CG method [O'Leary, D. P. (1980). The block conjugate gradient algorithm and related methods. Lin. Alg. Appl., 29, 293–322.], we require that they are nonzero in corresponding subdomains only. The GIPF-CG method, an approximate version of the MSD-CG method, only requires communication between neighboring subdomains and eliminate global inner product entirely. This method is therefore well suited for massively parallel computation. We give some propositions and a preconditioned version of the MSD-CG method.     

The age Galerkin method for solving two-point boundary value problems

In this paper finite element Galerkin methods are developed for spaces of piecewise polynomial functions which are most suitable for two-point boundary value problems. The resulting banded linear systems are then solved by a block matrix iterative method which is an extension of the point alternating group explicit (AGE) method.     

Distributed finite element calculations on transputer arrays and the DAP

An equation solver based on the preconditioned conjugate gradient method for the sparse system arising from finite element analysis is presented. The preconditioning matrix has been designed to take advantage of the domain decomposition approach used on local memory multiprocessor computers. The method has been implemented on a transputer array and on the DAP; results are given for these computers. A simple domain decomposition algorithm is also presented. This method is suitable for the decomposition of finite element meshes for the transputer based analysis program.     

The hierarchial preconditioning on unstructured grids

We present the implementation of two hierarchically preconditioned methods for the fast solution of mesh equations that approximate 2D-elliptic boundary value problems on unstructured quasi uniform triangulations. Based on the fictitious space approach the original problem can be embedded into an auxiliary one, where both the hierarchical grid information and the preconditioner are well defined. We implemented the corresponding Yserentant preconditioned conjugate gradient method as well as thebpx-preconditioned cg-iteration having optimal computational costs. Several numerical examples demonstrate the efficiency of the artificially constructed hierarchical methods which can be of importance in industrial engineering, where often only the nodal coordinates and the element connectivity of the underlying (fine) discretization are available.     

Exact boundary controllability of the second-order Maxwell system: Theory and numerical simulation

The exact controllability of the second order time-dependent Maxwell equations for the electric field is addressed through the Hilbert Uniqueness Method. A two-grid preconditioned conjugate gradient algorithm is employed to inverse the H.U.M. operator and to construct the numerical control. The underlying initial value problems are discretized by Lagrange finite elements and an implicit Newmark scheme. Two-dimensional numerical experiments illustrate the performance of the method.