On a posteriori estimates of inverse operators for linear parabolic initial-boundary value problems

We present numerically verified a posteriori estimates of the norms of inverse operators for linear parabolic differential equations. In case that the corresponding elliptic operator is not coercive, existing methods for a priori estimates of the inverse operators are not accurate and, usually, exponentially increase in time variable. We propose a new technique for obtaining the estimates of the inverse operator by using the finite dimensional approximation and error estimates. It enables us to obtain very sharp bounds compared with a priori estimates. We will give some numerical examples which confirm the actual effectiveness of our method.     

Monotonie- und Randmaximumsätze bei Diskretisierungen des Dirichletproblems allgemeiner nichtlinearer elliptischer Differentialgleichungen

In this paper we consider finite difference operators which approximate the dirichlet problem of general nonlinear elliptic equations. For such nonlinear operators we give several criteria which insure the validity of an discrete monotonicity and maximum principle. In the case of linear difference operators one of these criteria is known as a necessary and sufficient condition.     

Massively parallel methods for semiconductor device modelling

In this paper we describe, analyse and implement a parallel iterative method for the solution of the steady-state drift diffusion equations governing the behaviour of a semiconductor device in two space dimensions. The unknowns in our model are the electrostatic potential and the electron and hole quasi-Fermi potentials. Our discretisation consists of a finite element method with mass lumping for the electrostatic potential equation and a hybrid finite element with local current conservation properties for the continuity equations. A version of Gummel's decoupling algorithm which only requires the solution of positive definite symmetric linear systems is used to solve the resulting nonlinear equations. We show that this method has an overall rate of convergence which only degrades logarithmically as the mesh is refined. Indeed the (inner) nonlinear solves of the electrostatic potential equation converge quadratically, with a mesh independent asymptotic constant. We also describe an implementation on a MasPar MP-1 data parallel machine, where the required linear systems are solved by the preconditioned conjugate gradient method. Domain decomposition methods are used to parallelise the required matrix-vector multiplications and to build preconditioners for these very poorly-conditioned systems. Our preconditioned linear solves also have a rate of convergence which degrades logarithmically as the grid is refined relative to subdomain size, and their performance is resilient to the severe layers which arise in the coefficients of the underlying elliptic operators. Parallel experiments are given.     

Wei–Yao–Liu conjugate gradient projection algorithm for nonlinear monotone equations with convex constraints

In this paper, the Wei–Yao–Liu (WYL) conjugate gradient projection algorithm will be studied for nonlinear monotone equations with convex constraints, which can be viewed as an extension of the WYL conjugate gradient method for solving unconstrained optimization problems. These methods can be applied to solving large-scale nonlinear equations due to the low storage requirement. We can obtain global convergence of our algorithm without requiring differentiability in the case that the equation is Lipschitz continuous. The numerical results show that the new algorithm is efficient.     

Solving large elliptic difference equations on CYBER 205

Preconditioned conjugate gradient methods are considered for the solution of large elliptic difference equations on the CYBER 205 computer. An approximate polynomial preconditioning procedure is introduced for systems of equations derived from high-order numerical approximations to elliptic partial differential equations. Computational results for high-order versus low-order methods are presented, and the comparison of the conjugate gradient method used in conjunction with various preconditioning shows the new preconditioning strategy to be very effective for solving algebraic equations that arise from high-order discretization techniques.     

A projection method for solving nonsymmetric linear systems on multiprocessors

We consider the iterative solution of large sparse linear systems of equations arising from elliptic and parabolic partial differential equations in two or three space dimensions. Specifically, we focus our attention on nonsymmetric systems of equations whose eigenvalues lie on both sides of the imaginary axis, or whose symmetric part is not positive definite. This system of equation is solved using a block Kaczmarz projection method with conjugate gradient acceleration. The algorithm has been designed with special emphasis on its suitability for multiprocessors. In the first part of the paper, we study the numerical properties of the algorithm and compare its performance with other algorithms such as the conjugate gradient method on the normal equations, and conjugate gradient-like schemes such as ORTHOMIN(k), GCR(k) and GMRES(k). We also study the effect of using various preconditioners with these methods. In the second part of the paper, we describe the implementation of our algorithm on the CRAY X-MP/48 multiprocessor, and study its behavior as the number of processors is increased.     

An incomplete factorization iterative technique for elliptic equations

This paper describes efficient iterative techniques for solving the large sparse symmetric linear systems that arise from application of finite difference approximations to self-adjoint elliptic equations. We use an incomplete factorization technique with the method of D'Yakonov type, generalized conjugate gradient and Chebyshev semi-iterative methods. We compare these methods with numerical examples. Bounds for the 4-norm of the error vector of the Chebyshev semi-iterative method in terms of the spectral radius of the iteration matrix are derived.     

A numerical investigation on the interplay amongst geometry, meshes, and linear algebra in the finite element solution of elliptic PDEs

In this paper, we study the effect of the choice of mesh quality metric, preconditioner, and sparse linear solver on the numerical solution of elliptic partial differential equations (PDEs). We smooth meshes on several geometric domains using various quality metrics and solve the associated elliptic PDEs using the finite element method. The resulting linear systems are solved using various combinations of preconditioners and sparse linear solvers. We use the inverse mean ratio and radius ratio metrics in addition to conditioning-based scale-invariant and interpolation-based size-and-shape metrics. We employ the Jacobi, SSOR, incomplete LU, and algebraic multigrid preconditioners and the conjugate gradient, minimum residual, generalized minimum residual, and bi-conjugate gradient stabilized solvers. We focus on determining the most efficient quality metric, preconditioner, and linear solver combination for the numerical solution of various elliptic PDEs with isotropic coefficients. We also investigate the effect of vertex perturbation and the effect of increasing the problem size on the number of iterations required to converge and on the solver time. In this paper, we consider Poisson’s equation, general second-order elliptic PDEs, and linear elasticity problems.     

Conjugate gradient algorithms in the solution of optimization problems for nonlinear elliptic partial differential equations

Several variants of the conjugate gradient algorithm are discussed with emphasis on determining the parameters without performing line searches and on using splitting techniques to accelerate convergence. The splittings used here are related to the nonlinear SSOR algorithm. The behavior of the methods is illustrated on a discretization of a nonlinear elliptic partial differential boundary value problem, the minimal surface equation. A conjugate gradient algorithm with splittings is also developed for constrained minimization with upper and lower bounds on the variables, and the method is applied to the obstacle problem for the minimal surface equation.     

非线性预处理共轭斜量法

我们以Engli(1959)的线性方法为基础,构造出一个极小化一般非线性目标函数(3)的非线性预处理共轭斜量法:     

The use of matrix visualization in algorithmic design

The use of matrix visualization in the design and development of numerical algorithms for supercomputers is discussed. Using color computer graphics, numerical analysts can gain new insights into algorithm behavior, which can then be used to design more efficient (parallel) numerical algorithms. The application of a matrix visualization tool, MatVu, in the design of algorithms from numerical linear algebra is the primary focus. Specific examples include the derivation of optimal preconditioning matrices for a conjugate gradient method, the design of parallel hybrid algorithms for solving the symmetric eigenvalue problem, the effects of operator splitting in the solution of incompressible Navier-Stokes equations, and the monitoring of Jacobian matrices associated with the application of Newton's method to a corresponding nonlinear system of equations.     

Vectorizable preconditioners for mixed finite element solution of second-order elliptic problems

We compare the performance of the CG (conjugate gradient) method, the point-wise incomplete factorization preconditioned CG method, and the block-incomplete factorization preconditioned CG method for solving problems arising in mixed finite element discretization of second order elliptic differential equations. The robustness and vectorizable properties of these methods are illustrated by a large set of numerical tests.     

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.     

Use of fast direct methods for mildly nonlinear elliptic difference equations

We consider in a rectangle the dirichelet mildly nonlinear elliptic boundary value problem. The numerical solution by finite-difference equations leads to the problem of solving special nonlinear systems. We propose a numerical technique founded on the application of a fast double-sweep method to the linear system induced by modified Picard iteration. Computer results are given and a comparison is made with other methods which illustrate the effectiveness of the method.     

基于GPU-CUDA的共轭斜量法实现及性能对比

偏微分方程数值解法(包括有限差分法、有限元法)以及大量的数学物理方程数值解法最终都会演变成求解大型线性方程组。因此,探讨快速、稳定、精确的大型线性方程组解法一直是数值计算领域不断深入研究的课题且具有特别重要的意义。在迭代法中,共轭斜量法(又称共轭梯度法)被公认为最好的方法之一。但是,该方法最大缺点是仅适用于线性方程组系数矩阵为对称正定矩阵的情况,而且常规的CPU算法实现非常耗时。为此,通过将线性方程组系数矩阵作转换成对称矩阵后实施基于GPU-CUDA的快速共轭斜量法来解决一般性大型线性方程组的求解问题。试验结果表明:在求解效率方面,基于GPU-CUDA的共轭斜量法运行效率高,当线性方程组阶数超过3000时,其加速比将超过14;在解的精确性与求解过程的稳定性方面,与高斯列主元消去法相当。基于GPU-CUDA的快速共轭斜量法是求解一般性大型线性方程组快速而非常有效的方法。     

Enclosing the solutions of nonlinear systems of equations

The quadratically convergent Newton-type methods and its variants are generally used for solving the nonlinear systems of equations. Most of these methods use the convexity conditions [7] of the involved bounded linear operators for their convergence. Alefeld and Herzberger [1] have proposed a quadratically convergent iterative method for enclosing the solutions of the special type of nonlinear system of equations arising from the discretization of nonlinear boundary value problems which do not require the convexity conditions but uses the subinverses of the bounded linear operators. In this paper, we have proposed a modification of this method which takes it further faster. The proposed method uses bom the superinverses and subinverses of bounded linear operators. At the expense of slightly more computations than used in [1], the rate of convergence of our method enhances from quadratic to cubic. Finally, the method is tested on a numerical example.     

A generalized mean intensity approach for the numerical solution of the radiative transfer equation

In [7] we proposed a general numerical approach to the (linear) radiative transfer equation which resulted in a high-dimensional linear system of equations. Using the concept of the generalized mean intensity, the dimension of the system can be drastically diminished, without losing any information. Additionally, the corresponding system matrices are positive definite under appropriate conditions on the choice of the discrete ordinates and, therefore, the classical conjugate gradient-iteration (CG) is converging. In connection with local preconditioners, we develop robust and efficient methods of conjugate gradient type which are superior to the classical approximate Λ-iteration, but with about the same numerical effort. For some numerical tests, which simulate the astrophysically interesting case of radiation of stars in dust clouds, we compare the methods derived and give some examples for their efficiency.     

Parallel nonlinear preconditioners on multicore architectures

Parallel nonlinear preconditioners, for solving mildly nonlinear systems, are proposed. These algorithms are based on both the Fletcher–Reeves version of the nonlinear conjugate gradient method and a polynomial preconditioner type based on block two-stage methods. The behavior of these algorithms is analyzed when incomplete LU factorizations are used in order to obtain the inner splittings of the block two-stage method. As our illustrative example we have considered a nonlinear elliptic partial differential equation, known as the Bratu problem. The reported experiments show the performance of the algorithms designed in this work on two multicore architectures.     

Partially symmetrical derivative-free Liu–Storey projection method for convex constrained equations

ABSTRACT

Applying Powell symmetrical technique to the Liu–Storey conjugate gradient method, a partially symmetrical Liu–Storey conjugate gradient method is proposed and extended to solve nonlinear monotone equations with convex constraints, which satisfies the sufficient descent condition without any line search. By using some line searches, the global convergence is proved merely by assuming that the equations are Lipschitz continuous. Moreover, we prove the R-linear convergence rate of the proposed method with an additional assumption. Finally, compared with one existing method, the performance of the proposed method is showed by some numerical experiments on the given test problems.