On deflation and singular symmetric positive semi-definite matrices

For various applications, it is well-known that the deflated ICCG is an efficient method for solving linear systems with invertible coefficient matrix. We propose two equivalent variants of this deflated ICCG which can also solve linear systems with singular coefficient matrix, arising from discretization of the discontinuous Poisson equation with Neumann boundary conditions. It is demonstrated both theoretically and numerically that the resulting methods accelerate the convergence of the iterative process.     

A tearing-based hybrid parallel banded linear system solver

A new parallel algorithm for the solution of banded linear systems is proposed. The scheme tears the coefficient matrix into several overlapped independent blocks in which the size of the overlap is equal to the system’s bandwidth. A corresponding splitting of the right-hand side is also provided. The resulting independent, and smaller size, linear systems are solved under the constraint that the solutions corresponding to the overlap regions are identical. This results in a linear system whose size is proportional to the sum of the overlap regions which we refer to as the “balance” system. We propose a solution strategy that does not require obtaining this “balance” system explicitly. Once the balance system is solved, retrieving the rest of the solution can be realized with almost perfect parallelism. Our proposed algorithm is a hybrid scheme that combines direct and iterative methods for solving a single banded system of linear equations on parallel architectures. It has broad applications in finite-element analysis, particularly as a parallel solver of banded preconditioners that can be used in conjunction with outer Krylov iterative schemes.     

Application of modified homotopy perturbation method for solving the augmented systems

In this paper, a new approach is proposed for solving the augmented systems. Based on the modified homotopy perturbation method, we construct the new iterative methods and derive the sufficient and necessary conditions for guaranteeing its convergence. Some numerical experiments show that this method is more simple and effective.     

A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

Iterative refinement enhances the stability ofQR factorization methods for solving linear equations

Iterative refinement is a well-known technique for improving the quality of an approximate solution to a linear system. In the traditional usage residuals are computed in extended precision, but more recent work has shown that fixed precision is sufficient to yield benefits for stability. We extend existing results to show that fixed precision iterative refinement renders anarbitrary linear equations solver backward stable in a strong, componentwise sense, under suitable assumptions. Two particular applications involving theQR factorization are discussed in detail: solution of square linear systems and solution of least squares problems. In the former case we show that one step of iterative refinement suffices to produce a small componentwise relative backward error. Our results are weaker for the least squares problem, but again we find that iterative refinement improves a componentwise measure of backward stability. In particular, iterative refinement mitigates the effect of poor row scaling of the coefficient matrix, and so provides an alternative to the use of row interchanges in the HouseholderQR factorization. A further application of the results is described to fast methods for solving Vandermonde-like systems.     

Matrix enlarging methods and their application

This paper explores several methods for matrix enlarging, where an enlarged matrixà is constructed from a given matrixA. The methods explored include matrix primitization, stretching and node splitting. Graph interpretations of these methods are provided. Solving linear problems using enlarged matrices yields the answer to the originalAx=b problem.à can exhibit several desirable properties. For example,à can be constructed so that the valence of any row and/or column is smaller than some desired number (≥4). This is beneficial for algorithms that depend on the square of the number of entries of a row or column. Most particularly, matrix enlarging can results in a reduction of the fill-in in theR matrix which occurs during orthogonal factorization as a result of dense rows. Numerical experiments support these conjectures.     

A general finite element preconditioning for the conjugate gradient method

Discretizing a symmetric elliptic boundary value problem by a finite element method results in a system of linear equations with a symmetric positive definite coefficient matrix. This system can be solved iteratively by a preconditioned conjugate gradient method. In this paper a preconditioning matrix is proposed that can be constructed for all finite element methods if a mild condition for the node numbering is fulfilled. Such a numbering can be constructed using a variant of the reverse Cuthill-McKee algorithm.     

Fast transforms for tridiagonal linear equations

In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern ²×n ² in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems.     

Convergence theorems for block splitting iterative methods for linear systems

In this paper, we will present the block splitting iterative methods with general weighting matrices for solving linear systems of algebraic equations Ax=b$\mathit{Ax}=b$ when the coefficient matrix A is symmetric positive definite of block form, and establish the convergence theories with respect to the general weighting matrices but special splittings. Finally, a numerical example shows the advantage of this method.     

A tearing-based hybrid parallel sparse linear system solver

We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size of each overlap. Separating these blocks into independent linear systems with the constraint of matching the solution parts of neighboring blocks that correspond to the overlaps, we obtain a balance system. This balance system is not formed explicitly and has a size that is much smaller than the original system. Our novel solver requires only a one-time factorization of each diagonal block, and in each outer iteration, obtaining only the upper and lower tips of a solution vector where the size of each tip is equal to that of the individual overlap. This scheme proves to be scalable on clusters of nodes in which each node has a multicore architecture. Numerical experiments comparing the scalability of our solver with direct and preconditioned iterative methods are also presented.     

on hybrid preconditioning methods for large sparse saddle-point problems

Based on the block-triangular product approximation to a 2-by-2 block matrix, a class of hybrid preconditioning methods is designed for accelerating the MINRES method for solving saddle-point problems. The appropriate values for the parameters involved in the new preconditioners are estimated, so that the numerical conditioning and the spectral property of the saddle-point matrix of the linear system can be substantially improved. Several practical hybrid preconditioners and the corresponding preconditioning iterative methods are constructed and studied, too.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

Preconditioned GAOR methods for solving weighted linear least squares problems

In this paper, we present the preconditioned generalized accelerated overrelaxation (GAOR) method for solving linear systems based on a class of weighted linear least square problems. Two kinds of preconditioning are proposed, and each one contains three preconditioners. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the convergence rate of the preconditioned GAOR methods is indeed better than the rate of the original method, whenever the original method is convergent. Finally, a numerical example is presented in order to confirm these theoretical results.     

On multisplitting methods for band matrices

Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting factors may considerably improve the convergence. Received July 18, 1994 / Revised version received November 20, 1995     

A class of ABS algorithms for Diophantine linear systems

Summary. Systems of integer linear (Diophantine) equations arise from various applications. In this paper we present an approach, based upon the ABS methods, to solve a general system of linear Diophantine equations. This approach determines if the system has a solution, generalizing the classical fundamental theorem of the single linear Diophantine equation. If so, a solution is found along with an integer Abaffian (rank deficient) matrix such that the integer combinations of its rows span the integer null space of the cofficient matrix, implying that every integer solution is obtained by the sum of a single solution and an integer combination of the rows of the Abaffian. We show by a counterexample that, in general, it is not true that any set of linearly independent rows of the Abaffian forms an integer basis for the null space, contrary to a statement by Egervary. Finally we show how to compute the Hermite normal form for an integer matrix in the ABS framework. Received July 9, 1999 / Revised version received May 8, 2000 / Published online May 4, 2001     

Direct and approximate algorithmic methods for solving self-adjoint elliptic PDEs in three-space dimensions

The numerical implementation of the extended to the limit sparse LDL^T factorization solution methods for three-dimensional self-adjoint elliptic partial differential equations [3] is given. Two FORTRAN routines for the approximate (or exact) factorization of the coefficient matrix and solution of the resulting finite difference equations are supplied. The amount of fill-in terms can be controlled by the user through parameters R1, R2 the limiting case being when the matrix is factorized exactly.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.     

A generalized successive overrelaxation method for least squares problems

In this paper a new iterative method is given for solving large sparse least squares problems and computing the minimum norm solution to underdetermined consistent linear systems. The new scheme is called the generalized successive overrelaxation (GSOR) method and is shown to be convergent ifA is full column rank. The GSOR method involves a parameter ρ and an auxiliary matrixP. One can choose matrix P so that the GSOR method only involves matrix and vector operations; therefore the GSOR method is suitable for parallel computations. Besides, the GSOR method can be combined with preconditioning techniques, and therefore can be expected to be more effective. This author's work was supported by Natural Science Foundation of Liaoning Province, China.