热传导方程基于界面修正的迭代并行计算方法

在许多实际计算中,由于对时间步长稳定性的要求,辐射热传导方程的计算通常采用隐式格式．隐式格式难以直接在并行机上实施,显式差分格式尽管易于在并行机上实施,但它的稳定性条件苛刻．在计算问题规模相当大时,例如需要具有数百、数千甚至上万台处理器的大型并行计算机进行计算时,数据的强相关与全局通讯等问题成为制约实现高性能计算的突出的瓶颈问题．因此,改造现有的隐式格式,研究适应于大型并行计算机的并行计算方法是目前大型科学与工程计算中迫切需要解决的具有挑战性的问题．本文简要介绍基于界面修正的迭代并行计算格式的构造及基本性质．所提出的并行格式的构造方法是将预测-校正技术应用于分区子区域的内边界,且与子区域内部的迭代求解相结合,讨论了这些并行格式的稳定性、收敛性与并行度等性质．     

Nonlinear dynamics by mode superposition

A mode superposition technique for approximately solving nonlinear initial-boundary-value problems of structural dynamics is discussed, and results for examples involving large deformation are compared to those obtained with implicit direct integration methods such as the Newmark generalized acceleration and Houbolt backward-difference operators. The initial natural frequencies and mode shapes are found by inverse power iteration with the trial vectors for successively higher modes being swept by Gram—Schmidt orthonormalization at each iteration. The subsequent modal spectrum for nonlinear states is based upon the tangent stiffness of the structure and is calculated by a subspace iteration procedure that involves matrix multiplication only, using the most recently computed spectrum as an initial estimate. Then, a precise time integration algorithm that has no artificial damping or phase velocity error for linear problems is applied to the uncoupled modal equations of motion. Squared-frequency extrapolation is examined for nonlinear problems as a means by which these qualities of accuracy and precision can be maintained when the state of the system (and, thus, the modal spectrum) is changing rapidly.The results indicate that a number of important advantages accrue to nonlinear mode superposition: (a) there is no significant difference in total solution time between mode superposition and implicit direct integration analyses for problems having narrow matrix half-bandwidth (in fact, as bandwidth increases, mode superposition becomes more economical), (b) solution accuracy is under better control since the analyst has ready access to modal participation factors and the ratios of time step size to modal period, and (c) physical understanding of nonlinear dynamic response is improved since the analyst is able to observe the changes in the modal spectrum as deformation proceeds.     

关于非对称代数Riccati方程的ALI迭代算法收敛速率的讨论

交替线性化隐式迭代法(ALI)是求非对称代数Riccati方程最小非负解的一种十分有效的算法.其中所包含的一个参数能够显著影响其收敛速率.本文将讨论该参数的选择以及使收敛达到最快的参数最优值.     

Second-order predictor-corrector schemes for nonlinear distributed-order space-fractional differential equations with non-smooth initial data

ABSTRACT

We propose second-order linearly implicit predictor-corrector schemes for diffusion and reaction-diffusion equations of distributed-order. For diffusion equations of distributed order, we propose an analytical solution based on the spectral representation of the fractional Laplacian. Numerically, we approximate the integral term of the equation by the midpoint quadrature rule to obtain a multi-term space-fractional differential equation. The matrix transfer technique is used for spatial discretization of the resulting differential equation and methods based on Padé approximations to the exponential function are used in time. In particular, we discuss the (0,2)- and (1,1)-Padé approximations to the exponential function. The method based on the (1,1)-Padé approximation to the exponential function are seen to produce oscillations for some time steps and we propose a constraint on the choice of the time step to avoid these unwanted oscillations. Stability and convergence of the schemes are discussed. Numerical experiments are performed to support our theoretical observations.     

Implementation of high-order implicit runge-kutta methods

In this paper, we develop single-Newton iterative schemes for the solution of the stage equations of some implicit Runge-Kutta methods such as the four-stage Gauss and Radau IIA methods and the five-stage Lobatto IIIA formula. We also compare the implementation cost of these schemes with the simplified-Newton iteration and we present some numerical experiments on some well-known stiff test problems to show that the proposed iterations are reliable and efficient.     

Approximation of the Crank-Nicholson method by the iterated dynamic-theta method

Choptuik's iterated Crank-Nicholson method has become a popular algorithm for solving partial differential equations in computational physics. We generalize Choptuik's explicit iteration approach to implicit finite difference schemes, by the introduction of a novel method with an iteration step dependent parameter and analyze its stability and computational efficiency.     

A scheme for the implementation of implicit Runge-Kutta methods

The computational work required to implement implicit Runge-Kutta methods is often dominated by the cost of solving large sets of nonlinear equations. As an alternative to modified Newton methods, iteration schemes, which sacrifice superlinear convergence for reduced linear algebra costs, have been proposed. A new scheme of this type is considered here. This scheme avoids expensive vector transformations, is computationally more efficient, and gives improved performance.     

Improved predictor-corrector method for solving fuzzy initial value problems

In this paper, an improved predictor-corrector (IPC) method is proposed to solve the “fuzzy initial value problem”. The IPC method is generated by combining an explicit three-step method and an implicit two-step method. The methods are compared with the methods discussed in [T. Allahviranloo, N. Ahmady, E. Ahmady, Numerical solution of fuzzy differential equations by predictor-corrector method, Information Sciences 177(7) (2007) 1633-1647], and are shown to be more accurate. The convergence and stability of the proposed methods are also presented in detail. These methods are illustrated by solving some examples.     

Interval extensions and interval iterations

For nonlinear operators in partially ordered spaces interval extensions will be defined by means of Lipschitz operators. Assumptions are made for the inclusion monotony of these interval extensions. In this manner we obtain methods for interval iteration to include a solution of an operator equation. By transforming the equation in iterative form a parameter is chosen appropriately, so that the convergence of the interval sequence becomes as fast as possible.     

On the multi-grid method applied to difference equations

Multi-grid methods are characterized by the simultaneous use of additional auxiliary grids corresponding to coarser step widths. Contrary to usual iterative methods the speed of convergence is very fast and does not tend to one if the step size approaches zero. The computational amount of one iteration is proportional toN, the number of grid points. Thus, a solution with accuracy ? requires 0 (|log ?|N) operations. In this paper we apply a multi-grid method to Helmholtz's equation (Dirichlet boundary data) in a general region and to a differential equation with variable coefficients subject to arbitrary boundary conditions.     

An iterative matrix-free method in implicit immersed boundary/continuum methods

The objective of this paper is to present an iterative solution strategy for implicit immersed boundary/continuum methods. An overview of the newly proposed immersed continuum method in conjunction with the traditional immersed boundary method will also be presented. As a key ingredient of the fully implicit time integration, a matrix-free combination of Newton–Raphson iteration and GMRES iterative linear solver is proposed.     

Isomorphic iterative methods in solving singularly perturbed elliptic difference equations

A new approach for the efficient numerical solution of Singular Perturbation (SP) second order boundary-value problems based on Gradient-type methods is introduced. Isomorphic implicit iterative schemes in conjuction with the Extended to the Limit sparse factorization procedures [9] are used for solving SP second order elliptic equations in two and three-space dimensions. Theoretical results on the convergence rate of these first-degree iterative methods for three-space variables are presented. The application of the new methods on characteristic SP boundary-value problems is discussed and numerical results are given.     

Convergence acceleration of the rational Runge-Kutta scheme for the Euler and Navier-Stokes equations

An efficient method-of-lines approach is presented for the Euler and Navier-Stokes equations. The governing equations are spatially discretized by a central finite-difference approximation. The rational Runge-Kutta scheme is used for the time integration. Attention is focused on improving the efficiency and accuracy of the solution. A remarkable improvement in the efficiency is achieved by adopting a combination of the present scheme with the residual averaging and multigrid (M.G.) techniques. The M.G. method and the high suitability of the present scheme to a vector computer partly reduce the computational load imposed on a numerical simulation with a finer grid. The steady-state convergence obtained with the scheme is comparable with those of diagonalized implicit approximate factorization schemes for inviscid and viscous flow equations. The reliability and accuracy of the scheme have also been improved by adopting the artificial dissipation terms scaled down to the minimum level required for stability. The facilities of the scheme are demonstrated in a series of numerical experiments for two- and three-dimensional transonic flows.     

On a nonlinear iterative method in applied mechanics-part 1

A particular iterative method that has proven effective for finite difference solution of nonlinear membrane and plate problems is studied. The iteration is shown to belong to a general class of iterations termed SOR-Newton m_k step iteration and corresponds to the choice m_k = 1. As a result of this characterization we proceed to give the theoretical basis for studying convergence of the iteration. From this standpoint one is better able to evaluate the utility and limitations of the iterative scheme and compare it with alternative competitive schemes for various classes of problems and nonlinear systems in applied mechanics.     

Extension of fractional step techniques for incompressible flows: The preconditioned Orthomin(1) for the pressure Schur complement

The objective of this paper is to present different fractional step schemes in the algebraic context to solve the incompressible Navier–Stokes equations, test them and pick the best one in terms of efficiency and robustness. The equivalence between fractional step schemes and iterative methods for the pressure Schur complement system has been well established in the literature. For example, the classical incremental projection scheme can be associated with a Richardson iteration for the pressure Schur complement plus a correction to enforce the mass conservation. We introduce in this paper an Orthomin(1) iteration which minimizes the Schur complement residual at each solver iteration by using, in the updating step, a factor dynamically computed. Two versions are considered, namely the momentum preserving and continuity preserving versions. The method is compared to the classical Richardson method, including the continuity and momentum preserving versions. In addition, two Schur complement preconditioners are considered and compared, based on the approximation of the weak Uzawa operator. From the implementation point of view, the benefit of the method is two fold. On the one hand, it can be easily implemented starting from the global matrix of the monolithic scheme, without changing the assembly. On the other hand, it enables the use of simple algebraic solvers without the need for complex preconditioners; this is a requirement for massively parallel computers. The four methods are finally tested and compared through the solution of numerical examples. The main conclusion is that with very few additional computation, the Orthomin(1) iteration largely improves the global convergence properties of the fractional schemes here presented.     

An iterative scheme for numerical solution of steady incompressible viscous flows

An iterative solution scheme is proposed for application to steady incompressible viscous flows in simple and complex geometries. The iterative scheme solves the vorticity-stream function form of the Navier-Stokes equations in generalized curvilinear coordinates. The flow system of equations are cast into a Newton's iterative form which are solved using the modified strongly implicit procedure. The solution scheme is benchmarked using two test cases, namely: a shear-driven steady laminar flow in a square cavity; and a simple laminar flow in a complex expanding channel. The iterative process to steady-state convergence in both test cases is highly stable and the convergence rate is without spurious oscillations. At convergence, the flow solutions are second-order accurate.     

Parametric image alignment using enhanced correlation coefficient maximization

In this work we propose the use of a modified version of the correlation coefficient as a performance criterion for the image alignment problem. The proposed modification has the desirable characteristic of being invariant with respect to photometric distortions. Since the resulting similarity measure is a nonlinear function of the warp parameters, we develop two iterative schemes for its maximization, one based on the forward additive approach and the second on the inverse compositional method. As it is customary in iterative optimization, in each iteration the nonlinear objective function is approximated by an alternative expression for which the corresponding optimization is simple. In our case we propose an efficient approximation that leads to a closed form solution (per iteration) which is of low computational complexity, the latter property being particularly strong in our inverse version. The proposed schemes are tested against the Forward Additive Lucas-Kanade and the Simultaneous Inverse Compositional algorithm through simulations. Under noisy conditions and photometric distortions our forward version achieves more accurate alignments and exhibits faster convergence whereas our inverse version has similar performance as the Simultaneous Inverse Compositional algorithm but at a lower computational complexity.     

Numerical convergence and interpretation of the fuzzy c-shellsclustering algorithm

R. N. Dave's (1990) version of fuzzy c-shells is an iterative clustering algorithm which requires the application of Newton's method or a similar general optimization technique at each half step in any sequence of iterates for minimizing the associated objective function. An important computational question concerns the accuracy of the solution required at each half step within the overall iteration. The general convergence theory for grouped coordination minimization is applied to this question to show that numerically exact solution of the half-step subproblems in Dave's algorithm is not necessary. One iteration of Newton's method in each coordinate minimization half step yields a sequence obtained using the fuzzy c-shells algorithm with numerically exact coordinate minimization at each half step. It is shown that fuzzy c-shells generates hyperspherical prototypes to the clusters it finds for certain special cases of the measure of dissimilarity used.     

An adaptive multi-grid algorithm for the numerical solution of quasilinear potential equations

This paper describes an iterative method for the numerical solution of a class of quasilinear potential equations using an adaptive multi-grid algorithm (MG-algorithm). The method of solution has been illustrated using one iteration step of MG-cycle. The prolongation and restriction operators, which need coarse-to-fine as well as fine-to-coarse grid transfer, have been chosen of very simple linear structure. A simple error estimation has been carried out to show that the correction equation suggested in [2] has to be modified to get an efficient MG-algorithm. Another simple approach has been suggested which is based on a two-level version and uses a linear correction equation only on the coarser grid. We also present computational results of several numerical experiments applied on a specific example of the minimal surface problem. A comparison between our methods and other methods applied on the example of the minimal surface problem has been presented.     

A High Order Compact Time/Space Finite Difference Scheme for the Wave Equation with Variable Speed of Sound

We consider fourth order accurate compact schemes, in both space and time, for the second order wave equation with a variable speed of sound. We demonstrate that usually this is much more efficient than lower order schemes despite being implicit and only conditionally stable. Fast time marching of the implicit scheme is accomplished by iterative methods such as conjugate gradient and multigrid. For conjugate gradient, an upper bound on the convergence rate of the iterations is obtained by eigenvalue analysis of the scheme. The implicit discretization technique is such that the spatial and temporal convergence orders can be adjusted independently of each other. In special cases, the spatial error dominates the problem, and then an unconditionally stable second order accurate scheme in time with fourth order accuracy in space is more efficient. Computations confirm the design convergence rate for the inhomogeneous, variable wave speed equation and also confirm the pollution effect for these time dependent problems.