Sparse Approximate Inverse Preconditioning For Large Sparse Linear Systems

Solving large sparse linear systems is a central task in scientific and engineeringcomputing. The systems are from the real-world application such as the discretization ofelliptic and parabolic PDEs, the design and computer analysis of circuits, etc. Precondi-tioned Krylov subspace methods have been one class of the most well-known solvers forthese systems.Sparse approximate inverse (SAI) techniques have attracted the universal attentionduetotheirwideapplicabilityandhighparallelism,andhavebecomeoneclassofthemostpopular and important general-purpose preconditioning for Krylov solvers. To make SAIpreconditioners practical and effective, one has to use dropping techniques during thesetup process. That is to say, if the size of an entry is below some positive quantity (drop-ping tolerance), then it is set to zero. Therefore, dropping tolerance criteria play a centralrole in SAI preconditioning. However, one commonly takes some small quantities em-pirically or intuitively, say103,104, etc. as the dropping tolerances. Such empiricallychosen tolerances are not robust and at risk, may not be effective or even lead to failurein preconditioning. Therefore, dropping tolerances criteria strongly affect the robustnessand effectiveness of a SAI preconditioner and deserve enough attention, and there mustexist some deep mechanism behind them. However, this area still exists some kind ofblank in theory and technology. In the thesis, we establish a rigorous mathematical the-ory that reveals the intrinsic relationship between the dropping tolerances and the qualityand effectiveness of the SAI preconditioner. Using the theory, we derive an adaptivedropping criterion that is used to drop entries of small magnitude dynamically during thesetup process of the preconditioners, for F-norm minimization-based SAI and factorizedSAI,respectively. Numerical experimentsconfirm thetheoryand illustratetherobustnessand effectiveness of the dropping criteria.A sparse matrix is called irregular sparse if it has at least one dense column. Thereare quite a lot of irregular sparse problems in applications. Some SAI preconditioningprocedures such as SPAI and PSAI algorithms are usually effective for regular sparseproblems. However, when applied to irregular problems, they probably encounter intrin-sic difficulty, such as the low equality and the ineffectiveness of the preconditioner, or the large unacceptable cost. In the thesis, using the Sherman-Morrison-Woodbury formula asa powerful tool, we propose an approach to making the SAI algorithms more practicaland effective for irregular sparse problems. We carefully investigate and analyze severalimportant practical issues, and provide solid mathematical theory support, making ourapproach robust and effective. Numerical results from the vast majority of irregular prob-lems demonstrate the considerable superiority of our approach to the direct application ofSAI procedures to the original problem. In conclusion, our approach widely extends thepracticability of the SAI techniques.