스카이라인 저장

1. 개요

스카이라인 저장 Skyline (Profile) Storage
다른 이름	프로파일 저장 · 포락선 저장 · 가변 띠 저장
저장하는 것	각 열의 첫 비영 원소부터 대각까지 (안쪽 0 포함)
보조 배열	대각 원소 주소 하나 (Bathe 코드의 MAXA)
짝꿍 알고리즘	능동 열(active column) LDLT · 촐레스키
전성기	1970~80년대 유한요소 구조해석 코드

도시 스카이라인처럼, 각 열의 가장 높은 빌딩 꼭대기까지만 저장한다. 그 위 하늘은 영원히 0이다.

스카이라인 저장(skyline storage)은 대칭 희소행렬의 상삼각부를 열마다 첫 비영 원소부터 대각선까지 연속으로 저장하는 방식이다. 그 사이의 0도 함께 저장한다. 손해 같지만 이유가 있다. 촐레스키 분해나 LDL^T 분해를 하면 그 0들이 어차피 채워지고(fill-in), 반대로 첫 비영 원소 위쪽은 분해 내내 0으로 남는다. 그래서 스카이라인 영역은 “분해 결과가 들어갈 자리를 정확히, 미리” 잡아 둔 배열이 된다.

제닝스(Jennings, 1966)의 가변 띠폭 방식에서 출발해, 배스·윌슨(Bathe & Wilson)의 교과서 루틴 COLSOL 로 널리 퍼지며 구조해석 코드의 표준 직접법이 됐다.¹ 유한요소법 강성행렬을 푸는 직접법으로 20여 년간 업계를 지배했고, 지금은 다중전선·초절점 솔버에 자리를 내줬지만 교육용·임베디드·중소 규모 코드에서는 여전히 쓰인다. 왜 채움이 포락선 밖으로 안 나가는지, 순서화가 포락선을 얼마나 줄이는지는 역 커스힐-맥키가 자세히 다루니, 이 문서는 자료구조와 그 위에서 도는 분해에 집중한다.

2. 자료구조

$n\times n$ 대칭행렬에서 열 $j$ 의 높이 $h_j$ 를 대각 위로 첫 비영 원소까지의 거리 $j - m_j$ 로 정의한다($m_j$ 는 그 열 첫 비영 원소의 행 번호). 열 $j$ 는 $h_j + 1$ 칸을 쓴다.

배스 방식의 관례로 5×5 예를 보자. 열 높이가 $(0,1,1,2,4)$ 라면

• 열 1: $a_{11}$
• 열 2: $a_{22}, a_{12}$
• 열 3: $a_{33}, a_{23}$
• 열 4: $a_{44}, a_{34}, a_{24}$ — $a_{34}=0$ 이어도 저장
• 열 5: $a_{55}, a_{45}, a_{35}, a_{25}, a_{15}$

를 대각부터 위로 한 줄짜리 배열 A 에 이어 붙이고, 각 대각 원소의 주소를 MAXA = [1, 2, 4, 6, 9, 14] 로 둔다(마지막 칸은 끝+1). 열 $j$ 의 높이는 MAXA[j+1] - MAXA[j] - 1 로 바로 나오고, $a_{ij}$ 의 주소는 MAXA[j] + (j - i) 다. 저장량은 $\sum_j (h_j+1) = 13$ 칸으로, 꽉 찬 상삼각(15칸)과 비교하면 별것 아니지만 실제 FEM 행렬에선 차이가 수십~수백 배가 된다.

유한요소에서 높이 구하기. 강성행렬을 조립하기 전에 높이를 미리 알 수 있다. 요소 하나가 자유도 집합 $\{d_1,\dots,d_p\}$ 를 연결하면, 그 집합의 각 자유도 $j$ 에 대해 $m_j \leftarrow \min(m_j, \min_k d_k)$ 를 갱신하면 된다. 요소 루프 한 바퀴로 MAXA 가 완성되고, 그다음 조립은 계산된 주소에 더하기만 한다. 행렬 그래프를 만들 필요조차 없다는 게 이 방식이 사랑받은 이유다.

3. 능동 열 분해

스카이라인 저장 위에서는 열 단위로 LDL^T 를 진행하는 크라우트(Crout)형 알고리즘이 자연스럽다. 열 $j$ 를 처리할 때 필요한 것은 왼쪽 열들의 결과뿐이라 “지금 계산 중인 열”만 활성(active) 상태가 된다.

열 $j$ 에서 $i = m_j+1, \dots, j-1$ 에 대해

$$g_{ij} = a_{ij} - \sum_{r=\max(m_i, m_j)}^{i-1} l_{ri}\, g_{rj},$$

그다음

$$l_{ij} = g_{ij}/d_i,\qquad d_j = a_{jj} - \sum_{r=m_j}^{j-1} l_{rj}\, g_{rj}$$

로 열 $j$ 의 $L$ 성분과 $D$ 대각을 원래 자리에 덮어쓴다. 합의 하한 $\max(m_i, m_j)$ 가 핵심이다. 두 열의 스카이라인이 겹치는 구간에서만 내적을 하면 되므로, 모든 연산이 저장된 연속 배열 위의 짧은 내적이 된다. 1970~80년대 벡터 슈퍼컴퓨터에서 이 내적 구조가 잘 벡터화됐고, 열 단위로 디스크에서 블록을 읽어 오는 out-of-core 구현도 쉬웠다.

연산량은 대략 $\sum_j h_j^2/2$ 번의 곱셈-덧셈이다. 직접 구현해 2차원 5점 라플라시안($20\times20$ 격자, $n=400$)에 돌려 보니 $LDL^{\mathsf T}$ 재구성 오차(최대 절댓값) $4.4\times10^{-16}$, 곱셈-덧셈 78,679 회로 추정치 76,010 과 맞았다. 해 구하기(전진·후진 대입)는 저장량에 비례하는 $O(\sum_j h_j)$ 다.

4. 검산 — 무엇을, 얼마나 저장하나

$k\times k$ 격자 5점 라플라시안($n = k^2$)을 자연 순서, 역 커스힐-맥키(RCM), 무작위 순서로 번호를 매기고 저장량·연산량을 쟀다. $k=60$, $n = 3600$, 상삼각 비영 원소는 10,680 개다.

방식	저장 칸 수	최대 높이	분해 연산량
꽉 찬 상삼각	6,481,800	—	$7.8\times10^{9}$
띠 저장 (자연 순서, 폭 60)	219,600	60	$6.5\times10^{6}$
스카이라인 (무작위 순서)	4,304,755	3,552	$4.4\times10^{9}$
스카이라인 (자연 순서)	216,059	60	$6.4\times10^{6}$
스카이라인 (RCM)	149,330	60	$3.3\times10^{6}$

세 가지가 보인다.

1. 번호가 전부다. 같은 행렬이 무작위 번호면 꽉 찬 행렬의 2/3 를 저장한다. 스카이라인은 자료구조라기보다 “좋은 순서화가 있다는 전제” 위에서만 성립하는 약속이다.
2. 정규 격자 자연 순서에서는 띠 저장과 거의 같다. 모든 열 높이가 비슷하면 스카이라인의 이점이 사라진다. 이점이 커지는 건 높이가 들쭉날쭉한 비정렬 격자, 여러 부품이 붙은 조립 구조물이다.
3. RCM 은 높이의 최대값(띠폭)은 그대로 두고 합을 줄인다. 연산량은 높이 제곱합이라 거의 절반이 됐다. 이 용도에는 깁스-풀-스톡마이어·슬론(Sloan) 같은 프로파일 축소 알고리즘이 더 잘 듣는 경우가 많다.

그래도 한계는 분명하다. 2차원 격자에서 프로파일 방식의 저장은 $O(n^{3/2})$, 연산은 $O(n^2)$ 이다. 중첩절단은 같은 문제에서 채움 $O(n\log n)$, 연산 $O(n^{3/2})$ 을 낸다(George, 1973). $n$ 이 수백만이면 이 차이가 몇 시간과 몇 분의 차이다.

5. 왜 밀려났고, 어디에 남았나

1980년대 이후 직접법의 주류는 최소차수 순서화·중첩절단으로 채움 자체를 줄이고, 다중전선(multifrontal, Duff & Reid 1983)·초절점 방식으로 밀집 블록 BLAS-3 연산을 끌어내는 쪽으로 넘어갔다. MUMPS·PARDISO·CHOLMOD 가 그 후손이다. 이들은 스카이라인처럼 “연속 구간”을 고집하지 않아서 저장이 훨씬 작고, 캐시·병렬 효율도 높다.

그래도 스카이라인이 남은 곳이 있다.

• 교과서와 교육용 FEM 코드. 배열 두 개(A, MAXA)와 이중 루프 하나로 직접법이 완성된다. 구현이 손에 잡히는 마지막 희소 직접법이다.
• 작은 문제의 반복 해. 수천 자유도짜리 행렬을 같은 구조로 수만 번 분해하는 비선형·시간적분 루프에서는 복잡한 심볼릭 분석 없이 바로 도는 단순함이 이긴다.
• 고유값 해석 레거시. 부분공간 반복법·란초스로 낮은 고유모드를 찾는 구조동역학 코드가 스카이라인 분해를 시프트 역반복의 엔진으로 오래 썼다.
• 비대칭판. 하삼각은 행 프로파일, 상삼각은 열 프로파일로 따로 저장하면 구조 대칭·값 비대칭 행렬(LU 분해)에도 그대로 쓸 수 있다. 피벗팅을 하면 구조가 깨지므로 대각 우세가 보장될 때만이다.²

6. 관련 문서

• 희소행렬 · 촐레스키 분해 · LU 분해 · 강성행렬 · 유한요소법
• 역 커스힐-맥키 · 깁스-풀-스톡마이어 · 최소차수 순서화 · 중첩절단
• 토머스 알고리즘 · MUMPS · 프론탈 해법 · LDL 분해

7. Footnotes

1. 한 세대의 구조공학 대학원생이 교과서 부록의 COLSOL 을 손으로 타이핑하며 희소 직접법을 배웠다. 복붙이 없던 시절의 국룰. ↩

2. 스카이라인 솔버에 “피벗팅 옵션”이 없는 건 게을러서가 아니라 피벗 한 번에 스카이라인이 무너지기 때문이다. 하늘에서 빌딩이 자라는 걸 원하는 도시계획은 없다. ↩