In this paper, a graph theoretic elimination process which models Gaussian elimination on sparse system of linear equations is considered. The theoretical results and efficient algorithms based on graph theory are presented. Then these algorithms are combined into a more general ordering algorithm which produces a perfect ordering if one exists, or a minimal fill-in, otherwise.
This algorithm is implemented on NOVA-840 and compared with other ordering algorithms, the minimum degree ordering algorithm and the minimum deficiency ordering algorithm. the several sample models are tested and their results are included to show how this algorithm works.
연립선형 방정식의 계수로 이루어진 nonsingular sparse 행렬에 Gaussian elimination 하는 과정을 graph theory 와 관련 시켜서 생각해 보았다. 해를 구하는 과정에서 발생하는 fill-in 의 갯수를 줄임으로 해서 연산갯수와 Storage 를 줄일 수 있으므로 eliminat 될 uertex 의 순서에 대해서 많은 연구가 되어 왔다.
여기서는 지금까지 연구된 uertex 의 degree 와 deficency 를 관련시켜 ordering 한 algorithm 들로구한 fill-in 을 minimal fill-in 까지 줄이고 그 minimal fill-in 을 발생시키는 ordering 을 찾는 새로운 algorithm 을 구성했다. 이 방법을 실제 응용분야에서 많이 발생하는 sample sparse 행렬에 test 해본 결과 이 perfect 은 perfect인 praph 에 대해서는 대단히 빨리 perfect ordering 을 찾을 수 있었다. 그리고 어떤 fill-in 을 minimal fill-in 으로 줄이는데 시간이 좀 더 걸리지만 같은 zero-nonzero 구조를 가진 행렬에 대해서 여러번 elimination 과정응 적용할때는 vertex 들의 elimination 순서가 아주 중요하므로 이 ordering algorithm 이 더욱 좋다.
