Efficient solution of two-sided nonlinear space-fractional diffusion equations using fast Poisson preconditioners

We develop a fast Poisson preconditioner for the efficient numerical solution of a class of two-sided nonlinear space fractional diffusion equations in one and two dimensions using the method of lines. Using the shifted Gr¨unwald finite difference formulas to approximate the two-sided(i.e. the left and right Riemann-Liouville) fractional derivatives, the resulting semi-discrete nonlinear systems have dense Jacobian matrices owing to the non-local property of fractional derivatives. We employ a modern initial value problem solver utilising backward differentiation formulas and Jacobian-free Newton-Krylov methods to solve these systems. For efficient performance of the Jacobianfree Newton-Krylov method it is essential to apply an effective preconditioner to accelerate the convergence of the linear iterative solver. The key contribution of our work is to generalise the fast Poisson preconditioner, widely used for integer-order diffusion equations, so that it applies to the two-sided space fractional diffusion equation. A number of numerical experiments are presented to demonstrate the effectiveness of the preconditioner and the overall solution strategy.

On Nonlinear Preconditioners in Newton-Krylov-Methods for Unsteady Flows

The application of nonlinear schemes like dual time stepping as preconditioners in matrix-free Newton-Krylov-solvers is considered and analyzed. We provide a novel formulation of the left preconditioned operator that says it is in fact linear in the matrix-free sense, but changes the Newton scheme. This allows to get some insight in the convergence properties of these schemes which are demonstrated through numerical results.

Approximate factorization constraint preconditioners for saddle-point matrices

We consider the application of the conjugate gradient method to the solution of large, symmetric indefinite linear systems. Special emphasis is put on the use of constraint preconditioners and a new factorization that can reduce the number of flops required by the preconditioning step. Results concerning the eigenvalues of the preconditioned matrix and its minimum polynomial are given. Numerical experiments validate these conclusions.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

Two-Level Schwarz Preconditioners for Super Penalty Discontinuous Galerkin Methods

We extend the construction and analysis of the non-overlapping Schwarz preconditioners proposed in Antonietti et al. [Math. Model. Numer. Anal., 41(1):21-54, 2007] and [Math. Model. Numer. Anal., submitted, 2006] to the (non-consistent) super penalty discontinuos Galerkin methods introduced by Babuska et al. [SIAM J. Numer. Anal., 10:863-875, 1973] and by Brezzi et al. [Numer. Methods Partial Differential Equations, 16(4):365-378, 2000]. We show that the resulting preconditioners are scalable, and we provide the convergence estimates. We also present numerical experiments demonstrating the theoretical results.

A class of domain decomposition preconditioners for hp-discontinuous Galerkin finite element methods

In this article we address the question of efficiently solving the algebraic linear system of equations arising from the discretization of a symmetric, elliptic boundary value problem using hp-version discontinuous Galerkin finite element methods. In particular, we introduce a class of domain decomposition preconditioners based on the Schwarz framework, and prove bounds on the condition number of the resulting iteration operators. Numerical results confirming the theoretical estimates are also presented.

Computational strategies for surface fitting using thin plate spline finite element methods

Thin plate spline finite element methods are used to fit a surface to an irregularly scattered dataset [S. Roberts, M. Hegland, and I. Altas. Approximation of a Thin Plate Spline Smoother using Continuous Piecewise Polynomial Functions. SIAM, 1:208--234, 2003]. The computational bottleneck for this algorithm is the solution of large, ill-conditioned systems of linear equations at each step of a generalised cross validation algorithm. Preconditioning techniques are investigated to accelerate the convergence of the solution of these systems using Krylov subspace methods. The preconditioners under consideration are block diagonal, block triangular and constraint preconditioners [M. Benzi, G. H. Golub, and J. Liesen. Numerical solution of saddle point problems. Acta Numer., 14:1--137, 2005]. The effectiveness of each of these preconditioners is examined on a sample dataset taken from a known surface. From our numerical investigation, constraint preconditioners appear to provide improved convergence for this surface fitting problem compared to block preconditioners.

Precondicionadores baseados na aproximação da inversa.

Neste trabalho de dissertação apresentaremos uma classe de precondicionadores baseados na aproximação esparsa da inversa da matriz de coecientes, para a resolução de sistemas lineares esparsos de grandes portes através de métodos iterativos, mais especificamente métodos de Krylov. Para que um método de Krylov seja eficiente é extremamente necessário o uso de precondicionadores. No contexto atual, onde computadores de arquitetura híbrida são cada vez mais comuns temos uma demanda cada vez maior por precondicionadores paralelizáveis. Os métodos de inversa aproximada que serão descritos possuem aplicação paralela, pois so dependem de uma operação de produto matriz-vetor, que é altamente paralelizável. Além disso, alguns dos métodos também podem ser construídos em paralelo. A ideia principal é apresentar uma alternativa aos tradicionais precondicionadores que utilizam aproximações dos fatores LU, que apesar de robustos são de difícil paralelização.

ω循环型预条件矩阵及其应用

In this paper, we apply the preconditioned conjugate gradient method to the solution of positive-definite Toeplitz systems, especially we introduce a new kind of co-circulant preconditioners Pn[ca] by the use of embedding method. We have also discussed the properties of these new preconditioners and proved that many of former preconditioners can be considered as some special cases of Pn[co\. Because of the introduction of co-circulant preconditioners pn[a>], we can greatly overcome the singularity caused by circulant preconditioners. We have discussed the oo-circulant series and functions. We compare the ordinary circularity with the co-circularity, showing that the latter one can be considered as the extended form of the former one; correspondingly, many methods and theorems of the ordinary circularity can be extended. Furthermore, we present the co-circulant decompositional method. By the use of this method, we can divide any co-circulant signal into a summation of many sub-signals; especially among those sub-signals, there are many subseries of which their period is just equal to 1, which are actually the frequency elements of the original co-circulant signal. In this way, we can establish the relationship between the signal and its frequency elements, that is, the frequency elements hi the frequency domain are actually signals with the period of 1 in the spatial domain. We have also proved that the co-circulant has already existed in the traditional Fourier theory. By the use of different criteria for constructing preconditioners, we can get many different preconditioned systems. From the preconditioned systems PN[

Numerical experiments of some Krylov subspace methods for black oil model

This paper discusses preconditioned Krylov subspace methods for solving large scale linear systems that originate from oil reservoir numerical simulations. Two types of preconditioners, one being based on an incomplete LU decomposition and the other being based on iterative algorithms, are used together in a combination strategy in order to achieve an adaptive and efficient preconditioner. Numerical tests show that different Krylov subspace methods combining with appropriate preconditioners are able to achieve optimal performance.

Preconditioner updates applied to CFD model problems

In the present paper we concentrate on solving sequences of nonsymmetric linear systems with block structure arising from compressible flow problems. We attempt to improve the solution process by sharing part of the computational effort throughout the sequence. This is achieved by application of a cheap updating technique for preconditioners which we adapted in order to be used for our applications. Tested on three benchmark compressible flow problems, the strategy speeds up the entire computation with an acceleration being particularly pronounced in phases of instationary behavior.