F-norm Minimization Based Sparse Approximate Inverse Preconditioning

Preconditioned Krylov iterative solvers have been commonly used in nowdays for solving large sparse linear systems.Sparse approximate inverse（SAI）preconditioning techniques are among one class of the most important general-purpose preconditioning techniques.In this thesis,we focus on F-norm minimization based SAI preconditioning.We propose a residual based sparse approximate inverse preconditioning procedure（RSAI）for the large sparse linear system Ax=b.Different from the SPAI algorithm proposed by Grote and Huckle[SIAM J.Sci.Comput.,18（1997）,pp.838–853.]that is based on the F-norm minimization and computes a sparse approximate inverse M≈A^-1by adaptively adding the most profitable indices at each loop,RSAI uses only the dom-inant other than all information on the current residual and augments sparsity patterns adaptively during loops.In order to control the sparsity of M,we develop two practical algorithms RSAI（f ix）and RSAI（tol）.RSAI（f ix）retains the prescribed number of large nonzero entries and adjusts their positions in each column of M among all available ones,in which the number of large entries is increased by a fixed number at each loop.In con-trast,the existing indices of M by SPAI are untouched and a few most profitable indices are added to each column of M from the new candidates in the next loop.RSAI（tol）is a tolerance based dropping algorithm and retains all large entries by dynamically dropping small ones below some tolerances,and it better suits for the problem where the number-s of large entries in the columns of A^-1differ greatly.Based on the idea of RSAI,we also propose a refined-SPAI by modifying SPAI.Numerical experiments on real-world problems demonstrate that RSAI（f ix）,RSAI（tol）and the refined-SPAI work well for preconditoning Ax=b.It has been known that the sparse approximate inverse preconditioning procedures SPAI and PSAI（tol）are costly to construct preconditioners for a large sparse nonsymmet-ric linear system with the coefficient matrix having at least one relatively dense column.This is also true for SPAI and RSAI（tol）procedure when the matrix has at least one relatively dense row.The matrix is called double irregular sparse if it has at least one relatively dense column and row.Double irregular sparse linear systems have a wide range of applications,and 24.4%of the nonsymmetric matrices in the Florida University collection are double irregular sparse.Making use of the Sherman-Morrison-Woodbury formula twice,we propose an approach that transforms a double irregular sparse problem into some double regular sparse ones with the same coefficient matrix,for which SPAI,PSAI（tol）and RSAI（tol）are efficient to construct preconditioners for the transformed double regular linear systems.We consider some theoretical and practical issues on such transformation approach,and develop a practical algorithm that first preconditions the transformed systems and then solves them by Krylov iterative solvers and finally recover an approximate solution of the original linear system with the prescribed accuracy.Nu-merical experiments confirm the very sharp superiority of our transformation algorithms to SPAI,PSAI（tol）and RSAI（tol）applied to the double irregular sparse linear problem directly.