# 블록 행렬(Block Matrix) 해법

#### 블록 행렬의 개념

블록 행렬(block matrix)은 행렬을 보다 체계적으로 다루기 위해 행렬의 특정 부분을 하나의 “블록”이라 부르며, 이 블록을 단위로 묶어서 표현하는 방식을 말한다. 예를 들어, 어떤 행렬을 여러 개의 작은 행렬로 나누고, 이를 다시 배열하여 하나의 큰 행렬로 나타내면 그것이 곧 블록 행렬이 된다. 각 블록은 일반적으로 동일 차원의 행렬일 필요는 없으며, 이들을 특정 규칙에 따라 행과 열 방향으로 분할해 놓은 형태를 통칭한다.

블록 행렬을 이용하면 선형 시스템 $\mathbf{A}\mathbf{x} = \mathbf{b}$를 보다 구조적으로 파악할 수 있으며, 특정 조건에서 계산량을 획기적으로 줄이거나, 반복적으로 나타나는 서브행렬(sub-matrix)에 대한 처리를 간결하게 할 수 있다. 이 점이 블록 행렬 기법이 실제 대규모 계산에서 자주 활용되는 이유다.

행렬 $\mathbf{A}$를 블록 형태로 분할한다는 것은

$$
\mathbf{A} = \begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} \ \mathbf{A}*{21} & \mathbf{A}*{22} \end{pmatrix}
\\
\mathbf{x} = \begin{pmatrix} \mathbf{x}\_1 \ \mathbf{x}\_2 \end{pmatrix}
\\
\mathbf{b} = \begin{pmatrix} \mathbf{b}\_1 \ \mathbf{b}\_2 \end{pmatrix}
$$

와 같이 쓰는 것을 의미한다. 여기서 $\mathbf{A}*{11}, \mathbf{A}*{12}, \mathbf{A}*{21}, \mathbf{A}*{22}$는 각각 작지만 독립적인(혹은 함께 다루면 유리한) 행렬로 묶인 블록이다. 블록의 차원을 문제 상황에 맞게 설정하면, 해를 구하는 절차에서 연산을 효율적으로 조직할 수 있다.

#### 블록 행렬 분할과 병합

블록 행렬을 다루는 과정에서는 분할(partitioning)과 병합(merging)이 핵심 개념으로 등장한다. 구체적으로, 큰 행렬 $\mathbf{A}$를 여러 블록으로 나누어 문제를 해결할 때, 각 블록에서 부분 문제(sub-problem)를 풀고 나서 이를 다시 전체 해로 합치는 과정이 필요하다.

예를 들어, $\mathbf{A}*{11}, \mathbf{A}*{12}, \mathbf{A}*{21}, \mathbf{A}*{22}$ 각각을 이용해 서브문제를 구성하여 (적절한 전제조건 하에) 독립적으로 풀거나, 혹은 $\mathbf{A}*{11}, \mathbf{A}*{22}$만 분리하여 먼저 해를 구한 뒤 나머지 블록인 $\mathbf{A}*{12}, \mathbf{A}*{21}$을 이용해 후속 연산을 진행하는 블록 가우스 소거법(block Gaussian elimination) 등이 그 예다.

이러한 블록 단위 분할이 유용해지는 전형적인 상황 중 하나는 $\mathbf{A}$가 블록 삼각 행렬(block triangular matrix) 형태를 띨 때이다. 즉,

$$
\mathbf{A} = \begin{pmatrix} \mathbf{A}*{11} & \mathbf{0} \ \mathbf{A}*{21} & \mathbf{A}\_{22} \end{pmatrix}
$$

처럼 대각선을 기준으로 위아래 혹은 좌우 블록 중 일부가 영행렬이 되어 있을 때, 해석이 매우 간단해지며 계산 과정 또한 단순화된다. 물론 이런 이상적인 형태가 아니더라도, 구조적으로 특정 블록이 희소(sparse)하거나 특정 성질을 만족하면(대칭, 대각행렬, 밴드구조 등) 블록 단위 해법을 활용해 전체 연산을 최적화할 수 있다.

#### 블록 가우스 소거법의 소개

고전적 가우스 소거법을 확장한 형태로서, 큰 행렬을 블록으로 나누고 각 블록에 대해 소거 과정을 수행하는 기법을 블록 가우스 소거법(block Gaussian elimination)이라 부른다. 이는 각 단계에서 블록 연산을 통해 필요 부분만 갱신하거나, 혹은 국소적인 연산으로 일부 블록을 제거하고 다른 블록을 해석하는 과정을 반복함으로써 전체 해 $\mathbf{x}$를 구하게 해준다.

블록 가우스 소거법은 일반적인 $n\times n$ 행렬에서 단순 가우스 소거법을 수행하는 것에 비해 다음과 같은 계산 구조를 갖는다. (단, 여기서는 단순 비교를 위해 실제 구현 방식보다는 개념적 이해에 집중한다.)

먼저, 행렬 $\mathbf{A}$를 다음과 같이 $2\times 2$ 블록으로 분할했다고 하자.

$$
\mathbf{A} = \begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} \ \mathbf{A}*{21} & \mathbf{A}*{22} \end{pmatrix}, \quad \mathbf{x} = \begin{pmatrix} \mathbf{x}\_1 \ \mathbf{x}\_2 \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} \mathbf{b}\_1 \ \mathbf{b}\_2 \end{pmatrix}
$$

가우스 소거 과정에 준하여, 먼저 $\mathbf{A}\_{11}$이 역행렬(invertible)이 되도록 가정하고(이는 매우 중요한 전제조건이며, 블록 피벗(block pivot)을 교환하는 과정을 통해 확보하기도 한다), 다음 단계를 수행한다.

$$
\begin{align}
&\mathbf{A}*{21} \leftarrow \mathbf{A}*{21}\mathbf{A}*{11}^{-1} \quad \text{및} \quad \mathbf{b}*2 \leftarrow \mathbf{b}*2 - \mathbf{A}*{21}\mathbf{A}*{11}^{-1}\mathbf{b}*1
\\
&\mathbf{A}*{22} \leftarrow \mathbf{A}*{22} - \mathbf{A}*{21}\mathbf{A}*{12}
\end{align}
$$

이 과정을 통해 $\mathbf{A}$의 하부 블록을 갱신하면, 하부 영역이 어느 정도 소거되어(즉, $\mathbf{A}*{21}$이 단순화되며) 상부 블록은 그대로 유지된다. 이후 $\mathbf{A}*{22}$에 대해 또다시 유사한 소거 과정을 적용하여 해를 구할 수 있다. 최종적으로 각 단계에서 분리된 블록 내 해를 차례로 풀어가면, 전체 해를 얻을 수 있다.

여기서 핵심은 직접 전체 행렬에 대해 모든 연산을 수행하기보다는, 가능한 한 블록 단위(예: $\mathbf{A}*{11}$, $\mathbf{A}*{22}$)에만 집중해서 연산을 진행함으로써 메모리 사용량과 연산 복잡도를 보다 효율적으로 제어할 수 있다는 것이다. 특히 병렬 연산 환경에서 각 블록을 독립 프로세스/쓰레드에서 처리하거나, 특정 구조가 반복되는 블록을 재활용하게 되면 계산 효율이 배가된다.

#### 블록 행렬 해석의 유용성

블록 행렬 해법이 단순히 큰 행렬을 ‘나누고 다시 합치는’ 편의성에 그치지 않고, 다양한 분야에서 유의미하게 활용된다. 예컨대, 다물체 동역학(multi-body dynamics) 해석, 유한요소법(FEM)에서의 국소 해법, 전산유체역학(CFD)에서의 영역분할(domain decomposition) 기법 등이 모두 블록 단위 계산 전략과 밀접한 관련이 있다. 이들은 거대한 선형 시스템을 해결할 때, 특정 부분 문제를 반복적으로 해석하면서, 그 결과를 전체 해에 반영하는 과정을 효율화한다.

블록 행렬의 유용성은 다음과 같은 측면에서 더욱 드러난다. 상부 혹은 하부 블록이 서로 독립적인 구조(크기, 희소 패턴)를 띠는 경우, 각각에 대해 최적화된 해법을 적용할 수 있다. 예를 들어, $\mathbf{A}*{11}$이 대칭 양의 정부호(symmetric positive definite)인 블록이고, $\mathbf{A}*{22}$가 어떤 특별한 구조(예: 스칼라 곱셈으로 표현 가능)를 가지는 블록일 때, 서로 다른 알고리즘을 사용해 각 블록을 풀 수 있다. 이는 전체 문제를 일률적으로 처리할 때보다 훨씬 더 빠르게, 혹은 더 안정적으로 해를 찾을 수 있게 만든다.

#### 블록 LU 분해

블록 행렬에 대해 자주 사용되는 대표적 기법 중 하나가 블록 LU 분해(block LU factorization)이다. 이는 전체 행렬 $\mathbf{A}$를 하삼각 행렬 $\mathbf{L}$과 상삼각 행렬 $\mathbf{U}$의 곱으로 나타내는 전통적인 LU 분해를 확장하여, 각각의 삼각 행렬을 블록 형태로 다루는 방식이다.

예를 들어,

$$
\mathbf{A} = \begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} \ \mathbf{A}*{21} & \mathbf{A}*{22} \end{pmatrix}
$$

가 invertible하다고 하자. 그리고 $\mathbf{A}*{11}$ 또한 invertible하다고 가정한다. 여기서 $\mathbf{A}*{11}$이 비가역(즉, 역행렬이 존재하지 않음)이면, 가우스 소거 과정에서 부분 피벗(pivot)을 교환하거나, 더 일반적인 형태의 재배열(블록 피벗을 포함)을 고려해야 한다. 일단 $\mathbf{A}\_{11}$이 invertible하다는 가정 아래서, 다음과 같이 두 개의 블록 행렬 $\mathbf{L}$, $\mathbf{U}$를 구성할 수 있다.

$$
\mathbf{L} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \ \mathbf{L}*{21} & \mathbf{I} \end{pmatrix}, \quad \mathbf{U} = \begin{pmatrix} \mathbf{U}*{11} & \mathbf{U}\_{12} \ \mathbf{0}      & \mathbf{S} \end{pmatrix}
$$

이때,

$$
\begin{align}
\mathbf{U}*{11} &= \mathbf{A}*{11}\\
\mathbf{L}*{21} &= \mathbf{A}*{21}\mathbf{A}*{11}^{-1}\\
\mathbf{U}*{12} &= \mathbf{A}*{11}^{-1}\mathbf{A}*{12}\\
\mathbf{S} &= \mathbf{A}*{22} - \mathbf{A}*{21}\mathbf{A}*{11}^{-1}\mathbf{A}*{12}
\end{align}
$$

이 성립한다. 여기서 $\mathbf{I}$는 항등 블록 행렬(identity block matrix)을 의미한다(실제로는 적절한 차원으로 구성된 항등행렬).

계산 과정을 자세히 살펴보면,

$$
\begin{pmatrix} \mathbf{L}*{21} & \mathbf{I} \end{pmatrix} \begin{pmatrix} \mathbf{U}*{11} & \mathbf{U}*{12} \end{pmatrix} = \begin{pmatrix} \mathbf{L}*{21}\mathbf{U}*{11} & \mathbf{L}*{21}\mathbf{U}\_{12}  \end{pmatrix}
$$

인데, $\mathbf{L}*{21}\mathbf{U}*{11} = \mathbf{A}*{21}\mathbf{A}*{11}^{-1}\mathbf{A}*{11} = \mathbf{A}*{21}$, 그리고 $\mathbf{L}*{21}\mathbf{U}*{12} = \mathbf{A}*{21}\mathbf{A}*{11}^{-1}\mathbf{A}*{11}^{-1}\mathbf{A}*{12}$ 방식으로 연쇄 곱이 나타나게 된다. 전체적으로는,

$$
\begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} \ \mathbf{A}*{21} & \mathbf{A}*{22} \end{pmatrix} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \ \mathbf{L}*{21} & \mathbf{I} \end{pmatrix} \begin{pmatrix} \mathbf{U}*{11} & \mathbf{U}\_{12} \ \mathbf{0}      & \mathbf{S} \end{pmatrix}
$$

임을 보일 수 있다. 이렇게 분해된 $\mathbf{L}$, $\mathbf{U}$ 블록을 통해 선형 방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$의 해를 구할 때, 다음과 같은 방정식을 차례로 풀면 된다.

$$
\mathbf{L}\mathbf{y} = \mathbf{b},  \quad  \mathbf{U}\mathbf{x} = \mathbf{y}
$$

즉, 먼저 하삼각 블록 행렬 $\mathbf{L}$에 대한 방정식을 풀어서 $\mathbf{y}$를 구하고, 그 결과를 이용해 상삼각 블록 행렬 $\mathbf{U}$에 대한 방정식을 풀면 최종 해 $\mathbf{x}$를 얻는다.

#### 블록 피벗(block pivot)과 고려사항

물론 실제로는 “$\mathbf{A}\_{11}$이 역행렬이다”라는 가정이 항상 성립하지 않을 수 있다. 일반 LU 분해에서 피벗(pivot)을 교환하여 행렬의 특정 부분을 대각선으로 가져오는 것처럼, 블록 LU 분해에서도 적절한 크기의 블록을 피벗으로 삼아 교환하는 기법이 필요하다. 이를 블록 피벗(block pivot)이라 부른다.

블록 피벗은 보통 다음과 같은 상황에서 검토된다. 만일 어떤 단계에서 $\mathbf{A}\_{11}$ 블록이 비가역이거나 역행렬이 존재해도 수치적으로 매우 불안정한 상태라면, 다른 블록과 교환하여 보다 안정적인 형태를 확보하려 한다. 이 과정을 반복적으로 수행하면 전체 블록 행렬의 분해를 안전하게 진행할 수 있다. 이는 다소 복잡한 구현을 요구하나, 대규모 계산(특히 분산·병렬 환경)에서 필수적인 기법이다.

#### 블록 행렬식(determinant)과 역행렬

블록 LU 분해가 이루어지면, 행렬식과 역행렬 계산에도 장점을 얻을 수 있다. 예컨대,

$$
\det(\mathbf{A})  = \det\left( \begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} \ \mathbf{A}*{21} & \mathbf{A}*{22} \end{pmatrix}\right) = \det(\mathbf{A}\_{11}),\det(\mathbf{S})
$$

이 성립한다(단, $\mathbf{A}*{11}$과 슈어 보충행렬(Schur complement) $\mathbf{S} = \mathbf{A}*{22} - \mathbf{A}*{21}\mathbf{A}*{11}^{-1}\mathbf{A}\_{12}$이 모두 가역이라는 전제하에서 가능). 이를 이용하여 큰 차원의 행렬식 계산을 블록 단위로 나눠 수행할 수 있으므로 연산량이 감축된다.

또한 $\mathbf{A}$의 역행렬을 구하는 문제에서도,

$$
\mathbf{A}^{-1}  = \begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} \ \mathbf{A}*{21} & \mathbf{A}*{22} \end{pmatrix}^{-1} = \begin{pmatrix} \mathbf{U}*{11} & \mathbf{U}*{12} \ \mathbf{0}      & \mathbf{S} \end{pmatrix}^{-1} \begin{pmatrix} \mathbf{I} & \mathbf{0} \ -\mathbf{L}\_{21} & \mathbf{I} \end{pmatrix}
$$

등의 방식으로 분해를 재활용할 수 있다(여기서는 블록 LU 분해에 기초한 역행렬 공식 중 하나를 간략히 나타낸 것이며, 실제 전개는 조금 더 복잡할 수 있다). 핵심은 직접 큰 행렬에 대해 역행렬을 구하기보다, 각 블록에 대해 부분 분해 및 보충행렬을 활용함으로써 $\mathbf{A}^{-1}$을 단계적으로 구성한다는 점이다.

#### 대규모 계산에서의 확장성

블록 LU 분해를 비롯한 다양한 블록 행렬 해법은 큰 규모의 문제에서 병렬화를 고려하기에도 적합하다. 예컨대, 대규모 과학·공학 문제를 병렬 슈퍼컴퓨터 환경에서 풀 때, 행렬을 영역별로 나누거나(공간 분할), 변수 집합에 따라 나누어서(도메인 디컴포지션) 블록 형태로 처리하면, 각 프로세서가 독립적으로 서브블록을 담당하여 연산을 수행하고 필요할 때만 통신을 통해 연동할 수 있다.

이 과정에서 특정 서브블록이 정교한 해법(예: 다중 격자(multigrid) 알고리즘)을 사용해야 한다면, 그 블록을 처리하는 프로세서에서는 자체적으로 해당 알고리즘을 적용하고, 그 결과를 전체 해 벡터에 반영하는 식으로 계산을 진행하게 된다. 이는 전역적인 단일 알고리즘(예: 통상적인 전체 도메인에 대한 가우스 소거)이 너무 비효율적일 수 있는 경우에, 지역 특성을 적극적으로 활용할 수 있는 큰 장점이 있다.

#### 블록 행렬을 이용한 다중 단계 접근

선형 시스템 해법에서 “블록”을 어떻게 분할하느냐에 따라 접근 방식이 크게 달라진다. 예컨대, 시간 종속 편미분 방정식을 풀 때, 시간 차분(Time stepping)마다 어차피 일정 구조를 갖는 행렬을 구축해야 한다면, 해당 구조를 관찰하여 어떤 부분은 반복 알고리즘(예: Krylov 하위공간 기법)으로, 다른 부분은 직접(Direct) 계산으로 처리할 수 있다. 이것이 바로 블록 하이브리드(hybrid) 해법의 전형적인 예다.

블록 해법 관점에서 보면, 반복적 선형 해법을 특정 블록에만 적용하거나, 혹은 “선형 예측 → 비선형 보정” 단계를 번갈아 가며 수행할 때도 각 단계마다 부분 블록에 초점을 두고 계산을 재활용할 수 있다. 이런 식으로 블록 구조가 문제의 물리적 의미나 수학적 성질을 그대로 반영하도록 설정하면, 별도의 복잡한 스케줄링이나 추가 계산 없이도 큰 문제를 자연스럽게 여러 부분 문제로 나눠 해결할 수 있다.

#### 분산 및 병렬 환경에서의 블록 행렬 구현

현대 수치해석에서는 매우 큰 규모의 행렬 연산을 처리해야 하는 경우가 빈번하다. 특히 산업·과학 분야에서 등장하는 초대형 시스템(수백만, 수천만 개 이상의 자유도)이 대표적이다. 이런 문제를 단일 프로세서로 해결하기는 사실상 불가능하므로, 다수의 프로세서와 대용량 메모리가 결합된 병렬·분산 환경에서 효율적으로 계산을 수행해야 한다. 블록 행렬 구조는 이러한 병렬 처리에 적합한 자료 구조와 연산 패턴을 제공한다.

예컨대, 전체 계산 영역(domain)을 여러 부분으로 나누어(물리적 공간 또는 변수 집합에 따라) 각 부분을 하나의 블록으로 대응시키면, 각 프로세서(또는 노드)가 해당 블록을 담당하여 독립적인 계산을 수행하고, 경계 또는 인터페이스에 해당하는 블록 간의 상호작용만 통신을 통해 교환한다. 이렇게 하면 전역(system-wide) 통신량을 최소화하면서도 국소(블록 내부) 계산을 병렬화할 수 있다.

고성능 컴퓨팅(HPC) 환경에서 도메인 분할을 수행할 때는, 각 하위 영역의 자유도(행 인덱스·열 인덱스)를 물리적으로 연속되게 묶어(가령 페트라(PETSc) 같은 병렬 라이브러리에서 사용하는 CSR/CSC 구조 기반) 하나의 블록으로 만든다. 그렇게 얻어진 블록 구조를 인접 프로세서 사이에 분산시키고, 블록 내부에서의 LU 분해나 (부분) 가우스 소거를 로컬 연산으로 처리하는 식이다. 이때, 경계 블록이나 인터페이스 블록에 대한 정보만 적절히 교환하면 전역 해를 단계적으로 업데이트할 수 있다.

#### GPU 가속과 블록 구조

최근에는 GPU(Graphics Processing Unit) 기반 가속이 병렬 연산을 크게 빠르게 해주는데, 블록 행렬 접근 방식은 GPU 활용에도 유리하다. GPU가 대규모 병렬 연산에 강점을 가지므로, 각 블록 내에서 일괄적으로 행렬 벡터 곱이나 삼각 분해 등을 수행할 때 GPU 커널(kernels)을 효율적으로 적용할 수 있다. 예를 들어, 반복 해법에서 각 이터레이션마다 등장하는 블록 연산(대각 블록의 역행렬 곱, 블록 상호 곱셈 등)을 GPU에서 병렬 처리하면, CPU 대비 획기적인 성능 향상을 기대할 수 있다.

이처럼 블록 행렬을 GPU에 매핑할 때, 고려해야 할 사항은 다음과 같다. 우선, 블록 내의 희소(sparse) 구조를 어떻게 관리할 것인가 하는 점이다. GPU에서 효율적인 희소 행렬-벡터 곱을 구현하기 위해서는 CSR, ELLPACK, COO 등 다양한 희소 포맷이 있는데, 블록 단위를 독립적으로 처리한다면 각 블록에 맞는 최적 포맷을 달리 적용할 수 있다. 또한, 블록 간 데이터 전송(메모리 복사)이 과도하게 발생하지 않도록, 전체 알고리즘 흐름을 GPU 중심으로 설계하거나(커널 간 연쇄 호출), CPU-GPU 사이의 통신을 최소화하는 전략을 세우는 것이 중요하다.

#### 블록 구조 시각화 예시

아래는 블록 가우스 소거 과정을 도식화한 예시이다. 메모리 상에서 분할된 행렬을 단계적으로 소거하며, 상삼각·하삼각 블록이 정리되는 과정이 흐름도로 나타나 있다.

{% @mermaid/diagram content="flowchart TB
A((분할 전 행렬 A)) --> B\["블록 분할<br>(예: 2×2 형태)"]
B --> C\["블록 피벗 선택<br>(또는 A\_11 역가능성 확인)"]
C --> D\["블록 가우스 소거<br>(하부 블록 갱신)"]
D --> E("상삼각 블록<br>LU 분해 완성")
E --> F\["블록 U 해석<br>(앞부분 해 y)"]
F --> G\["블록 L 해석<br>(최종 해 x)"]" %}

이렇게 단계별로 블록을 분할하고 소거하며, 최종적으로 해 벡터를 얻게 된다. 실제 코드 구현 시에는 블록별 연산을 독립 모듈로 설계할 수 있어, 병렬화나 GPU 가속 등의 확장 적용이 한층 간편해진다.

#### 더욱 복잡한 블록 구조

실제 문제에서는 2×2 블록 구조가 아니라, 다중 블록(multi-block) 구조가 필요한 경우가 많다. 예를 들어, 다음과 같은 4×4 블록 구조를 고려할 수 있다.

$$
\mathbf{A} = \begin{pmatrix} \mathbf{A}*{11} & \mathbf{A}*{12} & \mathbf{A}*{13} & \mathbf{A}*{14} \ \mathbf{A}*{21} & \mathbf{A}*{22} & \mathbf{A}*{23} & \mathbf{A}*{24} \ \mathbf{A}*{31} & \mathbf{A}*{32} & \mathbf{A}*{33} & \mathbf{A}*{34} \ \mathbf{A}*{41} & \mathbf{A}*{42} & \mathbf{A}*{43} & \mathbf{A}*{44} \ \end{pmatrix}.
$$

이때 각 블록은 독립적인 물리 영역이거나, 다른 종류의 변수(또는 조건)를 나타내는 ‘하위 문제’를 가리킬 수 있다. 블록 가우스 소거를 확장 적용하면, 선택된 피벗 블록(예: $\mathbf{A}*{11}$)에 대해 소거를 수행하고, 그 결과를 아래·오른쪽 블록에 반영해 나간다. 이후 $\mathbf{A}*{22}$, $\mathbf{A}*{33}$, $\mathbf{A}*{44}$ 순으로 반복하면서 전체 행렬을 삼각화할 수 있다.

이 과정을 체계적으로 구현하면, 많은 연산이 병렬로 수행 가능해진다. 예컨대, 한 피벗 블록에 대한 소거 연산 동안, 독립된 다른 블록은 별도의 계산(전처리, 사전 준비 등)을 진행할 수 있다. 물론, 이때 블록 간 데이터 의존성을 정밀하게 파악해야 하므로, 그래프 이론 기반의 태스크 스케줄링 기법(DAG scheduling)을 적용하기도 한다.

#### 동적 블록 분할과 적응형 기법

문제 상황에 따라 고정된 블록 구조가 아니라, 동적으로 블록을 재분할(adaptive partitioning)해야 하는 경우도 있다. 예를 들어, 유한요소 해석 과정에서 메쉬를 국부적으로 재세분할할 때, 행렬 구조 역시 바뀐다. 그러면 새로 형성된 메쉬 구역에 대응하여 블록을 다시 설정해야 하며, 이전 단계에서 계산된 요긴한 정보(분해 결과나 전처리 구조 등)를 가능하면 최대한 재활용한다.

이와 관련하여, 적응형(Adaptive) 블록 기법은 반복 해법과 궁합이 좋다. 한 번의 이터레이션에서 블록을 분할해놓고, 수렴 과정 중 특정 블록의 크기가 너무 커지거나(또는 수치적 문제가 발생) 조건수가 나빠지면 블록을 세분화하거나, 반대로 서로 유사한 성질을 갖는 블록끼리는 병합하여 연산 비용을 줄이는 식이다. 이는 동적 하중 균형(dynamic load balancing)을 필요로 하는 병렬 환경에서 특히 의미가 크다.

#### 복합 물리(coupled physics) 문제에서의 활용

한 문제 내에 여러 물리 현상이 동시에 고려되는 복합 물리(coupled physics) 상황에서도 블록 행렬 해법이 자연스럽게 적용된다. 예를 들어, 열-구조 연성(thermal-structural coupling)을 다룬다고 하자. 열전달 방정식에 대응하는 블록과 구조 해석 방정식에 대응하는 블록이 각각 존재하며, 이 둘 사이에는 열팽창·열탄성 등으로 인해 상호 연동 항(coupling term)이 발생한다.

이를 단일 거대 행렬로 통합하면,

$$
\begin{pmatrix} \mathbf{A}*{TT} & \mathbf{A}*{TS} \ \mathbf{A}*{ST} & \mathbf{A}*{SS} \end{pmatrix} \begin{pmatrix} \mathbf{x}\_T \ \mathbf{x}\_S \end{pmatrix} = \begin{pmatrix} \mathbf{b}\_T \ \mathbf{b}\_S \end{pmatrix},
$$

와 같은 형태가 되어, 여기서 $\mathbf{x}*T$는 온도 분포에 관련된 해(변수), $\mathbf{x}S$는 구조 해석 변수(변형, 응력 등)에 해당한다. 블록 행렬 접근법을 사용하면, $\mathbf{A}{TT}, \mathbf{A}*{SS}$가 각각 물리적으로 독립된 방정식을 풀어주는 부분 블록으로 분할되어, 각 분야(열 해석, 구조 해석)에 특화된 알고리즘(예: 열 방정식에는 빠른 열전달 솔버, 구조 해석에는 대칭 양의 정부호 해석 알고리즘)을 그대로 적용할 수 있다. 그리고 상호 연동 항인 $\mathbf{A}*{TS}, \mathbf{A}*{ST}$는 블록 연산으로 처리되므로, 전체 계산 과정이 훨씬 구조화된다.

#### 예제 구현 (Python)

블록 행렬 해법을 직접 시연해보기 위해 간단한 Python 예제를 살펴보자. 여기서는 2×2 블록으로 분할된 선형 시스템을 블록 가우스 소거법을 통해 푸는 과정을 구현해본다. 실제 문제에서는 훨씬 큰 블록과 복잡한 구조가 등장하지만, 여기서는 기본 아이디어를 확인하기에 충분하다.

```python
import numpy as np

def block_gaussian_elimination(A11, A12, A21, A22, b1, b2):
    """
    2×2 블록 행렬
      [A11  A12]
      [A21  A22]
    와 우변 벡터
      [b1]
      [b2]
    에 대해 블록 가우스 소거법을 수행하여 해 x = [x1, x2]^T를 구한다.
    A11, A12, A21, A22는 각각 (n x n) 크기라 가정.
    b1, b2 역시 (n x 1) 크기라 가정.
    """
    # 1. A11이 가역(invertible)이라 가정.
    #    만약 그렇지 않다면 블록 피벗 등 교환 과정 필요.
    A11_inv = np.linalg.inv(A11)

    # 2. Schur complement: S = A22 - A21 * A11_inv * A12
    S = A22 - A21 @ A11_inv @ A12

    # 3. 중간 우변 벡터 갱신
    b2_tilde = b2 - A21 @ A11_inv @ b1

    # 4. S가 가역이라면, x2 = S^-1 b2_tilde
    S_inv = np.linalg.inv(S)
    x2 = S_inv @ b2_tilde

    # 5. x1 = A11_inv(b1 - A12 x2)
    x1 = A11_inv @ (b1 - A12 @ x2)

    return x1, x2

# 간단한 예시
n = 3
# 무작위로 3×3 블록 행렬 생성
np.random.seed(0)
A11 = np.random.randn(n, n)
A12 = np.random.randn(n, n)
A21 = np.random.randn(n, n)
A22 = np.random.randn(n, n)

# 해 x를 임의로 설정한 뒤, A x = b를 구성
true_x1 = np.random.randn(n, 1)
true_x2 = np.random.randn(n, 1)

A = np.block([[A11, A12],
              [A21, A22]])
x_true = np.vstack([true_x1, true_x2])
b = A @ x_true

# b를 블록으로 나눔
b1 = b[:n, :]
b2 = b[n:, :]

# 블록 가우스 소거법으로 해 구하기
x1_sol, x2_sol = block_gaussian_elimination(A11, A12, A21, A22, b1, b2)

# 결과 비교
print("블록 가우스 소거법으로 구한 해:")
print("x1_sol =\n", x1_sol)
print("x2_sol =\n", x2_sol)
print()
print("실제 해:")
print("x1_true =\n", true_x1)
print("x2_true =\n", true_x2)
print()
print("오차(norm):", np.linalg.norm(np.vstack([x1_sol, x2_sol]) - x_true))
```

이 코드는 간단히 무작위로 생성한 2×2 블록 행렬에 대해, 실제로 어떤 해 $\[x\_1, x\_2]^T$를 가정하고 시스템을 구성한 뒤, 블록 가우스 소거법을 이용해 구한 해와 비교한다. 실행 결과, 충분히 조건수가 나쁘지 않은 무작위 행렬이라면(그리고 $\mathbf{A}\_{11}, \mathbf{S}$가 역행렬이 존재한다면), 구해진 해는 실제 해와 매우 유사하거나 동일하게 나온다.

실제로는, $\mathbf{A}\_{11}$ 또는 슈어 보충행렬 $\mathbf{S}$가 비가역이거나(또는 수치적으로 불안정한) 경우를 대비해, 블록 피벗 교환이나 정교한 전처리 과정을 추가로 고려해야 한다.

#### 일반적 적용 시 유의점

블록 행렬 해법을 실제 응용 문제에 적용할 때, 유념해야 할 요소들은 다음과 같다. 가령, 2×2 블록으로 단순히 나눈 뒤에 “$\mathbf{A}\_{11}, \mathbf{S}$가 모두 역행렬”이라는 전제가 불필요하게 엄격할 수 있다. 실제로는 더 복잡한 블록 분할을 통해, 각 하위 블록의 구조적 특성에 맞게(대칭, 희소, 밴드 구조 등) 전문 알고리즘을 적용하거나, 역행렬 대신 근사 해법(반복적 방법, 다중 격자, 전처리 등)을 사용할 수 있다.

블록 가우스 소거법과 블록 LU 분해는 매우 유사한 맥락에서 작동하지만, 구현 세부 사항에서 차이가 있을 수 있으며, 피벗 선택 및 수치 안정성 측면에서는 일반 LU 분해에서의 전략(부분 피벗, 전체 피벗 등)을 확장 적용해야 한다.

#### 복잡한 시스템에 대한 접근

현실적인 대규모 문제에서는 다음과 같은 요소들이 종합적으로 고려된다. 복수의 블록(예: 4×4, 8×8, 혹은 불규칙한 분할)과 하부 구조(각 블록이 다시 다중 블록으로 이루어진 계층적 구조), 그리고 혼합된 해법(일부 블록은 직접 분해, 일부 블록은 반복 해법, 또 다른 일부는 근사 기법) 등이 조합되어 최적의 성능을 모색한다. 그 과정에서 필연적으로 병렬·분산 컴퓨팅 환경을 동원하게 되며, GPU 가속까지 활용하면 더욱 높은 처리 성능을 기대할 수 있다.

블록 행렬 해법은 이러한 “복잡다단한” 상황을 시스템적으로 접근할 수 있는 틀을 제공한다. 단순 가우스 소거를 전역으로 적용하기에는 너무나 큰 문제도, 여러 블록으로 나누어 각각의 특화 알고리즘을 조합하여 풀어낼 수 있다. 다만, 블록 경계부나 상호작용부에서의 수치적 복잡도가 증가할 가능성이 있고, 블록 간 통신(정보 교환) 스키마가 계산 속도를 크게 좌우하므로, 이에 대한 설계가 중요하다.

#### 범용(General) 블록 행렬의 형태

블록 행렬이라고 하면, 보통은 대각이나 삼각 구조가 뚜렷한 $2\times 2$ 혹은 $m\times m$ 분할을 먼저 떠올리게 되지만, 실제 산업·과학 응용 문제에서는 그보다 훨씬 복잡하게 얽힌 형태를 마주하게 된다. 예를 들어, 공학 시뮬레이션에서 동역학 시스템, 열·유체·구조 연성 문제 등을 다룰 때, 다음과 같이 서로 다른 크기의 블록들이 불규칙하게 배치된 스파스(sparse) 행렬을 얻게 될 수 있다.

$$
\mathbf{A} =  \begin{pmatrix} \mathbf{B}*{11} & \mathbf{B}*{12} & \cdots & \mathbf{B}*{1m} \ \mathbf{B}*{21} & \mathbf{B}*{22} & \cdots & \mathbf{B}*{2m} \ \vdots          & \vdots          & \ddots & \vdots          \ \mathbf{B}*{m1} & \mathbf{B}*{m2} & \cdots & \mathbf{B}\_{mm} \ \end{pmatrix},
$$

여기서 각 블록 $\mathbf{B}\_{ij}$는 저마다 행·열 차원이 다를 수 있다. 또한 많은 블록이 실제로 0(또는 매우 희박한) 구조를 가질 수 있다. 이렇게 복합적인 블록 구조를 효율적으로 관리하려면, 아래와 같은 접근이 가능하다.

먼저, 문제의 물리나 수학적 배경을 통해 “어떤 블록끼리 강하게 연결되어 있고, 어떤 블록끼리는 비교적 독립적인가?”를 판단한다. 그런 뒤, 블록 간 통신(혹은 연산 상호 의존성)이 많은 블록들을 인접해 두거나, 혹은 묶어서 병렬화에 유리한 배치를 만든다. 이 과정은 행렬의 행·열 순서를 재배열(reordering)하는 것과 동일하게 볼 수 있다. 즉, 그래프 이론 기반의 재배열 기법(예: 최소 대역폭, 최소 필인(fill-in) 정렬)을 블록 단위로 적용하는 것이다.

이렇게 재배열된 블록 행렬 구조를 갖추면, 이후에 적용되는 블록 가우스 소거나 블록 LU 분해, 혹은 블록 전처리 기법 등에서 연산 효율이 크게 올라간다. 실제로 대규모 선형 시스템을 다루는 유명 라이브러리들(예: PETSc, Trilinos, MUMPS 등)에서는 이러한 재배열과 블록 분해 전략이 내부적으로 복합적으로 적용되어 있다.

#### 비대칭/비정방 블록 행렬

일부 응용에서는 직사각형 형태의 계수 행렬, 즉 $m\times n$ 크기를 갖는 비정방 행렬이 등장한다. 물론 선형 방정식의 표준형 $\mathbf{A}\mathbf{x}=\mathbf{b}$를 생각하면 일반적으로 $\mathbf{A}$는 정방이어야 한다. 하지만 제약이 있는 최적화 문제나, 적분방정식을 선형 연산자 형태로 처리할 때, 혹은 상태방정식-출력방정식을 결합한 경우 등에서는 비정방 행렬이 흔히 나타난다.

이 경우에도 블록 행렬 접근을 도입할 수 있다. 예컨대, 행렬이

$$
\mathbf{A} = \begin{pmatrix} \mathbf{C}*{11} & \mathbf{C}*{12} \ \mathbf{C}*{21} & \mathbf{C}*{22} \end{pmatrix}
$$

와 같은 형태를 띠지만, $\mathbf{C}*{11}, \mathbf{C}*{22}$ 등 각각의 블록 크기가 달라서 전체로는 $m\times n$ 행렬이 되는 식이다. 이때는 “해 $\mathbf{x}$”와 “우변 벡터 $\mathbf{b}$” 역시 각각 다른 차원을 갖는 블록 벡터로 대응해야 한다. 이를 통해, 행렬-벡터 연산을 블록 단위로 수행하고, 필요하다면 최소제곱 문제나 제약조건 문제로 변환해 풀 수도 있다. 즉, 블록 구조가 해석 차원에서는 유사한 장점을 제공하되, 정방 행렬이 아닐 때 생기는 추가적인 고려(역행렬의 존재 여부, 해의 존재성 등)는 별도로 점검해야 한다.

#### 부정정(Indefinite) 블록 행렬

물리적 혹은 수학적으로 더 복잡한 상황 중 하나는 부정정 행렬(indefinite matrix) 구조다. 예컨대, 구속(Constraint)이나 라그랑주 승수(Lagrange multiplier)를 통해 형성된 구속 방정식 시스템은 다음과 같은 블록 행렬 형태를 보인다.

$$
\begin{pmatrix} \mathbf{W} & \mathbf{G}^T \ \mathbf{G} & \mathbf{0} \end{pmatrix} \begin{pmatrix} \mathbf{x} \ \boldsymbol{\lambda} \end{pmatrix} = \begin{pmatrix} \mathbf{f} \ \mathbf{h} \end{pmatrix}.
$$

여기서 $\mathbf{W}$는 어떤 대규모 내부 계수 행렬(예: 구조 해석에서의 질량이나 강성 행렬)에 해당하고, $\mathbf{G}$는 구속 조건(예: 접촉 조건, 유체의 불압축성 조건 등)에 대응하는 행렬, $\boldsymbol{\lambda}$는 라그랑주 승수에 해당한다. 이 시스템은 전형적으로 부정정 행렬 형태를 띠며, 직접 분해를 적용할 때 피벗 교환이나 추가적인 구조 활용(예: $\mathbf{W}$가 대칭 양의 정부호라면 특별한 분해법) 없이는 수치적으로 불안정하거나 계산량이 폭증할 우려가 있다.

블록 해법 관점에서는, 이 부정정 구조를 슈어 보충행렬을 사용해 다음과 같이 부분적으로 해결할 수 있다. 만약 $\mathbf{W}$가 역행렬을 갖는다면, 승수(라그랑주 승수) 블록만을 위한 슈어 보충행렬을 만들고, 이를 반복적 혹은 분할 정복 접근으로 풀어나간다. 이렇게 하면, 전체 시스템을 한꺼번에 다루는 대신, “주 블록($\mathbf{W}$)”과 “구속 블록($\mathbf{G}$)”을 분리하여 각각 적절한 해법(직접 분해, 전처리된 Krylov, 등등)을 쓸 수 있으므로 효율이 높아진다.

#### 크릴로프(Krylov) 하위공간과 블록 접근

Krylov 하위공간 기반의 반복법(CG, GMRES, BiCG 등)은 대규모 선형 시스템을 푸는 데 표준처럼 자리 잡았다. 이를 블록 구조와 결합하면, “블록 Krylov” 기법을 설계할 수도 있다. 예컨대, 다중 우변(multiright-hand-sides) 문제에서 $\mathbf{A}\mathbf{X} = \mathbf{B}$ 형태를 풀어야 할 때, $\mathbf{B}$가 여러 개의 열 벡터로 구성된 블록 벡터라면, 단일 Krylov 방법을 각각의 열 벡터에 대해 반복하는 대신, 블록 Krylov 방법을 통해 여러 열 벡터를 동시에 갱신할 수 있다.

블록 Krylov 접근은 캐시 활용이나 연산 중첩 측면에서 유리할 뿐 아니라, 서로 다른 우변 벡터들 사이의 선형 결합(상호 의존성)도 활용할 수 있다. 이와 유사하게, 혼합 변수 시스템에서 속도·압력 블록을 동시에 갱신하는 블록 Krylov 변형도 연구되고 있으며, 전처리 행렬 역시 블록 구조를 활용해 구성된다. 이 경우 “한 번의 매트릭스-벡터 곱 연산으로 여러 벡터에 대한 결과를 얻는다”는 이점이 뚜렷해진다.

#### 희소 패턴(sparsity pattern)과 블록 희소성

대부분의 대규모 공학 문제에서 행렬은 희소(sparse) 구조를 띠고, 이 희소성이 블록 단위로도 나타나는 경우가 많다. 예를 들어, 도메인이 물리적으로 분할되어 있으면, 서로 멀리 떨어진 영역에 대응하는 자유도들은 거의 연결되지 않아, 그에 해당하는 블록은 영행렬 혹은 매우 작은 요소만을 갖게 된다. 이럴 때, “블록 희소성(block sparsity)”을 인지하고, 실제 메모리 상에서 해당 블록을 완전히 생략하거나(저장하지 않음) 효율적인 희소 표현으로 관리하면, 메모리 사용량을 크게 줄일 수 있다.

특히, 행렬-벡터 곱이나 전처리 연산을 수행할 때, 실제 연산이 필요한 블록만 접근하면 되므로 계산량 역시 줄어든다. 이처럼 블록 희소 구조를 적절히 활용하기 위해서는, (1) 문제에 대한 도메인 지식(어떤 부분이 서로 독립적인가), (2) 재배열(reordering) 기법, (3) 라이브러리에서 제공하는 희소 포맷(압축 행 리스트, CSR, CSC, BSR(Block Sparse Row) 등)을 종합적으로 검토해야 한다.

#### 분할정복(Divide-and-Conquer)과 계층적 블록

블록 해법은 분할정복 기법과 결합되기도 한다. 예를 들어, 다단계(multilevel) 접근에서는 가장 큰 스케일에서 도메인을 대략적인 큰 블록으로 분할하고, 각 블록 내부에서도 다시 세분화하여 하위 블록을 구성하는 식으로 계층적 구조를 만든다. 이는 다중 격자(Multigrid) 방법이나 다단계 도메인 분할, 혹은 하이퍼 매트릭스(Hierarchical matrix) 기법 등에서 비슷한 개념이 활용된다.

이렇게 계층적으로 나눠진 블록에 대해, 상위 블록에서 거친(gross) 수준의 해를 구하고, 하위 블록으로 내려가면서 정밀한 로컬 구조를 반영해 보정(correction)하는 과정이 반복된다. 각각의 수준에서 특정 블록만을 대상으로 소규모 LU나 직교화(Orthonormalization) 연산 등을 수행할 수 있어, 전체 연산 비용은 로그 규모 혹은 선형 규모로 줄어들 수 있다. 이는 전형적인 “분할정복” 사상의 구현이며, 결과적으로는 블록 행렬 해법과 반복적 다단계 기법이 서로 보완적으로 작용해 대규모 문제를 빠르게 해결하게 해준다.

#### 소프트웨어 생태계와 블록 행렬

실무에서 블록 행렬 기법을 적극적으로 활용하려면, 수치연산 라이브러리나 솔버 패키지가 이를 지원해야 한다. 이미 많은 HPC 라이브러리가 “서브매트릭스(submatrix)” 추출이나 “블록 분산(block distribution)” 기능을 제공한다. 예를 들어,

로 PETSc의 DM(Domain Management) 모듈과 IS(Index Set)을 통해 도메인 분할 후 각 서브도메인에 대응하는 부분 행렬 블록을 추출하거나, 로 Trilinos의 Tpetra나 Ifpack2 모듈에서 블록 전처리자를 구성하거나, 로 MKL, MAGMA 등에서 제공하는 Batched BLAS(배치 연산)나 Block Sparse BLAS를 활용해 GPU 병렬 처리를 수행하는

과 같은 식으로, 블록 구조에 맞춘 연산을 간결히 구현할 수 있다. 이러한 지원이 없던 시절에는 사용자가 직접 행렬-벡터 곱이나 LU 분해를 블록 단위로 짜야 했으나, 최근에는 라이브러리에 내장된 기능이 상당히 발전해, 고성능 계산을 손쉽게 시도할 수 있게 되었다.

\---: 블록 접근의 본질

결국 블록 행렬 해법은 “복잡한 문제를 덩어리(블록)로 나누어 처리”한다는 간명한 철학에 기초한다. 물리적으로 혹은 문제적으로 서로 밀접한 자유도들을 묶어 하나의 블록으로 보고, 그 블록들 사이의 상호작용을 별도의 블록으로 구분함으로써, 문제 전체를 좀 더 구조적으로 이해하고 계산할 수 있다. 이는 다음과 같은 장점을 제공한다.

한편, 블록 접근이 무조건 이득을 보장하는 것은 아니고, 분할 전략이 문제와 맞지 않으면 오히려 성능이 악화되거나 구현이 복잡해질 수도 있다. 따라서 문제 특성, 목표 컴퓨팅 환경, 사용 가능한 라이브러리/알고리즘 등을 종합적으로 고려하여, 최적의 블록 구조와 해법을 결정하는 것이 핵심이다.