Solving Parametric Sparse Linear Systems by Local Blocking

摘要

In solving parametric sparse linear systems, we want 1) to know relations on parametric coefficients which change the system largely, 2) to express the parametric solution in a concise form suitable for theoretical and numerical analysis, and 3) to find simplified systems which show characteristic features of the system. The block triangularization is a standard technique in solving the sparse linear systems. In this paper, we attack the above problems by introducing a concept of local blocks. The conventional block corresponds to a strongly connected maximal subgraph of the associated directed graph for the coefficient matrix, and our local blocks correspond to strongly connected non-maximal subgraphs. By determining local blocks in a nested way and solving subsystems from low to higher ones, we replace sub-expressions by solver parameters systematically, obtaining the solution in a concise form. Furthermore, we show an idea to form simple systems which show characteristic features of the whole system.