Incremental unknowns in three-dimensional stationary problem

The main purpose of this work is to set up the explicit matrix framework appropriate to three-dimensional partial differential equations by means of the incremental unknowns method. Multilevel schemes of the incremental unknowns are presented in the three space dimensions, and through numerical experiments, we confirm that the incremental unknowns method is efficient and the hierarchical preconditioning based on the incremental unknowns can be applied in a more general form.      

Incremental unknowns for solving partial differential equations

Summary Incremental unknowns have been proposed in [T] as a method to approximate fractal attractors by using finite difference approximations of evolution equations. In the case of linear elliptic problems, the utilization of incremental unknown methods provides a new way for solving such problems using several levels of discretization; the method is similar but different from the classical multigrid method.In this article we describe the application of incremental unknowns for solving Laplace equations in dimensions one and two. We provide theoretical results concerning two-level approximations and we report on numerical tests done with multi-level approximations.     

Bi-parameter incremental unknowns ADI iterative methods for elliptic problems

Bi-parameter incremental unknowns (IU) alternating directional implicit (ADI) iterative methods are proposed for solving elliptic problems. Condition numbers of the coefficient matrices for these iterative schemes are carefully estimated. Theoretical analysis shows that the condition numbers are reduced significantly by IU method, and the iterative sequences produced by the bi-parameter incremental unknowns ADI methods converge to the unique solution of the linear system if the two parameters belong to a given parameter region. Numerical examples are presented to illustrate the correctness of the theoretical analysis and the effectiveness of the bi-parameter incremental unknowns ADI methods.     

Incremental Unknowns Method for Solving Three-Dimensional Convection-Diffusion Equations

We use the incremental unknowns method in conjunction with the iterative methods to approximate the solution of the nonsymmetric and positive-definite linear systems generated from a multilevel discretization of three-dimensional convection-diffusion equations. The condition numbers of incremental unknowns matrices associated with the convection-diffusion equations and the number of iterations needed to attain an acceptable accuracy are estimated. Numerical results are presented with two-level approximations, which demonstrate that the incremental unknowns method when combined with some iter- ative methods is very effcient.     

Nonlinear Galerkin method in the finite difference case and wavelet-like incremental unknowns

Summary The IMG algorithm (Inertial Manifold-Multigrid algorithm) which uses the first-order incremental unknowns was introduced in [20]. The IMG algorithm is aimed at numerically implementing inertial manifolds (see e.g. [19]) when finite difference discretizations are used. For that purpose it is necessary to decompose the unknown function into its long wavelength and its short wavelength components; (first-order) Incremental Unknowns (IU) were proposed in [20] as a means to realize this decomposition. Our aim in the present article is to propose and study other forms of incremental unknowns, in particular the Wavelet-like Incremental Unknowns (WIU), so-called because of their oscillatory nature.In this report, we first extend the general convergence results in [20] by proving them under slightly weaker conditions. We then present three sets of incremental unknowns (i.e. the first-order as in [20], the second-order and wavelet-like incremental unknowns). We show that these incremental unknown can be used to construct convergent IMG algorithms. Special stress is put on the wavelet-like incremental unknowns since this set of unknowns has theL ² orthogonality property between different levels of unknowns and this should make them particularly appropriate for the approximation of evolution equations by inertial algorithms.     

Repeated Red-Black ordering: a new approach

Hereafter, we describe and analyze, from both a theoretical and a numerical point of view, an iterative method for efficiently solving symmetric elliptic problems with possibly discontinuous coefficients. In the following, we use the Preconditioned Conjugate Gradient method to solve the symmetric positive definite linear systems which arise from the finite element discretization of the problems. We focus our interest on sparse and efficient preconditioners. In order to define the preconditioners, we perform two steps: first we reorder the unknowns and then we carry out a (modified) incomplete factorization of the original matrix. We study numerically and theoretically two preconditioners, the second preconditioner corresponding to the one investigated by Brand and Heinemann [2]. We prove convergence results about the Poisson equation with either Dirichlet or periodic boundary conditions. For a meshsizeh, Brand proved that the condition number of the preconditioned system is bounded byO(h ^–1/2) for Dirichlet boundary conditions. By slightly modifying the preconditioning process, we prove that the condition number is bounded byO(h ^–1/3).     

An efficient linear solver for the hybridized discontinuous Galerkin method

Discretizing partial differential equations by an implicit solving technique ultimately leads to a linear system of equations that has to be solved. The number of globally coupled unknowns is especially large for discontinuous Galerkin (DG) methods. It can be reduced by using hybridized discontinuous Galerkin (HDG) methods, but still efficient linear solvers are needed. It has been shown that, if hierarchical basis functions are used, a hierarchical scale separation (HSS) ansatz can be an efficient solver. In this work, we couple the HDG method with an HSS solver to solve a scalar nonlinear problem. It is validated by comparing the results with results obtained by GMRES with ILU(3) preconditioning as linear solver. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

High Accuracy Solution of Three-Dimensional Biharmonic Equations

In this paper, we consider several finite-difference approximations for the three-dimensional biharmonic equation. A symbolic algebra package is utilized to derive a family of finite-difference approximations for the biharmonic equation on a 27 point compact stencil. The unknown solution and its first derivatives are carried as unknowns at selected grid points. This formulation allows us to incorporate the Dirichlet boundary conditions automatically and there is no need to define special formulas near the boundaries, as is the case with the standard discretizations of biharmonic equations. We exhibit the standard second-order, finite-difference approximation that requires 25 grid points. We also exhibit two compact formulations of the 3D biharmonic equations; these compact formulas are defined on a 27 point cubic grid. The fourth-order approximations are used to solve a set of test problems and produce high accuracy numerical solutions. The system of linear equations is solved using a variety of iterative methods. We employ multigrid and preconditioned Krylov iterative methods to solve the system of equations. Test results from two test problems are reported. In these experiments, the multigrid method gives excellent results. The multigrid preconditioning also gives good results using Krylov methods.     

A domain decomposition preconditioner for hermite collocation problems

We propose a preconditioning method for linear systems of equations arising from piecewise Hermite bicubic collocation applied to two‐dimensional elliptic PDEs with mixed boundary conditions. We construct an efficient, parallel preconditioner for the GMRES method. The main contribution of the article is a novel interface preconditioner derived in the framework of substructuring and employing a local Hermite collocation discretization for the interface subproblems based on a hybrid fine‐coarse mesh. Interface equations based on this mesh depend only weakly on unknowns associated with subdomains. The effectiveness of the proposed method is highlighted by numerical experiments that cover a variety of problems. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 135–151, 2003     

A comparison of preconditioned Krylov subspace methods for large‐scale nonsymmetric linear systems

Preconditioned Krylov subspace (KSP) methods are widely used for solving large‐scale sparse linear systems arising from numerical solutions of partial differential equations (PDEs). These linear systems are often nonsymmetric due to the nature of the PDEs, boundary or jump conditions, or discretization methods. While implementations of preconditioned KSP methods are usually readily available, it is unclear to users which methods are the best for different classes of problems. In this work, we present a comparison of some KSP methods, including GMRES, TFQMR, BiCGSTAB, and QMRCGSTAB, coupled with three classes of preconditioners, namely, Gauss–Seidel, incomplete LU factorization (including ILUT, ILUTP, and multilevel ILU), and algebraic multigrid (including BoomerAMG and ML). Theoretically, we compare the mathematical formulations and operation counts of these methods. Empirically, we compare the convergence and serial performance for a range of benchmark problems from numerical PDEs in two and three dimensions with up to millions of unknowns and also assess the asymptotic complexity of the methods as the number of unknowns increases. Our results show that GMRES tends to deliver better performance when coupled with an effective multigrid preconditioner, but it is less competitive with an ineffective preconditioner due to restarts. BoomerAMG with a proper choice of coarsening and interpolation techniques typically converges faster than ML, but both may fail for ill‐conditioned or saddle‐point problems, whereas multilevel ILU tends to succeed. We also show that right preconditioning is more desirable. This study helps establish some practical guidelines for choosing preconditioned KSP methods and motivates the development of more effective preconditioners.     

一类多维非线性反应扩散方程有限差分格式的稳定性问题(英文)

本文研究了一类多维线性反应扩散方程差分格式的稳定性.利用量未知元方法,建立了具有增量未知元的有限差分格式;然后利用非线性Galerkin方法,得到该差分格式的稳定性条件.通过对该格式的稳定性分析,说明和经典的差分格式的稳定性相比较,带有增量未知元的有限差分格式的稳定性得到了提高.     

A supernodal block factorized sparse approximate inverse for non-symmetric linear systems

The concept of supernodes, originally developed to accelerate direct solution methods for linear systems, is generalized to block factorized sparse approximate inverse (Block FSAI) preconditioning of non-symmetric linear systems. It is shown that aggregating the unknowns in clusters that are processed together is particularly useful both to reduce the cost for the preconditioner setup and accelerate the convergence of the iterative solver. A set of numerical experiments performed on matrices arising from the meshfree discretization of 2D and 3D potential problems, where a very large number of nodal contacts is usually found, shows that the supernodal Block FSAI preconditioner outperforms the native algorithm and exhibits a much more stable behavior with respect to the variation of the user-specified parameters.     

Preconditioning analysis of the one dimensional incremental unknowns method on nonuniform meshes

The condition number of the incremental unknowns matrix on nonuniform meshes associated to the elliptic problem is analyzed. Comparing to the usual nodal unknowns matrix, the condition number of the incremental unknowns matrix is reduced significantly even if the meshes are nonuniform. Furthermore, if a diagonal scaling is used, the condition number of the preconditioned incremental unknowns matrix comes out to be O(1). Numerical experiments are performed respectively on Shishkin mesh and Chebyshev mesh. Computational results with respect to the two particular nonuniform meshes confirm our theoretical analysis.     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

Uzawa block relaxation method for the unilateral contact problem

We present a Uzawa block relaxation method for the numerical resolution of contact problems with or without friction, between elastic solids in small deformations. We introduce auxiliary unknowns to separate the linear elasticity subproblem from the unilateral contact and friction conditions. Applying a Uzawa block relaxation method to the corresponding augmented Lagrangian functional yields a two-step iterative method with a linear elasticity problem as a main subproblem while auxiliary unknowns are computed explicitly. Numerical experiments show that the method are robust and scalable with a significant saving of computational time.     

Convergence of a substructuring method with Lagrange multipliers

Summary. We analyze the convergence of a substructuring iterative method with Lagrange multipliers, proposed recently by Farhat and Roux. The method decomposes finite element discretization of an elliptic boundary value problem into Neumann problems on the subdomains plus a coarse problem for the subdomain nullspace components. For linear conforming elements and preconditioning by the Dirichlet problems on the subdomains, we prove the asymptotic bound on the condition number , or ,where is the characteristic element size and subdomain size. Received January 3, 1995     

A generalized preconditioned HSS method for non-Hermitian positive definite linear systems

Based on the HSS (Hermitian and skew-Hermitian splitting) and preconditioned HSS methods, we will present a generalized preconditioned HSS method for the large sparse non-Hermitian positive definite linear system. Our method is essentially a two-parameter iteration which can extend the possibility to optimize the iterative process. The iterative sequence produced by our generalized preconditioned HSS method can be proven to be convergent to the unique solution of the linear system. An exact parameter region of convergence for the method is strictly proved. A minimum value for the upper bound of the iterative spectrum is derived, which is relevant to the eigensystem of the products formed by inverse preconditioner and splitting. An efficient preconditioner based on incremental unknowns is presented for the actual implementation of the new method. The optimality and efficiency are effectively testified by some comparisons with numerical results.     

提高反应—扩散方程有限差分格式的稳定性问题

This paper deals with the special nonlinear reaction-diffusion equation.The finite difference scheme with incremental unknowns approximating to the differential equation (2.1) is set up by means of introducing incremental unknowns methods.Through the stability analyzing for the scheme,it was shown that the stability conditions of the finite difference schemes with the incremental unknowns are greatly improved when compared with the stability conditions of the corresponding classic difference scheme.     

The Generalization Paradox of Ensembles

Deconvolution is usually regarded as one of the ill-posed problems in applied mathematics if no constraints on the unknowns are assumed. This article discusses the idea of well-defined statistical models being a counterpart of the notion of well-posedness. We show that constraints on the unknowns such as positivity and sparsity can go a long way towards overcoming the ill-posedness in deconvolution. We show how these issues are dealt with in a parametric deconvolution model introduced recently. From the same perspective we take a fresh look at two familiar deconvolvers: the widely used Jansson method and another one that minimizes the Kullback-Leibler divergence between observations and fitted values. In the latter case, we point out that in the context of deconvolution and the general linear inverse problems with positivity contraints, a counterpart of the EM algorithm exists for the problem of minimizing the Kullback-Leibler divergence. We graphically compare the performance of these deconvolvers using data simulated from a spike-convolution model and DNA sequencing data.