Solving Parametric Sparse Linear Systems by Local Blocking, II
Solving Parametric Sparse Linear Systems by Local Blocking, II
复制标题
通过局部分块求解参数稀疏线性系统，II
DOI：
10.1145/2733693.2733712
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
F. Kako
中科院分区：
文献类型：
--
作者：
Tateaki Sasaki;D. Inaba;F. Kako
本文作者Inaba和Kako在最近的一篇论文[6]中提出了局部阻塞，用于解决工业中出现的参数稀疏线性系统，因此所获得的解适合于确定最佳参数值。他们采用了图论的处理方法，其要点是选择满足若干限制的强连通子图，形成所谓的“特征系统”。然而，选择子图的方法是复杂的，似乎不适合大系统。本文在假设用户指定了特征系统的少量代表顶点的情况下，给出了一种寻找特征系统的简单方法。然后，我们提出了一个简单而令人满意的方法，将给定的图分解成强连通子图。该方法采用SCC（强连通分量）分解算法。新方法的复杂度为O（#（顶点）+#（边））。我们成功地测试了我们的方法，人工制作的100个顶点的三个图形显示不同的，但典型的功能。
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.