Updating incomplete factorization preconditioners for model order reduction

When solving a sequence of related linear systems by iterative methods, it is common to reuse the preconditioner for several systems, and then to recompute the preconditioner when the matrix has changed significantly. Rather than recomputing the preconditioner from scratch, it is potentially more efficient to update the previous preconditioner. Unfortunately, it is not always known how to update a preconditioner, for example, when the preconditioner is an incomplete factorization. A recently proposed iterative algorithm for computing incomplete factorizations, however, is able to exploit an initial guess, unlike existing algorithms for incomplete factorizations. By treating a previous factorization as an initial guess to this algorithm, an incomplete factorization may thus be updated. We use a sequence of problems from model order reduction. Experimental results using an optimized GPU implementation show that updating a previous factorization can be inexpensive and effective, making solving sequences of linear systems a potential niche problem for the iterative incomplete factorization algorithm.     

一个求解无约束优化问题的条件预优共轭梯度法

1 引言 考虑无约束最优化问题minf(x)(1.1)     

Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation

The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable‐coefficient Helmholtz equation including very‐high‐frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three‐dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. © 2011 Wiley Periodicals, Inc.     

A Rayleigh–Ritz preconditioner for the iterative solution to large scale nonlinear problems

The approximation to the solution of large sparse symmetric linear problems arising from nonlinear systems of equations is considered. We are focusing herein on reusing information from previous processes while solving a succession of linear problems with a Conjugate Gradient algorithm. We present a new Rayleigh–Ritz preconditioner that is based on the Krylov subspaces and superconvergence properties, and consists of a suitable reuse of a given set of Ritz vectors. The relevance and the mathematical foundations of the current approach are detailed and the construction of the preconditioner is presented either for the unconstrained or the constrained problems. A corresponding practical preconditioner for iterative domain decomposition methods applied to nonlinear elasticity is addressed, and numerical validation is performed on a poorly-conditioned large-scale practical problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Toeplitz预条件子的统一构造与性能分析

１．引言考虑线性方程组ＴＮｘ＝ｂ（１．１）其中ＴＮ＝（ｔｉ,ｊ）是ＮｘＮ对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵,即ｔｉ,ｊ＝ｔ｜ｉ－ｊ｜（ｉ,ｊ＝０,１,...,Ｎ－１）且ＴＮ的所有特征值均为正数,并表为ＴＮ：＝Ｔ（ｔ。,ｔｉ,...,ｔＮ－１）．如果我们用预条件子共轭梯度法（ＰＣＧ）求解方程组（１．１）,最关健的任务是构造出高效的预条件子．而预条件子最自然的选择似乎其逆矩阵易求且构成矩阵ＴＮ的某种最优逼近．由于循环矩阵ＣＮ的逆矩阵ＣＲ'仍为循环矩阵,因此ＣＮ和ＣＨ'与向量的乘积可通ｉｓ速Ｆｏｕｒｉｅｒ…     

对称Toeplitz系统的快速W变换基预条件子

１．引言考虑下列Ｎ阶线性方程组其中T_N=(t_i,j)　是Ｎ×Ｎ阶实对称正定（ＳＰＤ）Ｔｏｅｐｌｉｔｚ矩阵,即０,１,…,Ｎ－１）且Ｔ_Ｎ的所有特征值为正数．Ｔｏｅｐｌｉｔｚ系统已广泛应用于数字信号处理,时间序列分析（参见［１］）以及微分方程的数值解（参见［２１］等领域．八十年代以前,考虑到Ｔｏｅｐｌｉｔｚ矩阵的特殊性,人们主要用Ｌｅｖｉｎｓｏｎ递推技术及其变形或者分而治之思想直接求解方程组（１．１）,计算复杂性为Ｏ（Ｎ~（２））或Ｏ（ＮｌｏｇＮ~（２））（参见［３］）;比Ｇａｕｓｓ法运算量级Ｏ（Ｎ~（３）…     

An efficient method to set up a Lanczos based preconditioner for discrete ill-posed problems

Rezghi and Hosseini [M. Rezghi, S.M. Hosseini, Lanczos based preconditioner for discrete ill-posed problems, Computing 88 (2010) 79–96] presented a Lanczos based preconditioner for discrete ill-posed problems. Their preconditioner is constructed by using few steps (e.g., k) of the Lanczos bidiagonalization and corresponding computed singular values and right Lanczos vectors. In this article, we propose an efficient method to set up such preconditioner. Some numerical examples are given to show the effectiveness of the method.     

A geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.     

Approximate inverse preconditioner by computing approximate solution of Sylvester equation

This paper presents a new method for obtaining a matrix M which is an approximate inverse preconditioner for a given matrix A, where the eigenvalues of A all either have negative real parts or all have positive real parts. This method is based on the approximate solution of the special Sylvester equation AX + XA = 2I. We use a Krylov subspace method for obtaining an approximate solution of this Sylvester matrix equation which is based on the Arnoldi algorithm and on an integral formula. The computation of the preconditioner can be carried out in parallel and its implementation requires only the solution of very simple and small Sylvester equations. The sparsity of the preconditioner is preserved by using a proper dropping strategy. Some numerical experiments on test matrices from Harwell–Boing collection for comparing the numerical performance of the new method with an available well-known algorithm are presented.     

Block filtering decomposition

This paper introduces a new preconditioning technique that is suitable for matrices arising from the discretization of a system of PDEs on unstructured grids. The preconditioner satisfies a so‐called filtering property, which ensures that the input matrix is identical with the preconditioner on a given filtering vector. This vector is chosen to alleviate the effect of low‐frequency modes on convergence and so decrease or eliminate the plateau that is often observed in the convergence of iterative methods. In particular, the paper presents a general approach that allows to ensure that the filtering condition is satisfied in a matrix decomposition. The input matrix can have an arbitrary sparse structure. Hence, it can be reordered using nested dissection, to allow a parallel computation of the preconditioner and of the iterative process. We show the efficiency of our preconditioner through a set of numerical experiments on symmetric and nonsymmetric matrices. Copyright © 2014 John Wiley & Sons, Ltd.     

Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods

In this work, the optimal adjustment algorithm for p coordinates, which arose from a generalization of the optimal pair adjustment algorithm is used to accelerate the convergence of interior point methods using a hybrid iterative approach for solving the linear systems of the interior point method. Its main advantages are simplicity and fast initial convergence. At each interior point iteration, the preconditioned conjugate gradient method is used in order to solve the normal equation system. The controlled Cholesky factorization is adopted as the preconditioner in the first outer iterations and the splitting preconditioner is adopted in the final outer iterations. The optimal adjustment algorithm is applied in the preconditioner transition in order to improve both speed and robustness. Numerical experiments on a set of linear programming problems showed that this approach reduces the total number of interior point iterations and running time for some classes of problems. Furthermore, some problems were solved only when the optimal adjustment algorithm for p coordinates was used in the change of preconditioners.     

ARMS: an algebraic recursive multilevel solver for general sparse linear systems

This paper presents a general preconditioning method based on a multilevel partial elimination approach. The basic step in constructing the preconditioner is to separate the initial points into two parts. The first part consists of ‘block’ independent sets, or ‘aggregates’. Unknowns of two different aggregates have no coupling between them, but those in the same aggregate may be coupled. The nodes not in the first part constitute what might be called the ‘coarse’ set. It is natural to call the nodes in the first part ‘fine’ nodes. The idea of the methods is to form the Schur complement related to the coarse set. This leads to a natural block LU factorization which can be used as a preconditioner for the system. This system is then solved recursively using as preconditioner the factorization that could be obtained from the next level. Iterations between levels are allowed. One interesting aspect of the method is that it provides a common framework for many other techniques. Numerical experiments are reported which indicate that the method can be fairly robust. Copyright © 2002 John Wiley & Sons, Ltd.     

On the performance of various adaptive preconditioned GMRES strategies

This paper compares the performance on linear systems of equations of three similar adaptive accelerating strategies for restarted GMRES. The underlying idea is to adaptively use spectral information gathered from the Arnoldi process. The first strategy retains approximations to some eigenvectors from the previous restart and adds them to the Krylov subspace. The second strategy also uses approximated eigenvectors to define a preconditioner at each restart. This paper designs a third new strategy which combines elements of both previous approaches. Numerical results show that this new method is both more efficient and more robust. © 1998 John Wiley & Sons, Ltd.     

An iterative solution method for the Stokes problem with variable viscosity

An iterative method for efficient solution of the Stokes problem with a variable viscosity is considered. A preconditioner for the Shur complement is constructed taking into account the variable viscosity. The efficiency analysis is given. An application of the preconditioner for solving one problem of the mantle convection modeling is considered.     

Preconditioned iterative methods on sparse subspaces

When some rows of the system matrix and a preconditioner coincide, preconditioned iterations can be reduced to a sparse subspace. Taking advantage of this property can lead to considerable memory and computational savings. This is particularly useful with the GMRES method. We consider the iterative solution of a discretized partial differential equation on this sparse subspace. With a domain decomposition method and a fictitious domain method the subspace corresponds a small neighborhood of an interface. As numerical examples we solve the Helmholtz equation using a fictitious domain method and an elliptic equation with a jump in the diffusion coefficient using a separable preconditioner.     

Domain decomposition for multiscale PDEs

We consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic PDEs with highly variable coefficients. In contrast to standard analyses, we do not assume that the coefficients can be resolved by a coarse mesh. This situation arises often in practice, for example in the computation of flows in heterogeneous porous media, in both the deterministic and (Monte–Carlo simulated) stochastic cases. We consider preconditioners which combine local solves on general overlapping subdomains together with a global solve on a general coarse space of functions on a coarse grid. We perform a new analysis of the preconditioned matrix, which shows rather explicitly how its condition number depends on the variable coefficient in the PDE as well as on the coarse mesh and overlap parameters. The classical estimates for this preconditioner with linear coarsening guarantee good conditioning only when the coefficient varies mildly inside the coarse grid elements. By contrast, our new results show that, with a good choice of subdomains and coarse space basis functions, the preconditioner can still be robust even for large coefficient variation inside domains, when the classical method fails to be robust. In particular our estimates prove very precisely the previously made empirical observation that the use of low-energy coarse spaces can lead to robust preconditioners. We go on to consider coarse spaces constructed from multiscale finite elements and prove that preconditioners using this type of coarsening lead to robust preconditioners for a variety of binary (i.e., two-scale) media model problems. Moreover numerical experiments show that the new preconditioner has greatly improved performance over standard preconditioners even in the random coefficient case. We show also how the analysis extends in a straightforward way to multiplicative versions of the Schwarz method. We would like to thank Bill McLean for very useful discussions concerning this work. We would also like to thank Maksymilian Dryja for helping us to improve the result in Theorem 4.3.     

SINE TRANSFORM MATRIX FOR SOLVING TOEPLITZ MATRIX PROBLEMS

1. IntroductionStrang[1] first studied the use of circulallt matrices C for solving systems of linear eqllationsTi x = b witha symmetric positive definite Toeplitz matrix.Numerous authors such as T.Chan[2],R.Chan,etc.[3],[4],[5], Tyrtyshnikov[6], Huckle[7] and T.Ku and C.Kuo[8] proposed differentfamilies of circulallt / skew- circulant precondit ioners.Appling the preconditioned conjugate gradient algorithm(PCGA) to solve the systems Ti x -b, we must find a preconditioner P such that P…     

Augmented Lagrangian-based preconditioners for steady buoyancy driven flow

In this paper, we apply the augmented Lagrangian (AL) approach to steady buoyancy driven flow problems. Two AL preconditioners are developed based on the variable’s order, specifically whether the leading variable is the velocity or the temperature variable. Correspondingly, two non-augmented Lagrangian (NAL) preconditioners are also considered for comparison. An eigenvalue analysis for these two pairs of preconditioners is conducted to predict the rate of convergence for the GMRES solver. The numerical results show that the AL preconditioner pair is insensitive with respect to the mesh size, Rayleigh number, and Prandtl number in terms of GMRES iterations, resulting in a significantly more robust preconditioner pair compared to the NAL pair. Accordingly, the AL pair performs much better than the NAL pair in terms of computational time. For the AL pair, the preconditioner with velocity as the leading variable gives slightly better efficiency than the one with temperature as the leading variable.     

A dimensional split preconditioner for Stokes and linearized Navier-Stokes equations

In this paper we introduce a new preconditioner for linear systems of saddle point type arising from the numerical solution of the Navier-Stokes equations. Our approach is based on a dimensional splitting of the problem along the components of the velocity field, resulting in a convergent fixed-point iteration. The basic iteration is accelerated by a Krylov subspace method like restarted GMRES. The corresponding preconditioner requires at each iteration the solution of a set of discrete scalar elliptic equations, one for each component of the velocity field. Numerical experiments illustrating the convergence behavior for different finite element discretizations of Stokes and Oseen problems are included.     

Multiscale Domain Decomposition Methods for Elliptic Problems with High Aspect Ratios

Abstract In this paper we study some nonoverlapping domain decomposition methods for solving a classof elliptic problems arising from composite materials and flows in porous media which contain many spatialscales. Our preconditioner differs from traditional domain decomposition preconditioners by using a coarsesolver which is adaptive to small scale heterogeneous features. While the convergence rate of traditional domaindecomposition algorithms using coarse solvers based on linear or polynomial interpolations may deteriorate inthe presence of rapid small scale oscillations or high aspect ratios, our preconditioner is applicable to multiple-scale problems without restrictive assumptions and seems to have a convergence rate nearly independent ofthe aspect ratio within the substructures. A rigorous convergence analysis based on the Schwarz framework iscarried out, and we demonstrate the efficiency and robustness of the proposed preconditioner through numericalexperiments which include problems with multipl