求解PageRank问题的重启GMRES修正的多分裂迭代法

PageRank算法已经成为网络搜索引擎的核心技术。针对PageRank问题导出的线性方程组,首先将Krylov子空间方法中的重启GMRES(generalized minimal residual)方法与多分裂迭代(multi-splitting iteration,MSI)方法相结合,提出了一种重启GMRES修正的多分裂迭代法;然后,给出了该算法的详细计算流程和收敛性分析;最后,通过数值实验验证了该算法的有效性。     

High order finite difference method for time-space fractional differential equations with Caputo and Riemann-Liouville derivatives

We consider high order finite difference methods for two-dimensional fractional differential equations with temporal Caputo and spatial Riemann-Liouville derivatives in this paper. We propose a scheme and show that it converges with second order in time and fourth order in space. The accuracy of our proposed method can be improved by Richardson extrapolation. Approximate solution is obtained by the generalized minimal residual (GMRES) method. A preconditioner is proposed to improve the efficiency for the implementation of the GMRES method.     

Numerical experiments on a flexible variant of GMRES-DR

The Flexible GMRES (FGMRES [1]) and the GMRES with deflated restarting (GMRES-DR [2]) methods are two algorithms derived from GMRES [3], that are considered as powerful when solving large non hermitian systems of linear equations. GMRES-DR is a variant of GMRES with an improved restarting technique that maintains in the Krylov subspace harmonic Ritz vector from the previous restart. In situations where the convergence of restarted GMRES is slow and where the matrix has few eigenvalues close to the origin, this technique has proved very efficient. The new method that we propose is the Flexible GMRES with deflated restarting (FGMRES-DR [6]), which combines the two above mentioned algorithms in order to yield better performance. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Block structured preconditioners in tensor form for the all-at-once solution of a finite volume fractional diffusion equation

We propose a tensor structured preconditioner for the tensor train GMRES algorithm (or TT-GMRES for short) to approximate the solution of the all-at-once formulation of time-dependent fractional partial differential equations discretized in time by linear multistep formulas used in boundary value form and in space by finite volumes.Numerical experiments show that the proposed preconditioner is efficient for very large problems and is competitive, in particular with respect to the AMEn algorithm.     

A new adaptive GMRES algorithm for achieving high accuracy

GMRES(k) is widely used for solving non-symmetric linear systems. However, it is inadequate either when it converges only for k close to the problem size or when numerical error in the modified Gram–Schmidt process used in the GMRES orthogonalization phase dramatically affects the algorithm performance. An adaptive version of GMRES(k) which tunes the restart value k based on criteria estimating the GMRES convergence rate for the given problem is proposed here. This adaptive GMRES(k) procedure outperforms standard GMRES(k), several other GMRES-like methods, and QMR on actual large scale sparse structural mechanics postbuckling and analog circuit simulation problems. There are some applications, such as homotopy methods for high Reynolds number viscous flows, solid mechanics postbuckling analysis, and analog circuit simulation, where very high accuracy in the linear system solutions is essential. In this context, the modified Gram–Schmidt process in GMRES, can fail causing the entire GMRES iteration to fail. It is shown that the adaptive GMRES(k) with the orthogonalization performed by Householder transformations succeeds whenever GMRES(k) with the orthogonalization performed by the modified Gram–Schmidt process fails, and the extra cost of computing Householder transformations is justified for these applications. © 1998 John Wiley & Sons, Ltd.     

Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

An Efficient Variant of the Restarted Shifted GMRES Method for Solving Shifted Linear Systems

We investigate the restart of the Restarted Shifted GMRES method for solving shifted linear systems.Recently the variant of the GMRES(m) method with the unfixed update has been proposed to improve the convergence of the GMRES(m) method for solving linear systems,and shown to have an efficient convergence property.In this paper,by applying the unfixed update to the Restarted Shifted GMRES method,we propose a variant of the Restarted Shifted GMRES method.We show a potentiality for efficient convergence within the variant by some numerical results.     

The generalized HSS method for solving singular linear systems

For the singular, non-Hermitian, and positive semidefinite linear systems, we propose an alternating-direction iterative method with two parameters based on the Hermitian and skew-Hermitian splitting. The semi-convergence analysis and the quasi-optimal parameters of the proposed method are discussed. Moreover, the corresponding preconditioner based on the splitting is given to improve the semi-convergence rate of the GMRES method. Numerical examples are given to illustrate the theoretical results and the efficiency of the generalized HSS method either as a solver or a preconditioner for GMRES.     

A method of congruent type for linear systems with conjugate-normal coefficient matrices

Minimal residual methods, such as MINRES and GMRES, are well-known iterative versions of direct procedures for reducing a matrix to special condensed forms. The method of reduction used in these procedures is a sequence of unitary similarity transformations, while the condensed form is a tridiagonal matrix (MINRES) or a Hessenberg matrix (GMRES). The algorithm CSYM proposed in the 1990s for solving systems with complex symmetric matrices was based on the tridiagonal reduction performed via unitary congruences rather than similarities. In this paper, we construct an extension of this algorithm to the entire class of conjugate-normal matrices. (Complex symmetric matrices are a part of this class.) Numerical results are presented. They show that, on many occasions, the proposed algorithm has a superior convergence rate compared to GMRES.     

Circulant-block preconditioners for solving ordinary differential equations

Boundary value methods for solving ordinary differential equations require the solution of non-symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A circulant-block preconditioner is proposed to speed up the convergence rate of the GMRES method. Theoretical and practical arguments are given to show that this preconditioner is more efficient than some other circulant-type preconditioners in some cases. A class of waveform relaxation methods is also proposed to solve the linear systems.     

Objective acceleration for unconstrained optimization

Acceleration schemes can dramatically improve existing optimization procedures. In most of the work on these schemes, such as nonlinear generalized minimal residual (N‐GMRES), acceleration is based on minimizing the ?₂ norm of some target on subspaces of ${\mathbb{R}}^n$. There are many numerical examples that show how accelerating general‐purpose and domain‐specific optimizers with N‐GMRES results in large improvements. We propose a natural modification to N‐GMRES, which significantly improves the performance in a testing environment originally used to advocate N‐GMRES. Our proposed approach, which we refer to as O‐ACCEL (objective acceleration), is novel in that it minimizes an approximation to the objective function on subspaces of ${\mathbb{R}}^n$. We prove that O‐ACCEL reduces to the full orthogonalization method for linear systems when the objective is quadratic, which differentiates our proposed approach from existing acceleration methods. Comparisons with the limited‐memory Broyden–Fletcher–Goldfarb–Shanno and nonlinear conjugate gradient methods indicate the competitiveness of O‐ACCEL. As it can be combined with domain‐specific optimizers, it may also be beneficial in areas where limited‐memory Broyden–Fletcher–Goldfarb–Shanno and nonlinear conjugate gradient methods are not suitable.     

Relaxation methods for solving the tensor equation arising from the higher‐order Markov chains

In this paper, we propose several relaxation algorithms for solving the tensor equation arising from the higher‐order Markov chain and the multilinear PageRank. The semi‐symmetrization technique on the original equation is also employed to modify the proposed algorithms. The convergence analysis is given for the proposed algorithms. It is shown that the new algorithms are more efficient than the existing ones by some numerical experiments when relaxation parameters are chosen suitably.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Some observations on weighted GMRES

We investigate the convergence of the weighted GMRES method for solving linear systems. Two different weighting variants are compared with unweighted GMRES for three model problems, giving a phenomenological explanation of cases where weighting improves convergence, and a case where weighting has no effect on the convergence. We also present a new alternative implementation of the weighted Arnoldi algorithm which under known circumstances will be favourable in terms of computational complexity. These implementations of weighted GMRES are compared for a large number of examples. We find that weighted GMRES may outperform unweighted GMRES for some problems, but more often this method is not competitive with other Krylov subspace methods like GMRES with deflated restarting or BICGSTAB, in particular when a preconditioner is used.     

Regularized DPSS Preconditioners for Singular Saddle Point Problems

Recently, Cao proposed a regularized deteriorated positive and skew-Hermitian splitting (RDPSS) preconditioner for the non-Hermitian nonsingular saddle point problem. In this paper, we consider applying RDPSS preconditioner to solve the singular saddle point problem. Moreover, we propose a two-parameter accelerated variant of the RDPSS (ARDPSS) preconditioner to further improve its efficiency. Theoretical analysis proves that the RDPSS and ARDPSS methods are semi-convergent unconditionally. Some spectral properties of the corresponding preconditioned matrices are analyzed. Numerical experiments indicate that better performance can be achieved when applying the ARDPSS preconditioner to accelerate the GMRES method for solving the singular saddle point problem.     

On preconditioned MHSS iteration methods for complex symmetric linear systems

We propose a preconditioned variant of the modified HSS (MHSS) iteration method for solving a class of complex symmetric systems of linear equations. Under suitable conditions, we prove the convergence of the preconditioned MHSS (PMHSS) iteration method and discuss the spectral properties of the PMHSS-preconditioned matrix. Numerical implementations show that the resulting PMHSS preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as GMRES and its restarted variants. In particular, both the stationary PMHSS iteration and PMHSS-preconditioned GMRES show meshsize-independent and parameter-insensitive convergence behavior for the tested numerical examples.     

Weighted and deflated global GMRES algorithms for solving large Sylvester matrix equations

The solution of a large-scale Sylvester matrix equation plays an important role in control and large scientific computations. In this paper, we are interested in the large Sylvester matrix equation with large dimensionA and small dimension B, and a popular approach is to use the global Krylov subspace method. In this paper, we propose three new algorithms for this problem. We first consider the global GMRES algorithm with weighting strategy, which can be viewed as a precondition method. We present three new schemes to update the weighting matrix during iterations. Due to the growth of memory requirements and computational cost, it is necessary to restart the algorithm effectively. The deflation strategy is efficient for the solution of large linear systems and large eigenvalue problems; to the best of our knowledge, little work is done on applying deflation to the (weighted) global GMRES algorithm for large Sylvester matrix equations. We then consider how to combine the weighting strategy with deflated restarting, and propose a weighted global GMRES algorithm with deflation for solving large Sylvester matrix equations. In particular, we are interested in the global GMRES algorithm with deflation, which can be viewed as a special case when the weighted matrix is chosen as the identity. Theoretical analysis is given to show rationality of the new algorithms. Numerical experiments illustrate the numerical behavior of the proposed algorithms.

     

Conjugate gradient and minimal residual methods for solving symmetric indefinite systems

Norm-minimizing-type methods for solving large sparse linear systems with symmetric and indefinite coefficient matrices are considered. The Krylov subspace can be generated by either the Lanczos approach, such as the methods MINRES, GMRES and QMR, or by a conjugate-gradient approach. Here, we propose an algorithm based on the latter approach. Some relations among the search directions and the residuals, and how the search directions are related to the Krylov subspace are investigated. Numerical experiments are reported to verify the convergence properties.     

Adaptive version of Simpler GMRES

In this paper we propose a stable variant of Simpler GMRES. It is based on the adaptive choice of the Krylov subspace basis at a given iteration step using the intermediate residual norm decrease criterion. The new direction vector is chosen as in the original implementation of Simpler GMRES or it is equal to the normalized residual vector as in the GCR method. We show that such an adaptive strategy leads to a well-conditioned basis of the Krylov subspace and we support our theoretical results with illustrative numerical examples.     

The PageRank model of minimal irreducible adjustment and its lumping method

In this paper, based on the original PageRank model with usual adjustment and computation, we propose a minimal irreducible adjustment model of PageRank. It is proved that the solution of this model is unique. Furthermore, an effective blocking and lumping algorithm is used for speeding up the process of obtaining this solution. Three numerical examples are given to verify the argues being correct and proper.