Search

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse-grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse-grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY An iterative method for finding the largest eigenvalue of a nonnegative tensor was proposed by Ng, Qi, and Zhou in 2009. In this paper, we establish an explicit linear convergence rate of the Ng-Qi-Zhou method for essentially positive tensors. Numerical results are given to demonstrate linear convergence of the Ng-Qi-Zhou algorithm for essentially positive tensors. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, a practical two-term acceleration algorithm is proposed, the interval of the parameter which guarantees the convergence of the acceleration algorithm is analyzed in detail. Further, the acceleration ratio of the new acceleration algorithm is obtained in advance. The new acceleration algorithm is less sensitive to the parameter than the Chebyshev semi-iterative method. Finally, some numerical examples show that the accelerated algorithm is effective. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

IDR ( s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are investigated for alleviating this bottleneck. First, a recently proposed IDR ( s) algorithm that is highly efficient and stable is reformulated in such a way that it has a single global synchronization point per iteration step. Second, the so-called test matrix is chosen so that the work, communication, and storage involving this matrix is minimized in multi-cluster environments. Finally, a methodology is presented for a-priori estimation of the optimal value of s using only problem and machine-based parameters. Numerical experiments applied to a 3D convection-diffusion problem are performed on the DAS-3 Grid computer, demonstrating the effectiveness of our approach. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Algebraic multigrid (AMG) is one of the most efficient and scalable parallel algorithms for solving sparse linear systems on unstructured grids. However, for large 3D problems, the coarse grids that are normally used in AMG often lead to growing complexity in terms of memory use and execution time per AMG V-cycle. Sparser coarse grids, such as those obtained by the parallel modified independent set (PMIS) coarsening algorithm, remedy this complexity growth but lead to nonscalable AMG convergence factors when traditional distance-one interpolation methods are used. In this paper, we study the scalability of AMG methods that combine PMIS coarse grids with long-distance interpolation methods. AMG performance and scalability are compared for previously introduced interpolation methods as well as new variants of them for a variety of relevant test problems on parallel computers. It is shown that the increased interpolation accuracy largely restores the scalability of AMG convergence factors for PMIS-coarsened grids, and in combination with complexity reducing methods, such as interpolation truncation, one obtains a class of parallel AMG methods that enjoy excellent scalability properties on large parallel computers. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper considers the inexact Barzilai–Borwein (BB) algorithm applied to saddle point problems. To this aim, we study the convergence properties of the inexact BB algorithm for symmetric positive definite linear systems. Suppose that gk and &gtilde;k are the exact residual and its approximation of the linear system at the kth iteration, respectively. We prove the R-linear convergence of the algorithm if ∥&gtilde;k – gk∥⩽η∥&gtilde;k∥ for some small η>0 and all k. To adapt the algorithm for solving saddle point problems, we also extend the R-linear convergence result to the case when the right-hand term ∥&gtilde;k∥ is replaced by ∥&gtilde;k–1∥. Although our theoretical analyses cannot provide a good estimate to the parameter η, in practice, we find that η can be as large as the one in the inexact Uzawa algorithm. Further numerical experiments show that the inexact BB algorithm performs well for the tested saddle point problems. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

When solving electromagnetic problems by finite element method, the resulting linear systems are ill-conditioned when the PML absorbing layers are adopted. Traditional Krylov iterative algorithms usually converge slowly or may even stagnate. In this paper, the combination of the inner–outer Flexible Generalized Minimum Residual Method (GMRES) and the symmetric successive overrelaxation (SSOR) preconditioning scheme is used to accelerate the iteration for solving a large sparse system of linear equations resulting from the analysis of EM problems by use of edge-based finite element method (FEM). The numerical results show that tens of times convergence improvement can be achieved compared with the conventional GMRES solver. © 2006 Wiley Periodicals, Inc. Microwave Opt Technol Lett 48: 1708–1712, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.21758 [ABSTRACT FROM AUTHOR]

The DEFLATED-GMRES(m, k) method is one of the major iterative solvers for the large sparse linear systems of equations, x = b. This algorithm assembles a preconditioner adaptively for the GMRES(m) method based on eigencomponents gathered from the Arnoldi process during iterations. It is usually known that if a restarted GMRES(m) method is used to solve linear systems of equations, the information of the smallest eigencomponents is lost at each restart and the super-linear convergence may also be lost. In this paper, we propose an adaptive procedure that combines the DEFLATED-GMRES(m, k) algorithm and the determination of a restart frequency automatically. It is shown that a new algorithm combining elements of both will reduce the negative effects of the restarted procedure. The numerical experiments are presented on three test problems by using the MIMD parallel machine AP3000. From these numerical results, we show that the proposed algorithm leads to faster convergence than the conventional DEFLATED-GMRES(m, k) method. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The solution of nonsymmetric systems of linear equations continues to be a difficult problem. A main algorithm for solving nonsymmetric problems is restarted GMRES. The algorithm is based on restarting full GMRES every s iterations, for some integer s > 0. This paper considers the impact of the restart frequency s on the convergence and work requirements of the method. It is shown that a good choice of this parameter can lead to reduced solution time, while an improper choice may hinder or preclude convergence. An adaptive procedure is also presented for determining automatically when to restart. The results of numerical experiments are presented. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we focus on the solution of shifted quasiseparable systems and of more general parameter‐dependent matrix equations with quasiseparable representations. We propose an efficient algorithm exploiting the invariance of the quasiseparable structure under diagonal shifting and inversion. This algorithm is applied to compute various functions of matrices. Numerical experiments show that this approach is fast and numerically robust. [ABSTRACT FROM AUTHOR]

This paper is devoted to the development of a finite volume method for the computation of turbulent flow fields on unstructured grids. The discretization of the inviscid fluxes is accomplished by means of the modern upwind scheme AUSMDV [35], whereby linear ansatz functions are considered on each control volume to achieve high resolution properties. Furthermore, a central scheme is used for the approximation of the viscous fluxes. The involved operator splitting technique leads to low memory requirement, yields high flexibility concerning the use of particular turbulence models, and preserves a possibly included second order time discretization. The time discretization is performed is an implicit manner, which enables large time steps in comparison with an explicit formulation. The linearization of the numerical flux functions as well as the turbulent and axisymmetric source terms leads to a linear system of equations including a large, sparse, and nonsymmetric matrix. Recently, a systematic investigation and comparison of different preconditioned Krylov subspace methods in the context of real engineering applications was presented [18]. Based on these results, the BiCGSTAB algorithm [31] preconditioned by an incomplete LU factorization is used to solve the linear system of equations. The scheme is finally validated on specific test cases, whereby the results are compared with experimental data, analytical solutions, and numerical simulations of other authors. [ABSTRACT FROM AUTHOR]

In the paper the use of a truncated envelope technique is discussed as a preconditioning for the conjugate gradient method for solving large linear systems of equations with symmetric positive-definite matrices. An algorithm to generate a truncated envelope is introduced. Computational experience with systems of linear equations from the Harwell-Boeing collection is presented to highlight the efficiency of this approach. [ABSTRACT FROM AUTHOR]

The paper is concerned with iterative algorithms for solving systems of linear algebraic equations where the coefficient matrix is large and sparse. Such systems often arise in the numerical solution of partial differential equations by finite difference or finite element methods. The algorithms considered include a basic iterative method, an acceleration procedure for speeding up the convergence of the basic iterative method and an adaptive procedure for determining any necessary iteration parameters. Algorithms are described both for the case where the coefficient matrix is symmetric and positive definite and for the nonsymmetrizable case. The ITPACK Project was established by the Center for Numerical Analysis at The University of Texas in 1974. The object of ITPACK was the study of iterative algorithms, using both theoretical and experimental methods. Several software packages are described which have been developed as part of the ITPACK project for carrying out experimental studies with a variety of algorithms over a wide range of problems. Recent work on the use of advanced computer architectures is briefly discussed. [ABSTRACT FROM AUTHOR]

Point iterative methods at which, at any one time only a single equation of the linear system is treated are well known. However, in recent times block (or line) iterative methods, in which a group of equations (or points on the grid mesh) are treated implicitly and solved directly by a specialized algorithm+ have become the standard techniques for solving the sparse linear systems derived from the finite difference/element discretization of a self-adjoint elliptic partial differential equation on a two-dimensional grid. The main concern of this paper is to construct new groupings of the mesh points of the network into four and nine points using the high order accurate nine-point finite difference equations and to investigate their advantages when used explicitly in the standard iterative methods. [ABSTRACT FROM AUTHOR]

Motivated by the Cayley–Hamilton theorem, a novel adaptive procedure, called a Power Sparse Approximate Inverse (PSAI) procedure, is proposed that uses a different adaptive sparsity pattern selection approach to constructing a right preconditioner M for the large sparse linear system Ax=b. It determines the sparsity pattern of M dynamically and computes the n independent columns of M that is optimal in the Frobenius norm minimization, subject to the sparsity pattern of M. The PSAI procedure needs a matrix–vector product at each step and updates the solution of a small least squares problem cheaply. To control the sparsity of M and develop a practical PSAI algorithm, two dropping strategies are proposed. The PSAI algorithm can capture an effective approximate sparsity pattern of A-1 and compute a good sparse approximate inverse M efficiently. Numerical experiments are reported to verify the effectiveness of the PSAI algorithm. Numerical comparisons are made for the PSAI algorithm and the adaptive SPAI algorithm proposed by Grote and Huckle as well as for the PSAI algorithm and three static Sparse Approximate Inverse (SAI) algorithms. The results indicate that the PSAI algorithm is at least comparable to and can be much more effective than the adaptive SPAI algorithm and it often outperforms the static SAI algorithms very considerably and is more robust and practical than the static ones for general problems. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Parallel two-stage multisplitting methods with overlap for the solution of linear systems of algebraic equations are studied. It is shown that, under certain hypotheses, the method with overlap is asymptotically faster than that without overlap. Experiments illustrating this phenomenon are presented. [ABSTRACT FROM AUTHOR]

A regularization procedure for linear systems of the type &Sigmat=1n fi (Zj)Xi = g(zj). J = 1, 2, .... n is presented, which is particularly useful in the case when z1, z2..... zn are close to each other. The associated numerical algorithm was tested on several examples for which analytic solutions do exist and was found to yield highly accurate results. [ABSTRACT FROM AUTHOR]