Solving Parametric Sparse Linear Systems by Local Blocking, II

摘要

The present author, Inaba and Kako proposed local blocking in a recent paper [6], for solving parametric sparse linear systems appearing in industry, so that the obtained solution is suited for determining optimal parameter values. They employed a graph theoretical treatment, and the points of their method are to select strongly connected sub graphs satisfying several restrictions and to form the so-called "characteristic system". The method of selecting sub graphs is, however, complicated and seems to be unsuited for big systems. In this paper, assuming that a small number of representative vertices of the characteristic system are specified by the user, we give a simple method of finding a characteristic system. Then, we present a simple and satisfactory method of decomposing the given graph into strongly connected sub graphs. The method applies the SCC (strongly connected component) decomposition algorithm. The complexity of new method is O(# (vertex) +# (edge)). We test our method successfully by three graphs of 100 vertices made artificially showing different but typical features.