In this paper, a new algorithm of finding a permutation matrix P for a given sparse, symmetric and positive definite is discussed.
This algorithm produces less bandwidth and requires less execution time than the reverse Cuthill-Mckee's algorithm and Wang's algorithm by using pseudo-diameter, distance of each node and rowward, columnward bandwidth of the associated graph G(A).
A simple example is given to show how this algorithm works. Several numerical experiments are included to illustrate the results.
연립선형방정식의 계수로 이루어진 SPARSE, SYMMETRIC, POSITIVE DEFINITE한 행렬이 여러 응용분야에서 발생한다.
근래에 이런 방정식의 해를 구하는데 필요한 STORAGE와 연산갯수를 줄이기 위해서 미리 BANDWIDTH를 줄이는 ALGORITHM에 대한 연구가 되어 왔었다. 본 논문에서는 주어진 행렬과 연관된 GRAPH에서 몇가지 새로운 개념들을 이용하고, 지금까지 연구되었던 많은 ALGORITHM중에서 특히 GIBBS의 ALGORITHM과 WANG의 ALGORITHM의 장점을 조합해서 ALGORITHM을 개선했다.
실제 응용분야에서 자주 생기는 특별한 SPARSE MATRIX와 임의로 만들어진 많은 SPARSE MATRIX에 대해 테스트 해본 결과 치환된 행렬의 BANDWIDTH와 치환하는데 소요된 시간이 VEVEVSE CUTHILL-MCKEE와 WANG의 ALGORITHM을 보다 작어졌음을 보여준다. 행렬과 연관된 GRAPH가 CONNECTED일때만 이 ALGORITHM을 적용할수 있지만 짧은 시간에 BANDWIDTH를 많이 줄인다.
특히 GRAPH가 규칙적이면 더 좋은 결과를 보여준다.