역 커스힐-맥키

1. 개요

역 커스힐-맥키 Reverse Cuthill–McKee (RCM)
원형	커스힐 · 맥키 (1969)
역순 제안	앨런 조지 (1971)
목표	대칭 희소행렬의 대역폭 · 프로파일(포락선) 축소
핵심 연산	유사 주변 노드에서 시작하는 너비 우선 탐색
비용	거의 O(nnz) — 정렬 포함해도 선형에 가깝다
쓰는 곳	띠 · 스카이라인 솔버, ILU 전처리 순서, 캐시 지역성

0 이 아닌 원소들을 대각선 근처로 끌어모은다. 너비 우선 탐색 한 번이면 된다.

역 커스힐-맥키(reverse Cuthill–McKee, RCM) 순서화는 대칭 희소행렬의 행·열을 같은 순열로 재배열해 비영 원소를 대각선 가까이 모으는 그래프 알고리즘이다. 행렬의 인접 그래프에서 주변부 노드부터 너비 우선 탐색(BFS)을 돌리며 차수가 작은 이웃부터 번호를 매기고(커스힐-맥키, CM), 마지막에 그 번호를 뒤집는다. 대역폭은 CM 과 같지만 프로파일이 줄고, 그래서 촐레스키 분해의 채움(fill-in)이 줄어든다.

최소차수 순서화나 중첩절단이 “채움 자체를 최소화”하는 순서라면, RCM 은 “채움이 생길 수 있는 영역을 좁게 가두는” 순서다. 목표가 다르고, 그래서 지금도 각자 쓰임새가 있다. 이 문서는 두 이웃이 표 한 줄로만 다룬 RCM 을 알고리즘·이론·실측으로 풀어 본다.

2. 대역폭과 프로파일

대칭행렬 $A$ 의 $i$ 행에서 대각 왼쪽 첫 비영 원소의 열을 $f_i$ 라 하자. 그러면

$$\text{대역폭 } \beta(A) = \max_i\,(i - f_i), \qquad \text{프로파일(포락선 크기) } |\mathrm{Env}(A)| = \sum_i\,(i - f_i).$$

포락선(envelope)은 각 행에서 첫 비영 원소부터 대각선까지의 구간을 모은 영역이다. 이것이 중요한 이유는 하나다. 촐레스키 인자 $L$ 의 채움은 포락선 밖으로 나가지 않는다. 행 $i$ 의 첫 비영 원소 왼쪽은 소거 내내 0 으로 남기 때문이다. 그래서 포락선 크기 + $n$ 이 $\operatorname{nnz}(L)$ 의 상한이 되고, 이 영역만 저장하는 스카이라인(프로파일) 저장 방식이 1970~80년대 유한요소법 코드의 표준이었다. 띠 솔버는 더 거칠게 폭 $\beta$ 의 띠 전체를 저장하고 $O(n\beta^2)$ 에 푼다.

3. 알고리즘

1. 시작 노드 고르기. 그래프의 “가장자리”에 있는 노드, 정확히는 이심률이 큰 노드를 고른다. 진짜 주변 노드(지름의 끝점)를 찾는 건 비싸므로 유사 주변 노드(pseudo-peripheral node)를 쓴다. 조지·리우(1979)의 방법은 임의 노드에서 BFS 로 수준 구조(level structure)를 만들고, 가장 깊은 수준에서 차수가 가장 작은 노드로 옮겨 다시 BFS 하기를 이심률이 더 늘지 않을 때까지 반복한다. 보통 두세 번이면 멈춘다.
2. 너비 우선 번호 매기기. 시작 노드에 1번을 주고, 번호가 매겨진 순서대로 노드를 꺼내 아직 번호 없는 이웃들에게 차수가 작은 순으로 다음 번호를 준다. 이것이 커스힐-맥키(1969) 순서다.
3. 뒤집기. CM 순서를 역순으로 읽는다. 조지(1971)가 학위논문에서 이 역순이 거의 언제나 더 낫다는 것을 관찰했다.¹

연결 성분이 여럿이면 성분마다 반복한다. 전체 비용은 BFS 몇 번과 이웃 정렬이라 사실상 $O(\text{nnz})$ 다. 이게 RCM 의 가장 큰 미덕이다 — 수백만 미지수에서도 순서화 시간이 무시할 만하다.

BFS 가 왜 대역폭을 줄이는가: 같은 수준의 노드들이 연속 번호를 받고, 간선은 같은 수준 안이나 인접 수준 사이에만 있다. 그러니 한 행의 비영 원소는 “자기 수준과 앞 수준” 범위에 갇히고, 대역폭은 대략 인접한 두 수준 크기의 합으로 묶인다. 시작점을 주변부에서 고르는 이유가 여기서 나온다 — 수준이 많을수록(=그래프 지름 방향으로 펼칠수록) 각 수준이 얇아진다.

4. 왜 뒤집으면 좋아지나

뒤집어도 대역폭은 변하지 않는다. $|i-j|$ 는 순서를 뒤집어도 그대로이기 때문이다. 바뀌는 건 프로파일이다. 행 기준 포락선은 각 행의 “왼쪽 첫 원소”를 보는데, 순서를 뒤집으면 이것이 원래 순서의 열 기준 포락선(각 열의 “아래쪽 마지막 원소”)과 같아진다. CM 순서는 BFS 특성상 뒤쪽 번호의 노드가 앞쪽 노드 몇 개에 몰려 연결되는 “부채꼴” 모양을 만들기 쉬운데, 뒤집으면 그 부채꼴이 포락선 바깥으로 빠져나간다.

리우·셔먼(1976)은 이를 정리로 만들었다. RCM 의 포락선은 CM 의 포락선보다 결코 크지 않고, 이에 더해 RCM 순서로 촐레스키를 하면 채움이 포락선 안에 갇히는 데서 그치지 않고 포락선 일부가 비어 남을 수 있다. 반면 CM 순서에서는 포락선이 통째로 채워지는 경우가 흔하다.

5. 검산 — 무작위 번호를 다시 정리해 본다

5점 라플라시안 격자와 무작위 기하 그래프(단위 정사각형에 점을 뿌리고 반경 안의 쌍을 잇는, 비정렬 격자 흉내)를 무작위 번호로 섞은 뒤, 유사 주변 노드 + CM, 그리고 그 역순 RCM 을 적용했다. 대역폭 $\beta$, 포락선 크기, 심볼릭 촐레스키로 센 $\operatorname{nnz}(L)$ 이다.

그래프	순서	$\beta$	포락선	nnz(L)
격자 20×20	자연(행 우선)	20	7,619	8,019
	무작위	379	53,276	12,564
	CM	20	5,510	5,910
	RCM	20	5,510	5,910
격자 40×40	자연	40	62,439	64,039
	무작위	1,576	846,349	198,555
	CM · RCM	40	43,420	45,020
기하 그래프 $n=800$ (평균 차수 8.4)	무작위	791	256,616	80,869
	CM	59	28,377	29,177
	RCM	59	22,861	18,700
기하 그래프 $n=1500$ (평균 차수 9.1)	무작위	1,490	906,061	300,894
	CM	85	73,919	75,419
	RCM	85	61,876	52,515

읽을거리가 넷이다.

• 무작위 번호의 피해는 엄청나고 RCM 은 그걸 거의 공짜로 되돌린다. 40×40 에서 $\operatorname{nnz}(L)$ 이 19.9만에서 4.5만으로 줄었다. 메시 생성기가 뱉은 번호를 그대로 쓰는 것이 왜 금기인지 보여 준다.
• 정렬 격자에서는 CM 과 RCM 이 똑같았다. 모서리에서 출발한 BFS 수준이 대각선 띠라서 부채꼴이 생기지 않는다. 뒤집기의 효과는 구조가 불규칙할수록 커진다.
• 불규칙 그래프에서 CM 은 포락선을 꽉 채웠다($28{,}377 + 800 = 29{,}177$, 정확히 포락선 + 대각). RCM 은 포락선 자체가 19% 작은 데다 그 안(대각 포함)의 21% 가 끝까지 0 으로 남아, $\operatorname{nnz}(L)$ 이 CM 의 64% 였다. 리우·셔먼 정리가 말한 그 현상이다.
• 자연 순서의 격자에도 RCM 이 이득이다(8,019 → 5,910). 이 수치는 중첩절단 문서의 비교표 RCM 열과 일치한다. 같은 표에서 보듯 채움 최소화로는 최소차수 순서화가 RCM 을 크게 이긴다(20×20 에서 3,729).

6. 언제 RCM 을 쓰나

채움만 보면 RCM 은 AMD·ND 에 진다. 그럼에도 살아남은 이유는 채움 말고 다른 것을 원하는 자리가 많기 때문이다.

• 띠·스카이라인 솔버. 구조해석 상용 코드와 고전 FEM 코드는 프로파일 솔버를 오래 썼고, 그 앞단 순서화는 RCM·깁스-풀-스톡마이어(GPS, 1976) 같은 프로파일 축소 알고리즘이 맡았다. GPS 는 수준 구조를 양 끝에서 조합해 RCM 보다 대체로 조금 나은 대역폭을 비슷한 비용에 준다.
• ILU 전처리의 순서. 불완전 LU 분해는 채움을 버리는 근사라서, 버려지는 양이 적은 순서가 품질이 좋다. 실험적으로 ILU(0)·ILUT 앞에 RCM 을 거는 것이 무작위나 자연 순서보다 크리로프 반복 수를 줄이는 경우가 많고, 최소차수가 오히려 ILU 품질을 해치는 사례도 보고돼 왔다. 반복 솔버 앞에서 RCM 이 여전히 국룰인 이유다.²
• 캐시 지역성. 희소 행렬-벡터 곱에서 $\mathbf x$ 의 접근이 대각 근처로 모이면 캐시 적중률이 오른다. 순서화의 목적이 채움이 아니라 메모리 접근일 때 RCM 은 싸고 충분하다. 입자법·비정렬 격자 코드가 노드 재번호에 RCM 이나 공간 채움 곡선을 쓰는 이유가 이것이다.
• 도구. SciPy scipy.sparse.csgraph.reverse_cuthill_mckee, MATLAB symrcm, Boost Graph Library, 그리고 METIS 이전 시대의 SPARSPAK 이 대표 구현이다.

대역폭을 최소화하는 문제 자체는 NP-난해(파파디미트리우, 1976)라서, RCM·GPS 는 최적이 아니라 빠르고 쓸 만한 휴리스틱이라는 점도 기억해 둘 것.³

7. 관련 문서

• 희소행렬 · 희소 직접 솔버 · 촐레스키 분해 · LU 분해
• 최소차수 순서화 · 중첩절단 · METIS · 그래프 분할
• 너비 우선 탐색 · 깁스-풀-스톡마이어 · 스카이라인 저장 · 소거 트리
• 불완전 LU 분해 · 유한요소법 · GMRES

8. Footnotes

1. 순서를 뒤집는 것만으로 결과가 좋아진다는 발견은 수치해석 역사상 가장 가성비 좋은 기여 중 하나로 꼽힌다. 코드 한 줄(reverse())로 논문이 나왔다. ↩

2. “AMD 로 순서 바꿨더니 ILU 가 더 안 수렴해요”는 반복 솔버 게시판의 단골 질문이다. 직접 솔버의 정답이 전처리기의 정답은 아니다. ↩

3. 그래서 “최적 대역폭 순서”를 찾았다는 주장은 일단 의심하는 게 국룰이다. 찾았다면 튜링상 각이다. ↩