Balsa, Carlos Jorge da Rocha. Inexact Subspace Iteration to Accelerate the Solution of Linear Systems with Multiple RightHand Sides. PhD, Institut National Polytechnique de Toulouse, 2006

(Document in English)
PDF  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader 2MB 
Official URL: http://ethesis.inptoulouse.fr/archive/00000315/
Abstract
We propose a twophase acceleration technique for the solution of Symmetric and Positive Definite (SPD) linear systems with multiple righthand sides. In the first phase we compute some partial spectral information related to the ill conditioned part of the given coefficient matrix and, in the second phase, we use this information to improve the convergence of the Conjugate Gradient (CG) algorithm. This approach is adequate for large scale problems, like the simulation of time dependent differential equations, where it is necessary to solve consecutively several linear systems with the same coefficient matrix (or with matrices that present very close spectral properties) but with changing righthand sides. To compute the spectral information, we combine the block Conjugate Gradient algorithm with the Subspace Iteration to build a purely iterative algorithm, that we call BlockCGSI. We analyze the convergence of the blockCG algorithm and exploit the possibility of reducing the total amount of computational work by controlling in a same appropriate manner the accuracy during the solution of linear systems at each subspace iteration. We also improve the global convergence of this algorithm by using Chebyshev polynomials as a spectral filtering tool when building the starting vectors. The concept of “sliding window” was also introduced as an algorithmic feature that enables the computation of a nearinvariant subspace of any dimension. The spectral information computed by the BlockCGSI algorithm is then used to remove the effect of the smallest eigenvalues in two different ways: either by building a Spectral Low Rank Update (SLRU) preconditioner that basically adds the value 1 to the approximated eigenvalues, or by performing a deflation of the initial residual in order to remove part of the solution corresponding to the smallest eigenvalues. Both techniques yield important reductions of the total number of iterations and computational work in each subsequent runs of the Conjugate Gradient algorithm. We report on experiments on a 2D diffusion equation as well as on two applications coming from Computational Fluid Dynamics (CFD). The analysis of costs and benefits, in terms of floating point operations, helps to validate the strategy as a good way to speed up the solution of symmetric and positive definite linear systems
Item Type:  PhD Thesis 

Uncontrolled Keywords:  Numerical simulations  Sparse matrices  Block iterative methods  Preconditioning  Conjugate Gradient  Block Conjugate Gradient  Inexact subspace iteration  Partial spectral factorization  Eigenvalues and eigenvector approximation  Chebyshev polynomials  Convergence analysis  Stopping criterion 
Institution:  Université de Toulouse > Institut National Polytechnique de Toulouse  Toulouse INP (FRANCE) 
Laboratory name:  
Research Director:  Daydé, Michel and Palma, José Laginha 
Statistics:  download 
Deposited On:  21 Nov 2012 13:48 
Repository Staff Only: item control page