1,071 research outputs found
A Class of Preconditioners for Large Indefinite Linear Systems, as by-product of Krylov subspace Methods: Part II
Get PDFIn this paper we consider the parameter dependent class of preconditioners M(a,d,D) defined in the companion paper The latter was constructed by using information from a Krylov subspace method, adopted to solve the large symmetric linear system Ax = b. We first estimate the condition number of the preconditioned matrix M(a,d,D). Then our preconditioners, which are independent of the choice of the Krylov subspace method adopted, proved to be effective also when solving sequences of slowly changing linear systems, in unconstrained optimization and linear algebra frameworks. A numerical experience is provided to give evidence of the performance of M(a,d,D).preconditioners; large indefinite linear systems; large scale nonconvex optimization; Krylov subspace methods
Métodos de Krylov-Newton aplicados à simulação numérica de reservatórios de petróleo
Get PDFDissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico.A simulação do processo de extração de óleo em um reservatório de petróleo é um problema complexo que envolve o escoamento multifásico em um meio poroso de geometria arbitrária, podendo conter falhas geológicas e outras irregularidades. A modelagem numérica implícita deste problema requer a solução de um complexo sistema de equações não-lineares que pode ser resolvido de diversas formas, mais ou menos eficientes. A forma mais comum de solução deste sistema emprega o método de linearização de Newton ou alguma de suas variantes. O foco deste trabalho está na análise de uma extensa classe de métodos de Newton conhecidos como métodos de Newton inexatos. Estes métodos empregam um segundo método iterativo na solução da equação linearizada resolvendo-a até uma certa tolerância; daí serem chamados de inexatos. Os métodos inexatos abordados neste trabalho concentram-se na escolha de processos iterativos baseados em métodos de projeção no espaço de Krylov, tais como: GMRES, BICGSTAB, TFQMR. Estes métodos, que formam uma subclasse dos métodos de Newton inexatos, são conhecidos como métodos de Krylov-Newton. São abordados também métodos quase-newtonianos baseados na aproximação da matriz Jacobiana considerando apenas os termos ortogonais da discretização em sistemas curvilíneos não-ortogonais. Vários problemas com diferentes graus de não-ortogonalidade da malha e não-linearidades são resolvidos e comparados usando os diferentes métodos implementados
Compress-and-restart block Krylov subspace methods for Sylvester matrix equations
Get PDFBlock Krylov subspace methods (KSMs) comprise building blocks in many state-of-the-art solvers for large-scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well-explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs
Nonsymmetric Preconditioner Updates in Newton–Krylov Methods for Nonlinear Systems
No full textNewton–Krylov methods, a combination of Newton-like methods and Krylov sub-
space methods for solving the Newton equations, often need adequate preconditioning in order to be
successful. Approximations of the Jacobian matrices are required to form preconditioners, and this
step is very often the dominant cost of Newton–Krylov methods. Therefore, working with precon-
ditioners may destroy the “Jacobian-free” (or matrix-free) setting where the single Jacobian-vector
product can be provided without forming and storing the element of the true Jacobian. In this paper,
we propose and analyze a preconditioning technique for sequences of nonsymmetric Jacobian matri-
ces based on the update of an earlier preconditioner. The proposed strategy can be implemented in
a matrix-free manner. Numerical experiments on popular test problems confirm the effectiveness of
the approach in comparison with the standard ILU-preconditioned Newton–Krylov approaches
Weighted Quadrature In Krylov Methods
No full text. The Krylov subspace approximation techniques described by Gallopoulos and Saad [2] for the numerical solution of parabolic partial differential equations are extended. By combining the weighted quadrature methods of Lawson and Swayne [6] with Krylov subspace approximations, three major improvements are made. First, problems with time-dependent sources or boundary conditions may be solved more efficiently. Second, methods are derived which have the stability properties (such as A--stability) of the underlying rational approximation to the exponential function. Third, it is possible to present methods which are robust under space discretization refinement. In particular, a fixed precision is essentially maintained for the same time integration method and for constant values of the parameters, when the spatial resolution is increased. Key words. parabolic problems, Krylov subspace methods, weighted quadrature, exponential propagation, Arnoldi's method, superlinear convergence, stabilit..
Approximate Inverse Preconditioners for Krylov Methods on Heterogeneous Parallel Computers
No full textThe popularity of GPGPUs in high performance platforms for scientific
computing in recent times has renewed interest in approximate inverse preconditioners
for Krylov methods. We have recently introduced some new algorithmic
variants [6] of popular approximate inverse methods. We now report on the behaviour
of these variations in high performance multilevel preconditioning frameworks,
and we present the software framework that enable
Newton-Krylov-Schwarz Methods in CFD
No full textthis paper we examine how points (3) through (5) may be addressed through Newton-Krylov-Schwarz methods. Our point of view with respect to (1) is that there will usually be an asymptotic regime in which the power of Newton's method is desirable if the storage overhead is not too great. To connect the opening iterations to the asymptotic regime, polyalgorithmic linear solvers for the Newton corrections were shown to be desirable in, for instance, [8]. Regarding (2), we refer to [19] for recent developments. The last three considerations are the most important with respect to parallel CFD. For a variety of reasons, industrial CFD groups are inclining towards the distributed network computing environment characterized by coarse to medium granularity, large memory per node, and very high latency. The all-to-all data dependencies between the unknown fields in a fully implicit method have led to a resurgence of interest in less rapidly convergent methods in high-latency parallel environments. Resisting, we present related investigations that lie along the route to parallel implicit CFD. Sections x2 and x3 briefly review Newton-Krylov and Krylov-Schwarz domain decomposition methods, respectively. Numerical results on three model problems, each focusing on different parts of the overall development of parallel Newton-Krylov-Schwarz methods, are then presented in x4 through x6. It is our intention to bring these developments together in a Navier-Stokes code, as described in the conclusions. 2. Newton-Krylov Method
Krylov-Subspace Preconditioners for Discontinuous Galerkin Finite Element Methods
No full textStandard (conforming) finite element approximations of convection-dominated convection-diffusion problems often exhibit poor stability properties that manifest themselves as non-physical oscillations polluting the numerical solution. Various techniques have been proposed for the stabilisation of finite element methods (FEMs) for convection-diffusion problems, such as the popular streamline upwind Petrov-Galerkin (SUPG) method, and its variants. During the last decade, families of discontinuous Galerkin finite element methods (DGFEMs) have been proposed for the numerical solution of convection-diffusion problems, due to the many attractive properties they exhibit. In particular, DGFEMs admit good stability properties, they offer flexibility in the mesh design (irregular meshes are admissible) and in the imposition of boundary conditions (Dirichlet boundary conditions are weakly imposed), and they are increasingly popular in the context of hp-adaptive algorithms. The increase in popularity for DGFEMs has created a corresponding demand for developing corresponding linear solvers. This work aims to provide an overview of the current state of affairs in the solution of DGFEM-linear problems and present some recent results on the preconditioning of stiffness matrices arising from DGFEM discretisations of steady-state convection-diffusion boundary-value problems. More specifically, preconditioners are derived for which theoretical results indicate GMRES performance independent of discretisation parameters
Recommended from our members
Newton-Krylov methods applied to nonequilibrium radiation diffusion
Get PDFThe authors present results of applying a matrix-free Newton-Krylov method to a nonequilibrium radiation diffusion problem. Here, there is no use of operator splitting, and Newton`s method is used to convert the nonlinearities within a time step. Since the nonlinear residual is formed, it is used to monitor convergence. It is demonstrated that a simple Picard-based linearization produces a sufficient preconditioning matrix for the Krylov method, thus elevating the need to form or store a Jacobian matrix for Newton`s method. They discuss the possibility that the Newton-Krylov approach may allow larger time steps, without loss of accuracy, as compared to an operator split approach where nonlinearities are not converged within a time step
- …
