Data-sparse incomplete Cholesky factorization (Michal Outrata, Charles University, Prag)

22.05.2018 14:00

Consider the problem of solving a large system of linear algebraic equations, using Krylov subspace methods. In order to find the solution efficiently, the system often needs to be preconditioned, i.e, transformed prior to the iterative scheme. A feature of the system that often enables fast solution with efficient preconditioners is the structural sparsity of the corresponding matrix. A recent development brought another and slightly different phenomenon called the data sparsity. In contrast to the classical (structural) sparsity, the data sparsity refers to an uneven distribution of extractable information inside the matrix. In practice, the data sparsity of a matrix typically means that its blocks can be successfully approximated by matrices of low rank. Naturally, this may significantly change the character of the numerical computations involving the matrix. The talk focuses on finding ways to construct Cholesky-based preconditioners for the conjugate gradient method to solve systems with symmetric and positive definite matrices, exploiting a combination of the data and structural sparsity.

Methods to exploit the data sparsity are evolving very fast, influencing not only iterative solvers but direct solvers as well. Hierarchical schemes based on data sparsity concepts can be derived both from applications or algebraically (see, e.g., Hackbusch, 1999; Xia and Xin, 2017). As for the Cholesky factorization as a subtask of such schemes, while the general trend seems to move towards the Schur complement approaches combined with nested-dissection reorderings that introduce incompleteness via low-rank approximations (see, e.g., Kriemann and Le Borne 2014), in this talk the focus is on the column-oriented approach that allows for combination of the two mentioned types of approximations. On one hand, one can use approximate factor blocks using low-rank approximations. On the other hand classical concepts of incomplete factorizations can be used. But in order to put those ideas into practice new algorithmic approaches have to be introduced. Our starting point is the classical sparse incomplete column-oriented Cholesky factorization that is significantly modified in the above spirit.

Lieu

salle 623, Séminaire d'analyse numérique

entrée libre