| 1 |
1
그래프 랭킹 수행 장치에 있어서,그래프의 구조에 따라서 상기 그래프에 대응되는 인접 행렬을 재정렬하는 재정렬부;상기 재정렬된 인접 행렬을 복수의 부분 행렬들로 분할하고, 상기 분할된 부분 행렬들을 상기 그래프의 랭킹 계산을 위한 선형 시스템에 대입함으로써 상기 그래프의 랭킹 계산을 위한 전처리를 수행하는 전처리 수행부; 및상기 전처리 결과를 이용하고, 상기 그래프의 랭킹을 나타내는 벡터에 포함된 적어도 하나의 원소에 대해서는 반복적인 연산을 수행함으로써 상기 벡터를 산출하는 반복연산 수행부를 포함하며,상기 반복연산 수행부는,상기 전처리 결과 얻은 행렬 중 적어도 하나의 프리컨디셔너(preconditioner)를 이용하여 상기 적어도 하나의 원소에 대한 반복연산을 수행하는 것을 특징으로 하는 장치
|
| 2 |
2
제1항에 있어서,상기 재정렬부는,둘 이상의 노드 재정렬 기법을 상기 인접 행렬에 적용함으로써 상기 인접 행렬을 재정렬하는 것을 특징으로 하는 장치
|
| 3 |
3
제2항에 있어서,상기 재정렬부는,데드 엔드 재정렬 기법 및 허브-앤-스포크 재정렬 기법을 상기 인접 행렬에 순차적으로 적용하는 것을 특징으로 하는 장치
|
| 4 |
4
제3항에 있어서,상기 재정렬부는,상기 선형 시스템에 대응되는 행렬로부터 분할된 부분행렬의 슈어 컴플리먼트(Schur complement)에 포함되는 논-제로(non-zero) 원소의 개수를 최소화하도록, 상기 허브-앤-스포크 재정렬 기법 수행시 이용되는 파라미터인 허브 선택률(hub selection ratio)을 선택하는 것을 특징으로 하는 장치
|
| 5 |
5
제1항에 있어서,상기 전처리 수행부는,상기 선형 시스템에 블록 제거 기법을 적용함으로써 상기 전처리를 수행하는 것을 특징으로 하는 장치
|
| 6 |
6
제1항에 있어서,상기 반복연산 수행부는,상기 적어도 하나의 원소에 대한 반복연산을 수행함에 있어서 GMRES (Generalized Minimal Residual) 기법을 활용하는 것을 특징으로 하는 장치
|
| 7 |
7
그래프 랭킹 수행 방법에 있어서,그래프의 구조에 따라서 상기 그래프에 대응되는 인접 행렬을 재정렬하는 단계;상기 재정렬된 인접 행렬을 복수의 부분 행렬들로 분할하고, 상기 분할된 부분 행렬들을 상기 그래프의 랭킹 계산을 위한 선형 시스템에 대입함으로써 상기 그래프의 랭킹 계산을 위한 전처리를 수행하는 단계; 및상기 전처리 결과를 이용하고, 상기 그래프의 랭킹을 나타내는 벡터에 포함된 적어도 하나의 원소에 대해서는 반복적인 연산을 수행함으로써 상기 벡터를 산출하는 단계를 포함하며,상기 벡터를 산출하는 단계는,상기 전처리 결과 얻은 행렬 중 적어도 하나의 프리컨디셔너(preconditioner)를 이용하여 상기 적어도 하나의 원소에 대한 반복연산을 수행하는 것을 특징으로 하는 방법
|
| 8 |
8
제7항에 있어서,상기 재정렬하는 단계는,둘 이상의 노드 재정렬 기법을 상기 인접 행렬에 적용함으로써 상기 인접 행렬을 재정렬하는 것을 특징으로 하는 방법
|
| 9 |
9
제8항에 있어서,상기 재정렬하는 단계는,데드 엔드 재정렬 기법 및 허브-앤-스포크 재정렬 기법을 상기 인접 행렬에 순차적으로 적용하는 것을 특징으로 하는 방법
|
| 10 |
10
제9항에 있어서,상기 재정렬하는 단계는,상기 선형 시스템에 대응되는 행렬로부터 분할된 부분행렬의 슈어 컴플리먼트(Schur complement)에 포함되는 논-제로(non-zero) 원소의 개수를 최소화하도록, 상기 허브-앤-스포크 재정렬 기법 수행시 이용되는 파라미터인 허브 선택률(hub selection ratio)을 선택하는 것을 특징으로 하는 방법
|
| 11 |
11
제7항에 있어서,상기 전처리를 수행하는 단계는,상기 선형 시스템에 블록 제거 기법을 적용함으로써 상기 전처리를 수행하는 것을 특징으로 하는 방법
|
| 12 |
12
제7항에 있어서,상기 벡터를 산출하는 단계는,상기 적어도 하나의 원소에 대한 반복연산을 수행함에 있어서 GMRES (Generalized Minimal Residual) 기법을 활용하는 것을 특징으로 하는 방법
|
| 13 |
13
그래프 랭킹 수행 장치에 의해 수행되며, 제7항에 기재된 방법을 수행하기 위해 매체에 저장된 컴퓨터 프로그램
|
| 14 |
14
제7항에 기재된 방법을 수행하는 프로그램이 기록된 컴퓨터 판독가능한 기록매체
|
