최소차수 순서화

1. 개요

최소차수 순서화 Minimum Degree Ordering
원조	마코비츠(1957, 비대칭) · 티니–워커(1967, 대칭)
규칙	매 단계 소거 그래프에서 차수가 가장 작은 정점을 소거
성격	국소 탐욕(greedy) — 이론적 보장 거의 없음, 실측 성능 우수
핵심 개량	몫 그래프 · 초변수 · 다중 소거(MMD) · 근사 차수(AMD)
대표 구현	AMD · COLAMD · SYMAMD (SuiteSparse), MATLAB amd

지금 당장 피해가 제일 적은 놈부터 처리한다. 앞날은 모른다. 그런데 이게 놀랍도록 잘 된다.

최소차수 순서화(minimum degree ordering, MD)는 희소 대칭 행렬을 가우스 소거법이나 촐레스키 분해로 분해할 때, 매 단계 현재 소거 그래프에서 이웃이 가장 적은 정점을 다음 소거 대상으로 고르는 그리디 알고리즘이다. 목표는 분해 중에 생기는 채움(fill-in)과 연산량을 줄이는 것이다. 전역 구조를 보고 그래프를 자르는 중첩절단과 정반대 철학의 국소 기법이고, 오늘날 중소 규모 희소 직접 솔버의 사실상 기본값이다.

희소 직접 솔버 문서는 여러 순서화의 위치를 한 표로 비교한다. 이 문서는 “가장 단순한 탐욕 규칙이 어떻게 반세기 동안 정교한 자료구조로 진화했는가”라는 각도를 판다. 알고리즘 규칙 자체는 한 줄인데, 그걸 빠르게 돌리는 방법이 30년짜리 연구 주제였다.

2. 규칙과 직관

대칭 행렬의 그래프에서 정점 $v$ 를 소거하면 $v$ 의 이웃 $\operatorname{adj}(v)$ 가 서로 전부 연결된 클리크가 된다. 차수가 $d$ 인 정점을 소거하면 새로 생길 수 있는 간선은 최대

$$\binom{d}{2} = \frac{d(d-1)}{2}$$

개이고, 그 단계의 연산량도 대략 $d^2$ 에 비례한다. 그러니 차수가 작은 정점부터 치우면 매 단계 피해의 상한이 작다. 이것이 최소차수의 전부다.

두 예가 직관을 준다.

• 트리. 잎은 차수 1이라 소거해도 채움이 0이다. 최소차수는 늘 잎부터 치우므로 트리 구조 행렬을 채움 없이 분해한다.
• 화살촉 행렬. 첫 행·첫 열만 꽉 찬 “별” 그래프에서 허브를 맨 먼저 소거하면 나머지 전체가 클리크가 되어 행렬이 통째로 채워진다. 최소차수는 허브(차수 $n-1$)를 맨 나중으로 미루고 잎들을 먼저 치워서 채움 0으로 끝낸다.

비대칭판의 원조는 선형계획법의 기저 행렬을 다루던 해리 마코비츠(1957)다. 그는 피벗 후보 $a_{ij}$ 에 대해 $(r_i - 1)(c_j - 1)$ ($r_i, c_j$ 는 행·열 비영 개수)을 최소화하는 규칙을 제안했고, 이것이 지금도 비대칭 희소 LU의 피벗 선택 기준으로 남아 있다.¹ 대칭판은 미국 본빌 전력청의 티니와 워커(1967)가 전력 계통의 회로망 방정식을 풀며 정리했다.

3. 순진한 구현이 왜 느린가

규칙을 그대로 구현하면 정점을 소거할 때마다 (1) 이웃들 사이에 간선을 실제로 추가하고 (2) 영향받은 정점들의 차수를 다시 센다. 문제는 둘 다다.

• 소거 그래프는 분해가 진행될수록 빽빽해진다. 채움 간선을 명시적으로 저장하면 메모리가 $\operatorname{nnz}(L)$ 수준까지 커진다.
• 한 번 소거할 때마다 클리크 전체의 차수가 바뀌어서, 차수 재계산이 알고리즘 비용을 지배한다.

1970~80년대의 개량은 전부 이 두 문제를 죽이는 데 쓰였다. 앨런 조지와 조지프 류의 1989년 리뷰가 이 진화사를 한 편으로 정리했다.²

4. 진화 — 몫 그래프에서 AMD까지

몫 그래프(quotient graph). 소거된 정점을 지우지 않고 원소(element)라는 특별한 정점으로 남긴다. 원소 $e$ 에 붙은 변수들은 “서로 전부 연결돼 있다”고 해석한다. 그러면 클리크를 간선 $O(d^2)$ 개 대신 원소 하나와 간선 $O(d)$ 개로 표현할 수 있다. 원소끼리 인접하면 하나로 흡수(element absorption)한다. 이 표현은 저장 공간이 원래 행렬의 $\operatorname{nnz}(A)$ 를 넘지 않는다는 결정적 성질이 있다 — 채움을 계산하면서도 채움을 저장하지 않는 셈이다.

초변수(supervariable)·구별 불가능 정점. 인접 집합이 (자기 자신 포함) 똑같은 정점들은 소거 순서상 늘 함께 움직인다. 유한요소법에서 한 절점의 $x, y, z$ 자유도가 전형적인 예다. 이들을 한 덩어리로 묶어 한 번에 처리(mass elimination)하면 그래프 크기가 자유도 수배 줄어든다.

다중 소거(multiple elimination, 류 1985). 최소 차수 정점이 여럿이고 서로 인접하지 않으면 한 번에 다 소거한 뒤 차수 갱신을 한 번만 한다. 이것을 묶은 것이 MMD(multiple minimum degree)이고, 1980년대 후반의 표준이었다.

외부 차수(external degree). 초변수 안의 자기 동료들은 차수에서 빼고 센다. 동료끼리는 어차피 함께 소거되므로 실제 채움과 무관하기 때문이다. 순서 품질이 눈에 띄게 좋아진다.

근사 최소차수(approximate minimum degree, AMD; 아메스토이·데이비스·더프 1996).³ 몫 그래프에서 정확한 차수를 세려면 여러 원소의 변수 집합 합집합 크기를 구해야 해서 비싸다. AMD는 이것을 포기하고 계산이 싼 차수 상한을 쓴다. 놀랍게도 상한으로 고른 순서의 품질이 정확 차수와 거의 같거나 오히려 나았고, 실행 시간은 MMD보다 크게 줄었다. 이것이 지금의 기본값이 된 이유다.

비대칭 LU 분해용으로는 $A^{\mathsf T}A$ 를 실제로 만들지 않고 그 패턴에 최소차수를 적용하는 COLAMD, 대칭 패턴 $A + A^{\mathsf T}$ 를 다루는 SYMAMD가 같은 계보다. MATLAB의 amd·colamd·symamd, SuiteSparse의 CHOLMOD·UMFPACK·KLU가 모두 이 코드를 쓴다.

5. 약점 — 근시안과 동점

최소차수는 전역 정보를 보지 않는다. 지금 차수가 작은 정점이 나중에 큰 클리크의 핵심 연결점이 되는 것을 막을 방법이 없다. 그래서 대규모 3D 격자처럼 분리자 구조가 뚜렷한 문제에서는 점근적으로 중첩절단에 진다.

동점 처리(tie-breaking)도 결과를 크게 흔든다. 정규 격자는 차수가 같은 정점투성이라, 같은 “최소차수”라도 동점에서 누구를 고르느냐로 채움이 크게 달라진다. 버먼·슈니트거(1990)는 동점 처리 방식에 따라 정규 격자에서도 최소차수가 최적보다 점근적으로 나쁜 결과를 낼 수 있음을 분석했다.⁴ 실무 구현이 입력 번호 순서에 따라 결과가 미묘하게 바뀌는 이유가 이것이다.

대안으로 최소 결핍(minimum deficiency, 일명 minimum fill) — 차수 대신 “소거하면 실제로 생길 채움 수”가 최소인 정점을 고르는 규칙 — 이 있다. 더 정확한 근시안이라 순서 품질이 대개 조금 낫지만, 매번 채움 수를 세는 비용이 훨씬 커서 표준은 못 됐다. 참고로 최소 채움 순서 자체를 찾는 문제는 NP-완전이다(야나카키스 1981). 휴리스틱 말고는 길이 없다는 공식 확인서다.

6. 검산 — 숫자로 본 위치

5점 라플라시안 $k \times k$ 격자와 7점 $k^3$ 격자에서 심볼릭 촐레스키로 $\operatorname{nnz}(L)$ 을 직접 셌다(정확 최소차수, 동점은 작은 번호 우선). 같은 표를 중첩절단 문서에서도 쓴다.

격자	$N$	자연 순서	최소차수	중첩절단(순수 기하)
2D 20×20	400	8,019	3,729	4,867
2D 63×63	3,969	250,109	69,090	86,408
3D 15³	3,375	715,289	226,236	293,801

이 크기에서는 최소차수가 채움에서 이긴다. 그런데 연산량 지표 $\sum_j c_j^2$ 로 보면 3D 15³ 에서 최소차수 $4.65\times10^7$, 중첩절단 $4.83\times10^7$ 로 거의 붙었고, 10³ 에서는 격차가 1.29배였다. 문제가 커질수록 중첩절단이 따라오는 추세라서, 수십만 자유도를 넘는 3D 문제에서 METIS 순서가 기본값으로 바뀌는 실무 관행과 맞아떨어진다. 실무 ND도 하위 조각은 결국 최소차수로 마무리하니, 둘은 경쟁자라기보다 위아래로 나눠 맡는 동료에 가깝다.

7. 관련 문서

• 희소 직접 솔버 · 중첩절단 · 촐레스키 분해 · LU 분해
• 가우스 소거법 · 희소행렬 · 그리디 알고리즘 · NP-완전
• METIS · 역 커스힐-맥키 · SuiteSparse · MUMPS
• 강성행렬 · 유한요소법 · 선형계획법

8. Footnotes

1. 그 마코비츠가 맞다. 1990년 노벨 경제학상을 받은 포트폴리오 이론의 해리 마코비츠다. 랜드 연구소에서 선형 계획법 계산을 하다가 희소 행렬 피벗 규칙을 남겼고, 수치해석 쪽에서는 “마코비츠 판정법”으로 지금도 매일 불린다. ↩

2. 제목부터 The evolution of the minimum degree ordering algorithm이다. 알고리즘 하나의 “진화사”를 SIAM Review에 실을 만큼 사연이 길었다는 뜻이고, 실제로 읽어 보면 거의 자료구조 고고학이다. ↩

3. 근사를 썼더니 정확한 것보다 순서가 좋거나 같게 나왔다는 결과는 처음 보면 킹받는다. 그런데 최소차수 자체가 근시안 휴리스틱이라 “정확한 차수”가 정답의 기준이 아니었다는 걸 떠올리면 덜 이상하다. ↩

4. 동점 처리에 따라 결과가 갈리는 탓에, 순서화 논문들은 비교 실험 전에 입력 행렬을 무작위로 순열해 여러 번 돌리는 것이 국룰이 됐다. 운빨 요소를 통계로 빼는 셈이다. ↩