Data structures to vectorize CG algorithms for general sparsity patterns

We describe an implementation of Conjugate Gradient-type iterative algorithms for problems with general sparsity patterns on a vector processor with a hierarchy of memories, such as the IBM 3090/VF. The implementation relies on the wavefront approach to vectorize the solution of the two sparse triangular systems that arise when using ILU type preconditioners. The data structure is the key to an effective implementation of sparse computational kernels on a vector processor. A data structure is a combination of a layout of the matrix coefficients and ordering schemes for the vectors to increase data locality. With the data structure we describe, we achieve comparable performance on both the matrix-vector product and the solution of the sparse triangular systems on a variety of real problems, such as those arising from large scale reservoir simulation or structural analysis.     

A note on the eigenvalues of a special class of matrices

In the analysis of stability of a variant of the Crank-Nicolson (C-N) method for the heat equation on a staggered grid a class of non-symmetric matrices appear that have an interesting property: their eigenvalues are all real and lie within the unit circle. In this note we shall show how this class of matrices is derived from the C-N method and prove that their eigenvalues are inside [−1,1] for all values of m (the order of the matrix) and all values of a positive parameter σ, the stability parameter. As the order of the matrix is general, and the parameter σ lies on the positive real line this class of matrices turns out to be quite general and could be of interest as a test set for eigenvalue solvers, especially as examples of very large matrices.     

On the modification of an eigenvalue problem that preserves an eigenspace

Eigenvalue problems arise in many application areas ranging from computational fluid dynamics to information retrieval. In these fields we are often interested in only a few eigenvalues and corresponding eigenvectors of a sparse matrix. In this paper, we comment on the modifications of the eigenvalue problem that can simplify the computation of those eigenpairs. These transformations allow us to avoid difficulties associated with non-Hermitian eigenvalue problems, such as the lack of reliable non-Hermitian eigenvalue solvers, by mapping them into generalized Hermitian eigenvalue problems. Also, they allow us to expose and explore parallelism. They require knowledge of a selected eigenvalue and preserve its eigenspace. The positive definiteness of the Hermitian part is inherited by the matrices in the generalized Hermitian eigenvalue problem. The position of the selected eigenspace in the ordering of the eigenvalues is also preserved under certain conditions. The effect of using approximate eigenvalues in the transformation is analyzed and numerical experiments are presented.     

The effect of ordering on preconditioned conjugate gradients

We investigate the effect of the ordering of the unknowns on the convergence of the preconditioned conjugate gradient method. We examine a wide range of ordering methods including nested dissection, minimum degree, and red-black and consider preconditionings without fill-in. We show empirically that there can be a significant difference in the number of iterations required by the conjugate gradient method and suggest reasons for this marked difference in performance.We also consider the effect of orderings when an incomplete factorization which allows some fill-in is performed. We consider the effect of automatically controlling the sparsity of the incomplete factorization through drop tolerances and level of fill-in.     

A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices

Summary In this paper we describe a block version of Arnoldi's method for computing a few eigenvalues with largest or smallest real parts. The method is accelerated via Chebyshev iteration and a procedure is developed to identify the optimal ellipse which encloses the spectrum. A parallel implementation of this method is investigated on the eight processor Alliant FX/80. Numerical results and comparisons with simultaneous iteration on some Harwell-Boeing matrices are reported.     

Differential equations for the analytic singular value decomposition of a matrix

Summary This paper is concerned with finding a smooth singular value decomposition for a matrix which is smoothly dependent on a parameter. A previous approach to this problem was based on minimisation techniques, here, in contrast, a system of ordinary differential equations is derived for the decomposition. It is shown that the numerical solution of an initial value problem associated with these differential equations provides a feasible approach to the solution of this problem. Particular consideration is given to the situation which arises with equal modulus singular values which lead to indeterminacies in the evaluations needed for the numerical solution. Examples which illustrate the behaviour of the method are included.     

Numerical experiments with two approximate inverse preconditioners

We present the results of numerical experiments aimed at comparing two recently proposed sparse approximate inverse preconditioners from the point of view of robustness, cost, and effectiveness. Results for a standard ILU preconditioner are also included. The numerical experiments were carried out on a Cray C98 vector processor. This work was partially supported by the GA AS CR under grant 2030706 and by the grant GA CR 205/96/0921.     

On proximity of Rayleigh quotients for different vectors and Ritz values generated by different trial subspaces

The Rayleigh quotient is unarguably the most important function used in the analysis and computation of eigenvalues of symmetric matrices. The Rayleigh-Ritz method finds the stationary values of the Rayleigh quotient, called Ritz values, on a given trial subspace as optimal, in some sense, approximations to eigenvalues.In the present paper, we derive upper bounds for proximity of the Ritz values in terms of the proximity of the trial subspaces without making an assumption that the trial subspace is close to an invariant subspace. The main result is that the absolute value of the perturbations in the Ritz values is bounded by a constant times the gap between the original trial subspace and its perturbation. The constant is the spread in the matrix spectrum, i.e. the difference between the largest and the smallest eigenvalues of the matrix. It’s shown that the constant cannot be improved. We then generalize this result to arbitrary unitarily invariant norms, but we have to increase the constant by a factor of .Our results demonstrate, in particular, the stability of the Ritz values with respect to a perturbation in the trial subspace.     

Towards a cost-effective ILU preconditioner with high level fill

There has been increased interest in the effect of the ordering of the unknowns on Preconditioned Conjugate Gradient (PCG) methods. A recently proposed Minimum Discarded Fill (MDF) ordering technique is effective in finding goodILU(l) preconditioners, especially for problems arising from unstructured finite element grids. This algorithm can identify anisotropy in complicated physical structures and orders the unknowns in an appropriate direction. TheMDF technique may be viewed as an analogue of the minimum deficiency algorithm in sparse matrix technology, and hence is expensive to compute for high levelILU(l) preconditioners.In this work, several less expensive variants of theMDF technique are explored to produce cost-effectiveILU preconditioners. The ThresholdMDF ordering combinesMDF ideas with drop tolerance techniques to identify the sparsity pattern in theILU preconditioners. The Minimum Update Matrix (MUM) ordering technique is a simplification of theMDF ordering and is an analogue of the minimum degree algorithm. TheMUM ordering method is especially effective for large matrices arising from Navier-Stokes problems.This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities.     

An incomplete-factorization preconditioning using repeated red-black ordering

Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, repeated red-black ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.     

AIR Tools — A MATLAB package of algebraic iterative reconstruction methods

We present a MATLAB package with implementations of several algebraic iterative reconstruction methods for discretizations of inverse problems. These so-called row action methods rely on semi-convergence for achieving the necessary regularization of the problem. Two classes of methods are implemented: Algebraic Reconstruction Techniques (ART) and Simultaneous Iterative Reconstruction Techniques (SIRT). In addition we provide a few simplified test problems from medical and seismic tomography. For each iterative method, a number of strategies are available for choosing the relaxation parameter and the stopping rule. The relaxation parameter can be fixed, or chosen adaptively in each iteration; in the former case we provide a new “training” algorithm that finds the optimal parameter for a given test problem. The stopping rules provided are the discrepancy principle, the monotone error rule, and the NCP criterion; for the first two methods “training” can be used to find the optimal discrepancy parameter.     

The spectral properties of the Hermitian and skew-Hermitian splitting preconditioner for generalized saddle point problems

In this paper, we consider the Hermitian and skew-Hermitian splitting (HSS) preconditioner for generalized saddle point problems with nonzero (2, 2) blocks. The spectral property of the preconditioned matrix is studied in detail. Under certain conditions, all eigenvalues of the preconditioned matrix with the original system being non-Hermitian will form two tight clusters, one is near (0, 0) and the other is near (2, 0) as the iteration parameter approaches to zero from above, so do all eigenvalues of the preconditioned matrix with the original system being Hermitian. Numerical experiments are given to demonstrate the results.     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

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 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.     

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.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

The ordering of tridiagonal matrices in the cyclic reduction method for Poisson's equation

Summary Discretization of the Poisson equation on a rectangle by finite differences using the standard five-point stencil yields a linear system of algebraic equations, which can be solved rapidly by the cyclic reduction method. In this method a sequence of tridiagonal linear systems is solved. The matrices of these systems commute, and we investigate numerical aspects of their ordering. In particular, we present two new ordering schemes that avoid overflow and loss of accuracy due to underflow. These ordering schemes improve the numerical performance of the subroutine HWSCRT of FISHPAK. Our orderings are also applicable to the solution of Helmholtz's equation by cyclic reduction, and to related numerical schemes, such as FACR methods.Dedicated to the memory of Peter HenriciResearch supported in part by the National Science Foundation under Grant DMS-870416     

A modified SSOR iterative method for augmented systems

Golub, Wu and Yuan [G.H. Golub, X. Wu, J.Y. Yuan, SOR-like methods for augmented systems, BIT 41 (2001) 71–85] have presented the SOR-like algorithm to solve augmented systems. In this paper, we present the modified symmetric successive overrelaxation (MSSOR) method for solving augmented systems, which is based on Darvishi and Hessari’s work above. We derive its convergence under suitable restrictions on the iteration parameter, determine its optimal iteration parameter and the corresponding optimal convergence factor under certain conditions. Finally, we apply the MSSOR method to solve augmented systems.     

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.