Enabling implicit time integration for compressible flows by partial coloring: A case study of a semi-matrix-free preconditioning technique.

Abstract

Numerical techniques involving linearizations of nonlinear functions require the repeated solution of systems of linear equations whose coefficient matrix is the Jacobian of that nonlinear function. If the Jacobian is large and sparse, iterative methods offer the advantage that they involve the Jacobian solely in the form of matrix-vector products. Techniques of automatic differentiation are capable of evaluating these Jacobian-vector products efficiently and accurately in a matrix-free fashion. So, the numerical technique does not need to store the Jacobian explicitly. When the solution of the linear system is preconditioned, however, there is currently a considerable gap between automatic differentiation and preconditioning because the latter typically requires to explicitly store the Jacobian in a sparse data format. In an attempt to bridge this gap, we introduce an approach based on block diagonal preconditioning that brings together known computational building blocks in a novel way. The crucial methodological ingredient to that approach is the formulation and solution of a partial coloring problem in which colors are assigned to only a subset of the vertices of the underlying graph. Numerical experiments are reported that demonstrate the feasibility of this approach.