On the semi-conjugate direction methods with dynamic preconditioning

The semi-conjugate residual methods and semi-conjugate gradient methods with dynamic preconditioners in Krylov subspaces are considered for solving the systems of linear algebraic equations whose matrices are not symmetric. Their orthogonal and variational properties are under study. New algorithms are proposed for choosing the inner iteration parameters in the preconditioning matrices corresponding to incomplete factorization methods. The efficiency of the resulting iterative processes is demonstrated by a set of numerical experiments for finite difference diffusion-convection equations.     

Parallel CPR preconditioner for a multicomponent fluid flow filtration problem in a porous medium

The constrained pressure residual (CPR) preconditioning method is considered with regard to solution of systems with matrices appearing in discretization of PDE systems describing multicomponent fluid flow in porous media. New versions of algorithms are proposed. Numerical experiments using an actual parallel hydrodynamic simulator were performed for test and actual oil fields in Western Siberia, these experiments confirm the efficiency of the methods.     

Preconditioned conjugate gradient methods for large-scale fluid flow applications

The simulation of large-scale fluid flow applications often requires the efficient solution of extremely large nonsymmetric linear and nonlinear sparse systems of equations arising from the discretization of systems of partial differential equations. While preconditioned conjugate gradient methods work well for symmetric, positive-definite matrices, other methods are necessary to treat large, nonsymmetric matrices. The applications may also involve highly localized phenomena which can be addressed via local and adaptive grid refinement techniques. These local refinement methods usually cause non-standard grid connections which destroy the bandedness of the matrices and the associated ease of solution and vectorization of the algorithms. The use of preconditioned conjugate gradient or conjugate-gradient-like iterative methods in large-scale reservoir simulation applications is briefly surveyed. Then, some block preconditioning methods for adaptive grid refinement via domain decomposition techniques are presented and compared. These techniques are being used efficiently in existing large-scale simulation codes.     

How real is your matrix?

For scalars there is essentially just one way to define reality, real part and to measure nonreality. In this paper various ways of defining respective concepts for complex-entried matrices are considered. In connection with this, products of circulant and diagonal matrices often appear and algorithms to approximate additively and multiplicatively with them are devised. Multiplicative structures have applications, for instance, in diffractive optics, preconditioning and fast Fourier expansions.     

Construction and efficient implementation of implicit preconditioning methods. I

The paper presents a comparative analysis of various preconditioning procedures and proposes a new approach to the construction of preconditioning methods for the solution of large systems of linear algebraic equations with sparse matrices. Efficient implementation of preconditioning methods on MIMD multiprocessor computing systems is considered under constraints on computer resources and technical possibilities.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 63, pp. 42–49, 1987.     

Construction and efficient implementation of implicit preconditioning methods,II

The paper presents a comparative analysis of various preconditioning procedures and proposes a new approach to the construction of preconditioning methods for the solution of systems of linear algebraic equations of any order with sparse matrices. Efficient implementation of preconditioning methods on MIMD multiprocessor computer systems is considered under constraints on computer resources and technical possibilities.Part I, seeVychislitel'naya i Prikladnaya Matematika, No. 63, 42–50 (1987).Translated from Vychislitel'naya i Prikladnaya Matematika, No. 65, pp. 14–24, 1988. Original article submitted April 10, 1987.     

On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, we present block SSOR and modified block SSOR iteration methods based on the special structures of the coefficient matrices. In each step of the block SSOR iteration, we employ the block LU factorization to solve the sub-systems of linear equations. We show that the block LU factorization is existent and stable when the coefficient matrices are block diagonally dominant of type-II by columns. Under suitable conditions, we establish convergence theorems for both block SSOR and modified block SSOR iteration methods. In addition, the block SSOR iteration and AF-ADI method are considered as preconditioners for the nonsymmetric systems of linear equations. Numerical experiments show that both block SSOR and modified block SSOR iterations are feasible iterative solvers and they are also effective for preconditioning Krylov subspace methods such as GMRES and BiCGSTAB when used to solve this class of systems of linear equations.     

On large-scale diagonalization techniques for the Anderson model of localization

We propose efficient preconditioning algorithms for an eigenvalue problem arising in quantum physics, namely the computation of a few interior eigenvalues and their associated eigenvectors for large-scale sparse real and symmetric indefinite matrices of the Anderson model of localization. Our preconditioning approaches for the shift-and-invert symmetric indefinite linear system are based on maximum weighted matchings and algebraic multi-level incomplete LDL^T factorizations. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques for the highly ill-conditioned symmetric indefinite Anderson matrices. Our numerical examples reveal that recent algebraic multi-level preconditioning solvers can accelerate the computation of a large-scale eigenvalue problem corresponding to the Anderson model of localization by several orders of magnitude. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

Influences of preconditioning on the mutual coherence and the restricted isometry property of Gaussian/Bernoulli measurement matrices

This article discusses the influence of preconditioning on the mutual coherence and the restricted isometry property of Gaussian or Bernoulli measurement matrices. The mutual coherence can be reduced by preconditioning, although it is fairly small due to the probability estimate of the event that it is less than any given number in (0, 1). This can be extended to a set that contains either of the two types of matrices with a high probability but a subset with Lebesgue measure zero. The numerical results illustrate the reduction in the mutual coherence of Gaussian or Bernoulli measurement matrices. However, the first property can be true after preconditioning for a large type of measurement matrices having the property of s-order restricted isometry and being full row rank. This leads to a better estimate of the condition number of the corresponding submatrices and a more accurate error estimate of the conjugate gradient methods for the least squares problems typically used in greedy-like recovery algorithms.     

Combination of numerical and structured approaches to the construction of a second-order incomplete triangular factorization in parallel preconditioning methods

Parallel versions of the stabilized second-order incomplete triangular factorization conjugate gradient method in which the reordering of the coefficient matrix corresponding to the ordering based on splitting into subdomains with separators are considered. The incomplete triangular factorization is organized using the truncation of fill-in “by value” at internal nodes of subdomains, and “by value” and ‘by positions” on the separators. This approach is generalized for the case of constructing a parallel version of preconditioning the second-order incomplete LU factorization for nonsymmetric diagonally dominant matrices with. The reliability and convergence rate of the proposed parallel methods is analyzed. The proposed algorithms are implemented using MPI, results of solving benchmark problems with matrices from the collection of the University of Florida are presented.     

Structure preserving quaternion full orthogonalization method with applications

This article proposes a structure-preserving quaternion full orthogonalization method (QFOM) for solving quaternion linear systems arising from color image restoration. The method is based on the quaternion Arnoldi procedure preserving the quaternion Hessenberg form. Combining with the preconditioning techniques, we further derive a variant of the QFOM for solving the linear systems, which can greatly improve the rate of convergence of QFOM. Numerical experiments on randomly generated data and color image restoration problems illustrate the effectiveness of the proposed algorithms in comparison with some existing methods.     

On Preconditioning of Incompressible Non-Newtonian Flow Problems

This paper deals with fast and reliable numerical solution methods for the incompressible non-Newtonian Navier-Stokes equations. To handle the nonlinearity of the governing equations, the Picard and Newton methods are used to linearize these coupled partial differential equations. For space discretization we use the finite element method and utilize the two-by-two block structure of the matrices in the arising algebraic systems of equations. The Krylov subspace iterative methods are chosen to solve the linearized discrete systems and the development of computationally and numerically efficient preconditioners for the two-by-two block matrices is the main concern in this paper. In non-Newtonian flows, the viscosity is not constant and its variation is an important factor that affects the performance of some already known preconditioning techniques. In this paper we examine the performance of several preconditioners for variable viscosity applications, and improve them further to be robust with respect to variations in viscosity.     

嵌套简单ILU分解代数预处理方法

In this paper, we propose a nested simple incomplete LU decomposition (NSILU) method for preconditioning iterative methods for solving largely scale and sparse ill-conditioned hnear systems. NSILU consists of some numerical techniques such as simple modification of Schur complement, compression of ill-condition structure by permutation, nested simple ILU, and inner-outer iteration. We give detailed error analysis of NSILU and estimations of condition number of the preconditioned coefficient matrix, together with numerical comparisons. We also show an analysis of inner accuracy strategies for the inner-outer iteration approach. Our new approach NSILU is very efficient for linear systems from a kind of two-dimensional nonlinear energy equations with three different temperature variables, where most of the calculations centered around solving large number of discretized and illconditioned linear systems in large scale. Many numerical experiments are given and compared in costs of flops, CPU times, and storages to show the efficiency and effectiveness of the NSILU preconditioning method. Numerical examples include middle-scale real matrices of size n = 3180 or n = 6360, a real apphcation of solving about 755418 linear systems of size n = 6360, and a simulation of order n=814080 with structures and properties similar as the real ones.     

Parallel Newton two‐stage methods based on ILU factorizations for nonlinear systems

Parallel iterative algorithms based on the Newton method and on two of its variants, the Shamanskii method and the Chord method, for solving nonlinear systems are proposed. These algorithms are based on two‐stage multisplitting methods where incomplete LU factorizations are considered as a mean of constructing the inner splittings. Convergence properties of these parallel methods are studied for H‐matrices. Computational results of these methods on two parallel computing systems are discussed. The reported experiments show the effectiveness of these methods. Copyright © 2006 John Wiley & Sons, Ltd.     

The least-squares method for matrices dependent on parameters

Some algorithms are suggested for constructing pseudoinverse matrices and for solving systems with rectangular matrices whose entries depend on a parameter in polynomial and rational ways. The cases of one- and two-parameter matrices are considered. The construction of pseudoinverse matrices are realized on the basis of rank factorization algorithms. In the case of matrices with polynomial occurrence of parameters, these algorithms are the ΔW-1 and ΔW-2 algorithms for one- and two-parameter matrices, respectively. In the case of matrices with rational occurrence of parameters, these algorithms are the irreducible factorization algorithms. This paper is a continuation of the author's studies of the solution of systems with one-parameter matrices and an extension of the results to the case of two-parameter matrices with polynomial and rational entries. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 176–185. This work was supported by the Russian Foundation of Fundamental Research (grant 94-01-00919). Translated by V. N. Kublanovskaya.     

A CLASS OF NEW PARALLEL HYBRID ALGEBRAIC MULTILEVEL ITERATIONS

1. IntroductionConsider the large sparse system of linear equationsAx = b, (1.1)where, for a fixed positive integer cr, A e L(R") is a symmetric positive definite (SPD) matrir,having the bloCked formx,b E R" are the uDknwn and the known vectors, respectively, having the correspondingblocked formsni(ni S n, i = 1, 2,', a) are a given positthe integers, satisfying Z ni = n. This systemi= 1of linear equations often arises in sultable finite element discretizations of many secondorderseifad…     

Duality in conjugate gradient methods

In this paper we show that if the step (displacement) vectors generated by the preconditioned conjugate gradient algorithm are scaled appropriately they may be used to solve equations whose coefficient matrices are the preconditioning matrices of the original equations. The dual algorithms thus obtained are shown to be equivalent to the reverse algorithms of Hegedüs and are subsequently generalised to their block forms. It is finally shown how these may be used to construct dual (or reverse) algorithms for solving equations involving nonsymmetric matrices using only short recurrences, and reasons are suggested why some of these algorithms may be more numerically stable than their primal counterparts. This revised version was published online in June 2006 with corrections to the Cover Date.     

Band-Toeplitz Preconditioned GMRES Iterations for Time-Dependent PDEs

Nonsymmetric linear systems of algebraic equations which are small rank perturbations of block band-Toeplitz matrices from discretization of time-dependent PDEs are considered. With a combination of analytical and experimental results, we examine the convergence characteristics of the GMRES method with circulant-like block preconditioning for solving these systems.This revised version was published online in October 2005 with corrections to the Cover Date.