MUMPS

1. 개요

MUMPS MUltifrontal Massively Parallel sparse direct Solver
종류	희소 직접 솔버 (다중전방 LU / LDLᵀ)
행렬	비대칭, 대칭 양정치, 대칭 부정치 — 실수·복소수, 단·배정밀도
병렬	MPI 분산 + OpenMP, 동적 스케줄링
언어	Fortran 90 (C 인터페이스 제공)
기원	EU 에스프리 PARASOL 프로젝트(1996~1999)
개발	CERFACS · ENSEEIHT-IRIT · Inria · CNRS · ENS 리옹 등, 현재 Mumps Technologies 가 유지
라이선스	CeCILL-C (자유 소프트웨어)

반복법이 수렴을 안 한다고? 그럼 그냥 분해해. 메모리가 허락하는 한.

MUMPS(MUltifrontal Massively Parallel sparse direct Solver)는 대규모 희소 연립방정식 $Ax=b$ 를 다중전방법(multifrontal method)으로 LU 또는 $LDL^T$ 분해해 푸는 분산 메모리 병렬 직접 솔버다. 1990년대 후반 유럽연합 PARASOL 프로젝트에서 출발해 프랑스 툴루즈·리옹의 연구진(CERFACS, ENSEEIHT-IRIT, Inria 등)이 키워 왔고, 오늘날 PETSc·FreeFEM·Code_Aster·MOOSE 등 수많은 해석 코드가 “직접법이 필요할 때” 부르는 사실상의 표준 공개 구현이다.

다중전방법의 원리 — 소거 트리, 전방행렬, 갱신행렬의 extend-add — 는 희소 직접 솔버 문서가 자세히 다룬다. 여기서는 MUMPS라는 소프트웨어가 그 원리를 어떻게 병렬화했고, 사용자가 어떤 손잡이를 잡아야 하는가에 집중한다. 이 바닥 신입이 처음 보는 오류 메시지가 대개 MUMPS의 INFOG(1)=-9 라는 데는 이유가 있다.

2. 세 단계와 JOB 코드

MUMPS의 인터페이스는 구조체 하나(DMUMPS_STRUC 등)에 행렬·옵션·결과를 다 담고, 같은 함수를 JOB 값만 바꿔 여러 번 부르는 방식이다.

JOB	단계	하는 일
−1	초기화	MPI 통신자 연결, 기본 옵션 채움
1	해석(analysis)	순서화, 기호 분해, 소거 트리·메모리 예측, 프로세스 배정
2	분해(factorization)	수치 분해 — 시간 대부분
3	풀이(solve)	전진·후진 대입, 선택적으로 반복 정밀화·오차 추정
4, 5, 6	묶음	1+2, 2+3, 1+2+3
−2	종료	내부 메모리 해제

이 분리가 실무에서 결정적이다. 희소 패턴이 같으면 해석은 한 번, 값이 바뀌면 분해만 다시, 우변이 바뀌면 풀이만 다시 한다. 뉴턴 반복의 야코비안(패턴 고정, 값 변화), 주파수 스윕(행렬 변화), 다중 하중 케이스(우변만 변화)가 각각 다른 단계만 반복한다. 비대칭은 SYM=0, 대칭 양정치는 SYM=1, 일반 대칭(부정치 포함)은 SYM=2 로 지정하는데, 양정치가 확실할 때만 SYM=1 을 써야 한다. 아니면 피벗 없는 촐레스키가 음의 피벗에서 멈춘다.

3. 병렬화 — 트리 병렬과 노드 병렬

MUMPS는 해석 단계에서 소거 트리의 노드를 세 부류로 나눈다.

• 유형 1 노드: 트리 아래쪽의 작은 전방행렬. 한 프로세스가 통째로 처리한다. 서로 다른 부분트리는 독립이라 트리 병렬이 공짜로 나온다.
• 유형 2 노드: 위쪽의 큰 전방행렬. 한 “마스터” 프로세스가 피벗 블록을 맡고, 기여 블록의 행들을 여러 “슬레이브” 프로세스에 1차원으로 나눠 맡긴다. 슬레이브를 누구로 할지는 분해 도중 동적으로 그 순간 일이 적은 프로세스를 골라 정한다.
• 유형 3 노드: 트리 뿌리(가장 큰 분리자). 2차원 블록 순환 분배로 ScaLAPACK에 넘겨 밀집 분해한다.

2001년 논문 제목이 “완전 비동기 다중전방 솔버, 분산 동적 스케줄링”인 이유가 이 유형 2 처리다. 정적 배정은 해석 단계의 예측을 믿어야 하는데, 수치 피벗팅 때문에 실제 작업량이 예측과 달라지므로 동적 스케줄링이 그 오차를 흡수한다. 2006년 이후에는 메모리 사용량까지 고려하는 혼합 스케줄링이 들어갔다.

결과적으로 확장성은 트리 모양에 크게 좌우된다. 중첩절단 순서(METIS·SCOTCH)는 균형 잡힌 덤불형 트리를 만들어 병렬화에 유리하고, 최소차수 순서화(AMD 계열)는 작은 문제의 채움은 적지만 트리가 길쭉해 병렬 확장성이 떨어진다. 순서화는 ICNTL(7)(순차 해석)로 고르며 AMD·AMF·QAMD·PORD·METIS·SCOTCH 와 자동 선택을 지원한다. 병렬 해석(ICNTL(28))을 켜면 ParMETIS·PT-SCOTCH 를 쓴다.

4. 피벗팅과 “지연 피벗”

대칭 부정치·비대칭 행렬은 안정성을 위해 수치 피벗팅이 필요하다. 그런데 다중전방법에서 한 전방행렬 안의 피벗 후보는 그 노드에서 소거하기로 정해진 변수들(완전 합산된 행·열)뿐이다. 문턱 부분 피벗팅 기준(대각 후보가 같은 열 최대 원소의 일정 비율 이상, 비율은 CNTL(1))을 통과하는 후보가 없으면, 그 변수의 소거를 부모 노드로 미룬다(delayed pivot).

미뤄진 변수는 부모의 전방행렬을 키우고, 그게 다시 위로 미뤄지면 눈덩이가 된다. 해석 단계의 메모리 예측은 이걸 모른다. 그래서 분해 단계에서

• INFOG(1) = -9: 주 작업공간 부족

이 뜬다. 국룰 처방은 ICNTL(14)(예측 대비 작업공간 증가율, 백분율)를 올리는 것이다. 20 → 50 → 100 으로 키워 보고, 그래도 안 되면 문제의 조건 자체를 의심한다. 대칭 부정치 안장점 문제(비압축성 유동의 속도-압력, 혼합 유한요소)가 지연 피벗의 단골 원천이다. 이때는 대칭 행렬용 최대 매칭 기반 스케일링·순서화 옵션을 켜는 것이 효과가 크다.¹

특이 행렬이나 거의 특이한 행렬은 ICNTL(24) 로 영 피벗 검출을 켜면 문턱 이하 피벗을 기록하고 계속 진행해, 영공간 차원과 기저를 얻을 수 있다. 부유 구조물의 강체 모드나 순수 노이만 문제의 상수 모드를 찾을 때 쓴다.

5. 메모리 벽을 미루는 손잡이

3차원 문제에서 직접법의 적은 연산이 아니라 메모리다(정칙 3D 격자에 중첩절단을 쓰면 인자 크기 $O(N^{4/3})$). MUMPS는 이 벽을 미루는 장치를 몇 개 갖고 있다.

• 외부 메모리(out-of-core, ICNTL(22)): 분해된 인자를 디스크로 내보낸다. 활성 전방행렬만 메모리에 둔다. 풀이 단계가 디스크 I/O 에 묶여 느려지지만 “돌기는 돈다”.
• 메모리 상한(ICNTL(23)): 프로세스당 최대 작업공간(MB)을 박아 두면 ICNTL(14) 추정 대신 그 한도를 쓴다.
• 블록 저랭크(BLR) 압축(ICNTL(35), 허용 오차 CNTL(7)): 전방행렬의 비대각 블록이 수치적으로 저랭크 근사가 가능하다는 성질을 이용해 인자를 압축한다. 타원형 문제에서 연산과 메모리를 크게 줄이며, 오차 $\varepsilon$ 을 허용한 근사 분해라서 반복 정밀화나 크리로프 법의 전처리기로 쓰는 것이 정석이다. 2015년 SIAM 논문 이후 5.x 판에 정식 기능으로 들어갔다.
• 슈어 보수 출력(ICNTL(19)): 일부 변수(예: 계면 자유도)를 남기고 나머지만 소거해 슈어 보수를 돌려준다. 영역 분할법·하위구조화의 국소 솔버로 쓰는 기능이다.

6. 언제 MUMPS를 부르나

• 반복법이 안 듣는 행렬: 조건이 나쁜 구조 문제(얇은 쉘, 큰 강성 대비), 고주파 전자기·음향의 부정치 헬름홀츠, 접촉·구속이 섞인 안장점 계. 대수적 다중격자가 실패할 때 마지막 보루.
• 우변이 많은 문제: 분해 한 번을 수백 번 재사용한다. 주파수 영역 해석의 다중 포트, 감도 해석의 수반 방정식.
• 전처리기 내부: 영역 분할의 부분영역 풀이, 다중격자의 최조립 격자 풀이, 블록 전처리기의 한 블록. PETSc에서는 -pc_type lu -pc_factor_mat_solver_type mumps 한 줄이다.
• 결정식이 필요할 때: ICNTL(33) 으로 행렬식을 (가수·지수 분리해) 돌려준다. 고유값 계수 세기나 실베스터 관성 법칙에 기반한 관성 검사에 쓴다.

반대로 수백만 이상 자유도의 3D 확산·탄성 문제는 좋은 전처리 반복법이 메모리·시간 모두 이긴다. 경계선은 문제마다 다르지만, “일단 MUMPS로 정답을 만들어 두고 반복법을 그 정답에 맞춰 튜닝한다”는 순서는 어디서나 통하는 국룰이다.²

7. 실무 체크리스트

1. 입력 형식. 기본은 좌표 형식(COO: 행·열·값 세 배열), 1부터 세는 인덱스다. C 코드에서 0부터 넘기면 첫 행·열이 통째로 사라진 이상한 행렬이 된다. 대칭 행렬은 한쪽 삼각만 넘긴다(양쪽 다 넘기면 중복 원소가 더해진다).
2. 분산 입력. ICNTL(18) 로 각 프로세스가 자기 원소만 넘기게 하라. 랭크 0이 전체 행렬을 모으는 기본 방식은 큰 문제에서 메모리 병목이다.
3. 오류 코드부터 본다. INFOG(1) 이 음수면 실패. −9(작업공간), −10(수치적으로 특이), −13(할당 실패)이 흔하다. INFOG(2) 에 보조 정보가 있다.
4. 정확도 확인. ICNTL(11) 로 오차 해석을 켜면 후진 오차 추정치를 돌려준다. 잔차를 직접 계산해 조건수와 함께 보는 습관이 안전하다.
5. MPI × OpenMP 비율. 최근 판은 노드 안 OpenMP 스레드를 잘 쓴다. 노드당 MPI 랭크를 줄이고 스레드를 늘리면 메모리 중복이 줄어 더 큰 문제가 들어가는 경우가 많다.³

8. 관련 문서

• 희소 직접 솔버 · 희소행렬 · LU 분해 · 촐레스키 분해 · 가우스 소거법
• 중첩절단 · 최소차수 순서화 · 소거 트리 · METIS
• ScaLAPACK · LAPACK · MPI · PETSc · SuiteSparse
• 슈어 보수 · 영역 분할법 · 안장점 문제 · 저랭크 근사 · 전처리기

9. Footnotes

1. 이름이 질병 이름(볼거리, mumps)과 같아서 “MUMPS에 걸렸다”는 농담이 저절로 나온다. 증상은 INFOG(1)=-9, 처방은 ICNTL(14) 증량. ↩

2. 직접법은 “느리지만 답은 낸다”, 반복법은 “빠르지만 수렴은 신에게 맡긴다”. 둘 다 써 본 사람만이 현생의 마감 앞에서 어느 쪽에 걸지 안다. ↩

3. 반대로 노드당 랭크를 코어 수만큼 꽉 채우면 각 랭크가 MPI 버퍼와 중복 구조를 따로 들고 있어, 계산은 같은데 메모리만 먼저 터지는 킹받는 상황이 나온다. ↩