Preconditioned iterative algorithms for large sparse unsymmetric problems

A numerical study of the efficiency of the generalized conjugate residual methods (GCR) is performed using three different preconditioners all based upon an incomplete LU factorization. The GCR behavior is evaluated in connection with the solution of large, sparse unsymmetric systems of equations, arising from the finite element integration of the diffusion-convection equation for 2-dimensional (2-D) and 3-D problems with different Peclet and Courant numbers. The order of the test matrices ranges from 450 to 1700. Results from a set of numerical experiments are presented and comparisons with preconditioned GCR methods and with direct method are carried out.     

Preconditioned iterative methods for fractional diffusion models in finance

Most recent qualitative models for financial assets assume that the dynamics of underlying equity prices follows a jump or Lévy process. It has been evident that some most intricate characteristics of such dynamics can be captured by CGMY and KoBoL procedures. The prices of financial derivatives with such models satisfy fractional partial differential equations or partial integro‐differential equations. This study focuses at aforementioned fractional equations and discretizes them via a monotone Crank–Nicolson procedure. A spatial extrapolation strategy is introduced to ensure an overall second‐order accuracy in approximations. Preconditioned conjugate gradient normal residual methods are incorporated for solving resulted linear systems. Numerical examples are given to illustrate the accuracy and efficiency of the novel computational approaches implemented. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1382–1395, 2015     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

Preconditioned iterative methods for coupled discretizations of fluid flow problems

Computational fluid dynamics, where simulations require largecomputation times, is one of the areas of application of highperformance computing. Schemes such as the SIMPLE (semi-implicitmethod for pressure-linked equations) algorithm are often usedto solve the discrete Navier-Stokes equations. Generally theseschemes take a short time per iteration but require a largenumber of iterations. For simple geometries (or coarser grids)the overall CPU time is small. However, for finer grids or morecomplex geometries the increase in the number of iterationsmay be a drawback and the decoupling of the differential equationsinvolved implies a slow convergence of rotationally dominatedproblems that can be very time consuming for realistic applications.So we analyze here another approach, DIRECTO, that solves theequations in a coupled way. With recent advances in hardwaretechnology and software design, it became possible to solvecoupled Navier-Stokes systems, which are more robust but implyincreasing computational requirements (both in terms of memoryand CPU time). Two approaches are described here (band blockLU factorization and preconditioned GMRES) for the linear solverrequired by the DIRECTO algorithm that solves the fluid flowequations as a coupled system. Comparisons of the effectivenessof incomplete factorization preconditioners applied to the GMRES(generalized minimum residual) method are shown. Some numericalresults are presented showing that it is possible to minimizeconsiderably the CPU time of the coupled approach so that itcan be faster than the decoupled one.     

关于鞍点问题的预处理HSS-SOR交替分裂迭代方法

为了高效地求解大型稀疏鞍点问题,在白中治,Golub和潘建瑜提出的预处理对称/反对称分裂(PHss)迭代法的基础上,通过结合SOR-like迭代格式对原有迭代算法进行加速,提出了一种预处理HSS-SOR交替分裂迭代方法,并研究了该算法的收敛性.数值例子表明:通过参数值的选择,新算法比SOR-like和PHSS算法都具有更快的收敛速度和更少的迭代次数,选择了合适的参数值后,可以提高算法的收敛效率.     

Preconditioned iterative methods for diffusion problems with high‐contrast inclusions

This paper is concerned with robust numerical treatment of an elliptic PDE with high‐contrast coefficients, for which classical finite‐element discretizations yield ill‐conditioned linear systems. This paper introduces a procedure by which the discrete system obtained from a linear finite element discretization of the given continuum problem is converted into an equivalent linear system of the saddle‐point type. Three preconditioned iterative procedures—preconditioned Uzawa, preconditioned Lanczos, and preconditioned conjugate gradient for the square of the matrix—are discussed for a special type of the application, namely, highly conducting particles distributed in the domain. Robust preconditioners for solving the derived saddle‐point problem are proposed and investigated. Robustness with respect to the contrast parameter and the discretization scale is also justified. Numerical examples support theoretical results and demonstrate independence of the number of iterations of the proposed iterative schemes on the contrast in parameters of the problem and the mesh size.     

Preconditioned iterative regularization in Banach spaces

Regularization methods for inverse problems formulated in Hilbert spaces usually give rise to over-smoothness, which does not allow to obtain a good contrast and localization of the edges in the context of image restoration. On the other hand, regularization methods recently introduced in Banach spaces allow in general to obtain better localization and restoration of the discontinuities or localized impulsive signals in imaging applications. We present here an expository survey of the topic focused on the iterative Landweber method. In addition, preconditioning techniques previously proposed for Hilbert spaces are extended to the Banach setting and numerically tested.     

Preconditioned GMRES methods with incomplete Givens orthogonalization method for large sparse least-squares problems

We propose to precondition the GMRES method by using the incomplete Givens orthogonalization (IGO) method for the solution of large sparse linear least-squares problems. Theoretical analysis shows that the preconditioner satisfies the sufficient condition that can guarantee that the preconditioned GMRES method will never break down and always give the least-squares solution of the original problem. Numerical experiments further confirm that the new preconditioner is efficient. We also find that the IGO preconditioned BA-GMRES method is superior to the corresponding CGLS method for ill-conditioned and singular least-squares problems.     

Preconditioned iterative methods for linear discrete ill-posed problems from a Bayesian inversion perspective

In this paper we revisit the solution of ill-posed problems by preconditioned iterative methods from a Bayesian statistical inversion perspective. After a brief review of the most popular Krylov subspace iterative methods for the solution of linear discrete ill-posed problems and some basic statistics results, we analyze the statistical meaning of left and right preconditioners, as well as projected-restarted strategies. Computed examples illustrating the interplay between statistics and preconditioning are also presented.     

Convergence of block iterative methods applied to sparse least-squares problems

Recently, special attention has been given, in the mathematical literature, to the problems of accurately computing the least-squares solutions of very large-scale overdetermined systems of linear equations, such as those arising in geodetical network problems. In particular, it has been suggested that one solve such problems, iteratively by applying the block-SOR (successive overrelaxation) iterative method to a consistently ordered block-Jacobi matrix that is weakly cyclic of index 3. Here, we obtain new results (Theorem 1), giving the exact convergence and divergence domains for such iterative applications. It is then shown how these results extend, and correct, the literature on such applications. In addition, analogous results (Theorem 2) are given for the case when the eigenvalues of the associated block-Jacobi matrix are nonnegative.     

Robust expansion of subspaces in iterative projection methods for large eigenvalue problems

The Jacobi–Davidson method is known to converge at least quadratically if the correction equation is solved exactly, and it is common experience that the fast convergence is maintained if the correction equation is solved only approximately. Here we derive the Jacobi–Davidson method in a way that explains this robust behavior. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Preconditioned low-order Newton methods

In this paper, low-order Newton methods are proposed that make use of previously obtained second-derivative information by suitable preconditioning. When applied to a particular 2-dimensional Newton method (the LS method), it is shown that a member of the Broyden family of quasi-Newton methods is obtained. Algorithms based on this preconditioned LS model are tested against some variations of the BFGS method and shown to be much superior in terms of number of iterations and function evaluations, but not so effective in terms of number of gradient evaluations.     

Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations

The finite difference or the finite element discretizations of many differential or integral equations often result in a class of systems of weakly nonlinear equations. In this paper, by reasonably applying both the multisplitting and the two-stage iteration techniques, and in accordance with the special properties of this system of weakly nonlinear equations, we first propose a general multisplitting two-stage iteration method through the two-stage multiple splittings of the system matrix. Then, by applying the accelerated overrelaxation (AOR) technique of the linear iterative methods, we present a multisplitting two-stage AOR method, which particularly uses the AOR-like iteration as inner iteration and is substantially a relaxed variant of the afore-presented method. These two methods have a forceful parallel computing function and are much more suitable to the high-speed multiprocessor systems. For these two classes of methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some suitable assumptions when the involved nonlinear mapping is only directionally differentiable. When the system matrix is either an H-matrix or a monotone matrix, and the nonlinear mapping is a P-bounded mapping, we thoroughly set up the global convergence theories of these new methods. Moreover, under the assumptions that the system matrix is monotone and the nonlinear mapping is isotone, we discuss the monotone convergence properties of the new multisplitting two-stage iteration methods, and investigate the influence of the multiple splittings as well as the relaxation parameters upon the convergence behaviours of these methods. Numerical computations show that our new methods are feasible and efficient for parallel solving of the system of weakly nonlinear equations. This revised version was published online in August 2006 with corrections to the Cover Date.     

On iterative refinements for spectral sets and spectral subspaces

Stewart (1971) and Demmel (1987) have proposed iterative procedures for refining invariant subspaces of Hilbert space operators and matrices respectively. In this paper, modifications are proposed for these procedures which facilitates their application to bounded Banach space operators. Under regularity conditions (which could include densely defined closed operators) it is shown that the modifications perform as well as or better than the procedures of Stewart and Demmel.     

ILU++: A new software package for solving sparse linear systems with iterative methods

ILU++ is a software package for solving sparse linear systems with iterative methods using state-of-the-art incomplete multilevel LU-factorisations as preconditioners. It implements several types of preprocessing (permuting and scaling both rows and columns prior to factorisation to make the matrix more suitable for LU-factorisation), different pivoting strategies and a number of dropping rules to ensure sparsity. ILU++ is available under the GNU public licence. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Preconditioned sor methods for generalized least-squares problems

1.IntroductionThegeneralizedleastsquaresproblem,definedasmin(Ax--b)"W--'(Ax--b),(1.1)xacwhereAERm",m>n,bERm,andWERm'misasymmetricandpositivedefinitematrix,isfrequentlyfoundwhensolvingproblemsinstatistics,engineeringandeconomics.Forexample,wegetgeneralizedleastsquaresproblemswhensolvingnonlinearregressionanalysisbyquasi-likelihoodestimation,imagereconstructionproblemsandeconomicmodelsobtainedbythemaximumlikelihoodmethod(of.[1,21).Paige[3,4]investigatestheproblemexplicitly.Hechangestheorig…     

Biconjugate direction methods in Krylov subspaces

The paper addresses the orthogonal and variational properties of a family of iterative algorithms in Krylov subspaces for solving the systems of linear algebraic equations (SLAE) with sparse nonsymmetric matrices. There are proposed and studied a biconjugate residual method, squared biconjugate residual method, and stabilized conjugate residual method. Some results of numerical experiments are given for a series of model problems as well.     

求解分布控制问题的预处理最小残量方法(英文)

通过分析Bai(Bai Z Z.Block preconditioners for elliptic PDE-constrained optimization problems.Computing,2011,91:379-395)给出的离散分布控制问题的块反对角预处理线性系统,提出了该问题的一个等价线性系统,并且运用带有预处理子的最小残量方法对该系统进行求解.理论分析和数值实验结果表明,所提出的预处理最小残量方法对于求解该类椭圆型偏微分方程约束最优分布控制问题非常有效,尤其当正则参数适当小的时候.     

Asynchronous two-stage iterative methods

Summary. Parallel block two-stage iterative methods for the solution of linear systems of algebraic equations are studied. Convergence is shown for monotone matrices and for -matrices. Two different asynchronous versions of these methods are considered and their convergence investigated. Received September 7, 1993 / Revised version received April 21, 1994