부분 피벗·완전 피벗에 대한 이해
선형 방정식 $\mathbf{A}\mathbf{x} = \mathbf{b}$을 풀이하는 대표적인 방법인 가우스 소거법(Gaussian elimination) 과정에서, 피벗(pivot)이라는 개념은 매우 중요한 역할을 한다. 일반적으로 어떤 열(column) 또는 행(row)의 원소를 기준으로 하여 행렬을 단계적으로 삼각화(triangularization)하면서 해를 구하게 되는데, 이때 피벗 원소가 0에 가까워서 연산 과정에서 큰 반올림 오차(round-off error)가 발생하거나, 실제로 0이라서 소거가 불가능해지는 문제가 발생하기도 한다. 이를 보완하기 위해 **부분 피벗(partial pivoting)**이나 완전 피벗(complete pivoting) 기법을 도입한다.
아래에서는 부분 피벗과 완전 피벗의 수학적·알고리즘적 배경을 자세히 살펴본다. 특히 수치 안정성(numerical stability)을 확보하기 위해 어떤 식으로 피벗을 선택하는지가 핵심이다.
부분 피벗의 기본 개념
가우스 소거법을 진행할 때, 각 단계에서 현재 열에서 절댓값이 가장 큰 행을 선택하여 그 행과 현재 피벗 행을 교환(swap)하는 것을 부분 피벗이라고 한다. 예를 들어 $k$번째 단계에서 $k$번째 열의 피벗을 선택할 때, $k$번째 열의 $k$행부터 $n$행까지 중에서 절댓값이 가장 큰 원소가 있는 행을 찾아서 $k$행과 맞바꾸면 된다. 이렇게 하면 피벗 원소의 절댓값이 상대적으로 작아서 발생하는 오차를 줄이는 효과가 있다.
예시로 다음과 같은 $3 \times 3$ 행렬 $\mathbf{A}$가 있다고 하자:
처음 소거 단계에서 1행의 피벗 원소는 $|\alpha|$가 될 것이나, 부분 피벗을 적용하려면 다음 두 원소 $|p|$, $|s|$와도 비교해서 가장 큰 값을 피벗으로 삼게끔 행을 맞바꿔야 한다. 즉
중 최대값이 있는 행을 찾아 1행과 교환하는 방식이다. 이를 통해 계산 과정에서 발생할 수 있는 불필요한 분수(또는 0에 가까운 수) 연산을 줄이는 효과가 있다.
부분 피벗의 알고리즘
가우스 소거법에서 $k$번째 단계에 대하여, 부분 피벗을 적용하는 절차는 다음과 같은 식으로 진행된다. (알고리즘 서술 시 편의를 위해 열거 형태가 아닌 서술형으로 정리하며, 여기서는 $n$차 정방행렬을 가정한다.)
먼저 $k$번째 열에서 $k$행 이하에 해당하는 행(즉 $k$행부터 $n$행)들 중에서, 그 열의 해당 원소의 절댓값이 최대가 되는 행을 찾는다. 이를 $r_k$라고 하자. 만약 $r_k \ne k$이면, $k$행과 $r_k$행을 교환한다. 그리고 나서 기존의 가우스 소거법을 적용하여 $k$번째 열의 피벗 원소를 중심으로 하위 행의 원소들을 0으로 만들어 나간다.
이 과정을 수식으로 표현해 보면, $k$번째 단계에서 피벗을
으로 삼아야 한다. $a_{ik}$가 그 열의 $i$행 원소를 의미한다면, $|a_{ik}|$가 최대가 되는 $i$값을 $r_k$라 할 때, 만약 $r_k \ne k$이면
를 수행한 후, 가우스 소거의 업데이트를 진행한다.
부분 피벗의 장단점
부분 피벗은 수치 안정성을 크게 개선한다. 가우스 소거법을 피벗 없이 수행하면, 만약 피벗이 되는 원소가 매우 작거나 0에 가까운 값일 경우 연산 과정 중에 무한히 큰 값이 발생하거나(오버플로우, underflow), 반올림 오차가 누적될 가능성이 크다. 부분 피벗만 적용해도 이러한 문제를 상당 부분 완화할 수 있다.
그러나 부분 피벗은 각 단계에서 행만 교환하며 열을 교환하지 않으므로, 어떤 경우에는 충분하지 않을 수 있다. 예를 들어 실제로 피벗이 되는 원소가 매우 작지만, 같은 열 내에서 큰 원소가 없을 경우에는 다른 열의 원소들이 더 클지라도 선택되지 않는다. 따라서 수치적 안정성을 더욱 높이려면 완전 피벗을 사용해야 한다.
완전 피벗의 개념
완전 피벗에서는 각 단계에서 피벗 후보가 되는 부분 행렬(submatrix) 안에서 절댓값이 가장 큰 원소를 찾는다. 즉 행 뿐 아니라 열도 맞바꿀 수 있게끔 자유도가 더 생긴다. $k$단계에서 $k$행과 $k$열 아래에 있는 모든 원소를 살펴본 뒤 최대값을 갖는 자리(이를 $r_k$행, $c_k$열이라 하자)를 찾아, 먼저 $k$행과 $r_k$행을 교환하고, 이어 $k$열과 $c_k$열을 교환한다. 이러한 방식으로 가장 안정적인(절댓값이 큰) 피벗을 선택하게 된다.
완전 피벗은 부분 피벗보다 한층 더 수치 안정성을 개선하지만, 각 단계마다 열 교환 과정을 추가로 수행해야 하므로 연산 비용이 증가하고, 프로그램 구현도 복잡해진다. 그럼에도 불구하고 매우 크거나 매우 작은 피벗 원소가 나타날 가능성을 최소화해 준다는 장점이 있다.
아래의 수식을 통해 완전 피벗에서 피벗 선택 과정을 살펴보자. $k$번째 단계에서
와 같이, $k$행 및 $k$열 이하의 부분 행렬에서 가장 큰 값(절댓값 기준)을 찾는다. 그 위치를 $(r_k,, c_k)$로 두고, $r_k \ne k$이면 행을 맞바꾸고, $c_k \ne k$이면 열을 맞바꾸는 것이다.
완전 피벗의 필요성
실제로 많은 응용 분야에서 부분 피벗만으로도 충분한 경우가 많지만, 행렬이 특이(singular)에 가깝거나, 특이 행렬에 가까운 희소(sparse) 구조를 가질 때, 부분 피벗만으로는 각 단계에서 선택되는 피벗이 매우 작아지는 것을 막을 수 없게 된다. 이때 완전 피벗을 도입하면 어떠한 행이나 열에 큰 값이 존재할 때 그것을 피벗으로 삼아 연산을 안정화할 수 있다.
간단한 코드 예시 (Python)
아래는 부분 피벗을 사용하여 가우스 소거를 구현한 간단한 Python 예시이다. 실제로는 오류 처리나 행렬 검증 등 추가 요소가 필요하지만, 개념 이해 차원에서 간략히 살펴볼 수 있다.
이 코드는 간단히 다음 순서를 따른다. 먼저 $k$단계에서 $k$번째 열부터 밑으로 내려가며, 절댓값이 가장 큰 피벗 후보를 찾는다. 해당 행을 $k$행과 교환한 뒤, 가우스 소거법을 진행한다. 마지막으로 뒤로 대입(back-substitution)을 수행하여 해를 구한다.
간단한 예제 행렬에서의 부분 피벗 및 완전 피벗 시연
구체적인 행렬 예시를 통해 부분 피벗과 완전 피벗이 실제로 어떻게 이루어지는지 살펴보자. $3\times 3$ 행렬로 간단히 가정한 뒤, 매 스텝마다 어떤 방식으로 행과 열을 교환하는지를 보여주면, 개념을 더욱 명확히 이해할 수 있다.
우선 아래와 같은 $3\times 3$ 행렬 $\mathbf{A}$와 우변 벡터 $\mathbf{b}$를 가정하자.
이제 해당 시스템 $\mathbf{A}\mathbf{x} = \mathbf{b}$에 대해 부분 피벗과 완전 피벗이 차이를 가져오는 과정을 단계적으로 살펴본다.
부분 피벗을 적용한 가우스 소거 예시
1단계($k=1$ 단계라 하자)에서, 부분 피벗은 열 고정 상태에서 행만 교환한다. $k=1$일 때, 가능한 피벗 후보는 $a_{11} = 2$, $a_{21} = 1$, $a_{31} = 0.1$ 이다. 절댓값을 비교해 보면
중 가장 큰 값은 $2$이다. 현재 1행이 이미 최대값을 갖고 있으므로, 부분 피벗에서는 행 교환 없이 바로 소거를 진행한다. 이렇게 해서 1단계가 진행되면,
$m_{21} = a_{21}/a_{11} = 1/2 = 0.5$,
$m_{31} = a_{31}/a_{11} = 0.1/2 = 0.05$,
등을 구해 2행과 3행을 업데이트한다.
반면, 만일 현재 1열에 $|a_{31}|$이 2보다 더 컸다면, 그 행을 1행과 교환하게 될 것이다.
2단계($k=2$ 단계)에서는, 이제 2행을 피벗 행으로 삼고, 2열에서 2행 이후 행(즉 2행, 3행)의 절댓값이 가장 큰 원소가 있는 행을 찾는다. 그 위치를 2행과 교환한 뒤, 소거를 진행한다. 마찬가지 방식으로 3단계($k=3$ 단계)에 이르면 더 교환할 행이 없거나 이미 교환된 상태이므로 그냥 소거(또는 뒤로 대입(back-substitution) 준비 단계)로 마무리된다.
완전 피벗을 적용한 가우스 소거 예시
이번에는 완전 피벗을 적용해 보자. 1단계에서, 부분 피벗과 달리 열도 교환할 수 있음을 유의하자. 즉 1단계에서 $k=1$일 때, $1$행과 $1$열 기준으로 하위 행렬인
의 모든 원소 중 절댓값이 가장 큰 값을 찾는다. 이 예시에서 절댓값을 비교해 보면 가장 큰 값은 $10$(혹은 $|10|=10$)이다. 그런데 $10$이 존재하는 위치가 $(1,2)$, $(2,3)$, $(3,2)$ 여러 곳 중에서, 실제 수치로 보면 $(1,2)$와 $(2,3)$에서 $10$이 나오는 것을 발견한다. 두 값이 크기는 같으므로, 일반적으로는 가장 먼저 발견되는 위치를 선택하거나, 특정 규칙(예: 행이 작은 위치 먼저)에 의해 선택한다. 여기서는 (1,2)에 있는 $10$을 피벗으로 선택한다고 하자.
그렇다면, 우리는 **현재 피벗 위치가 (1,1)이 아니라 (1,2)**라는 것을 의미한다. 완전 피벗 알고리즘에 따르면, 우선 1행은 1행 자체이니 행 교환은 필요가 없다(피벗 원소가 여전히 1행에 있으므로). 하지만, 열은 2열이 피벗 열이므로 1열과 2열을 교환해야 한다. 즉
을 수행한다. 그렇게 되면 행렬 $\mathbf{A}$는 내부적으로 열들이 맞바뀐 상태가 되고, 우변 $\mathbf{b}$와 $\mathbf{x}$의 대응 또한 고려되어야 한다(해당 열 교환이 행렬의 해석에 따라 $\mathbf{x}$ 벡터의 순서를 재배치하는 효과가 있기 때문이다).
그 후 1단계 소거를 수행한다. 2단계($k=2$)에서도 남아 있는 부분행렬(2행, 3행과 2열, 3열)에 대하여 절댓값이 가장 큰 원소를 찾아서 2행과 교환하거나, 2열과 교환하는 식으로 진행하게 된다.
계수행렬과 해 벡터에 대한 열 교환 처리
완전 피벗을 수행할 때, 열을 교환한다는 것은 $\mathbf{A}$의 열을 뒤섞는 것과 동시에, 해 벡터 $\mathbf{x}$의 순서 역시 같은 방식으로 뒤섞이는 효과를 가져야 시스템이 일관성을 유지한다. 예를 들어, $k$단계에서 $c_k \ne k$라면, $k$열과 $c_k$열을 맞바꿀 뿐 아니라 해 벡터 $\mathbf{x}$ 내부에서도 $x_k$와 $x_{c_k}$가 교환된다고 해석할 수 있다. 수치해석 구현상에서는 이를 기록해 두었다가, 마지막에 해 $\mathbf{x}$를 원래 순서로 되돌리는 방법을 쓴다.
즉, 완전 피벗에서 행렬만 단순 교환하고 해를 구한 뒤, 최종적으로 "어느 열이 어느 열과 교환되었는지"에 대한 이력을 역추적하여 $\mathbf{x}$의 구성 요소 순서를 재배치한다. 이 과정이 부분 피벗보다 구현 면에서 조금 번거로운 이유이다.
피벗 교환에 따른 행렬 표현 예시 (다이어그램)
아래는 $3\times 3$ 문제에서 완전 피벗으로 1단계에서 열을 교환하는 모습을 개념적으로 표시한 다이어그램 예시이다. 간단히, 1행과 1열 기준의 부분행렬에서 가장 큰 원소(절댓값)가 (1,2)에 있다고 했을 때, 그 열을 맨 왼쪽 열과 교환하는 상황을 나타낸다.
이처럼, 완전 피벗에서는 각 단계마다 열을 맞바꾸는 가능성을 열어두므로, 부분 피벗에 비해 계산 과정이 복잡해진다. 그러나 그만큼 피벗 선택에 대한 자유도가 증가하므로, 수치적으로 훨씬 더 안정적인 해를 얻을 수 있는 장점이 있다.
행렬 분해 관점에서의 피벗
가우스 소거법은 사실상 $PA=LU$ (혹은 완전 피벗일 경우 $P,A,Q = L,U$) 형태의 행렬 분해(Matrix factorization)를 구하는 과정으로 해석할 수 있다. 여기서 $P$는 행 교환을 나타내는 퍼뮤테이션 행렬(permutation matrix)이고, $Q$는 열 교환을 나타내는 퍼뮤테이션 행렬이다. 따라서 부분 피벗을 하면 $P\mathbf{A} = \mathbf{L},\mathbf{U}$의 꼴이 되고, 완전 피벗을 하면 $P,\mathbf{A},Q = \mathbf{L},\mathbf{U}$ 형태가 된다. 열 교환을 추가로 고려해야 하므로 이론적 차원이 한층 확장되는 셈이다.
LU 분해와 피벗 행렬
가우스 소거법 과정은 결국 $\mathbf{A}$를 $\mathbf{L}\mathbf{U}$로 분해하는 과정과 동일하게 볼 수 있다. 행 교환이 발생하면 $\mathbf{A}$ 대신 $P,\mathbf{A} = \mathbf{L}\mathbf{U}$ 형태가 되고, 열 교환까지 고려하면 $P,\mathbf{A},Q = \mathbf{L}\mathbf{U}$ 형태로 확장된다. 여기서 $P$는 행 교환을 나타내는 퍼뮤테이션 행렬이고, $Q$는 열 교환을 나타내는 퍼뮤테이션 행렬이다.
부분 피벗만 사용할 때는 $Q = \mathbf{I}$가 되어 $P,\mathbf{A} = \mathbf{L},\mathbf{U}$ 꼴이 된다. 그러나 완전 피벗을 수행하면 $Q \ne \mathbf{I}$가 되어 $P,\mathbf{A},Q = \mathbf{L},\mathbf{U}$라는 더욱 일반적인 형태가 된다. 이때, $\mathbf{L}$은 가우스 소거법에서의 전진 소거(forward elimination) 과정에서 생기는 계수들을 하삼각 행렬로 모아둔 것이고, $\mathbf{U}$는 소거를 마친 뒤의 상삼각 행렬이다.
피벗의 교환 여부에 따라, $\mathbf{L}$이 순수하게 하삼각 행렬 형태를 유지하되(대각 원소는 모두 1), $P$와 $Q$가 가우스 소거 과정에서의 행·열 교환을 기호적으로 표현한다. 완전 피벗은 수치 안정성 제고를 위해, 절댓값 기준으로 가장 큰 원소를 피벗으로 삼기 때문에 $\mathbf{U}$의 대각 원소가 지나치게 작거나 0에 가까워지는 상황을 훨씬 줄여 준다.
연산 비용과 구현 난이도
부분 피벗은 각 단계마다 현재 열에서 최대값을 갖는 행만 찾으면 되므로, $n\times n$ 행렬에서 가우스 소거법의 $k$번째 단계마다 $n-k+1$개 행의 절댓값을 비교하면 된다. 전체적으로는 $O(n^2)$ 정도의 비교 연산을 추가로 요구한다고 볼 수 있다.
완전 피벗은 각 단계마다 남아 있는 부분 행렬의 모든 원소를 비교해야 하므로, $k$번째 단계에서 $(n-k+1)\times (n-k+1)$개 원소에 대한 절댓값 비교가 필요하다. 결국 전체 관점에서 $O(n^3)$ 규모의 비교 연산이 추가되어, 부분 피벗보다 더 많은 연산 비용이 든다. 또한 각 단계에서 열 교환이 발생할 수 있으므로, 결과적으로 $\mathbf{A}$의 열과 $\mathbf{b}$(또는 $\mathbf{x}$)의 성분에 대한 추가 조작이 필요해 구현 난이도가 증가한다.
현실적인 관점에서, 부분 피벗만으로도 안정성이 매우 훌륭한 경우가 많다. 그러나 학술적·이론적으로는 완전 피벗이 더욱 안전하며, 특정 상황(예를 들어 특이 행렬에 가까운 계수행렬, 혹은 매우 큰 스케일 차이를 갖는 행렬)에서는 완전 피벗이 결정적으로 유리하다.
피벗 선택과 반올림 오차
수치해석에서는 컴퓨터 부동소수점(floating-point) 오차가 필연적으로 발생한다. 피벗 선택이 좋지 않으면, 매우 작은 수를 나누는 연산이 빈번하게 나타날 수 있고, 그로 인해 반올림 오차가 더욱 커지게 된다. 특히 피벗 원소가 0에 가깝다면, 실제 계산 과정에서 큰 값이 분모에 등장하여 결과가 왜곡될 우려가 있다.
부분 피벗과 완전 피벗은 이러한 문제를 완화하기 위한 전략이다. 부분 피벗은 선택된 열에서만 최대값을 고르는 것이지만, 그래도 가우스 소거 무피벗(no pivoting)에 비해서는 월등히 안정적이다. 반면 완전 피벗은 더 넓은 후보(열 전체)를 대상으로 최대값을 고르므로, 더욱 안정적으로 계산되며, 각 단계에서의 피벗 원소가 비교적 큰 값을 유지할 수 있다.
행렬 컨디션 넘버와 피벗의 관계
행렬 $\mathbf{A}$의 컨디션 넘버(condition number)는 대체로 $\mathbf{A}$가 어떤 연산(예: 역행렬 연산)에 대해 얼마나 민감하게 반응하는지를 평가하는 척도이다. 피벗을 통해 연산 순서를 바꿔도, 이론적으로는 행렬의 컨디션 넘버 자체가 달라지지는 않는다. 다만 실제 컴퓨터 부동소수점 연산에서, 피벗 선택에 따라 일어나는 작은 반올림 오차의 누적 정도가 달라지므로, 해석적으로는 "나쁜 컨디션"을 갖는 행렬도 완전 피벗을 적용하면 실제 계산에서 조금 더 안전해질 가능성이 높다.
컨디션 넘버가 극도로 큰 행렬(즉 $\mathbf{A}$가 거의 특이(singular)에 가까운 행렬)은 부분 피벗으로도 충분히 위험할 수 있으며, 이럴 때는 완전 피벗 이상의 안정화 전략(대각 스케일링, iterative refinement, 정규화 기법 등)을 함께 고려해야 한다.
피벗과 스케일링 기법
스케일링(scaling)은 행렬의 행이나 열을 적절히 곱하거나 나누어서, 행렬 원소들이 지나치게 크거나 작은 값을 갖지 않도록 미리 조정하는 기법이다. 실제 수치해석 라이브러리(예: LAPACK, MATLAB 등)에서는, 가우스 소거 시 자동으로 행 또는 열 단위의 스케일링을 적용한 후 피벗 선택을 수행하는 경우도 있다. 이렇게 하면, 행렬의 특정 행이나 열만 유난히 크게 혹은 작게 나타나는 스케일 문제로 인한 피벗 선택의 왜곡이 줄어들 수 있다.
부분 피벗과 결합한 스케일링 기법을 일반적으로 scaled partial pivoting이라고 하고, 완전 피벗과 결합한 경우를 scaled complete pivoting이라고 한다. 스케일링을 수행하는 순서는 각 라이브러리마다 조금씩 다르지만, 보통 소거 과정에 들어가기 전 또는 각 단계에서 피벗 선택하기 직전에 행·열의 크기를 점검하고, 이를 기준으로 피벗 우선순위를 조정한다.
코드 구현 시 고려사항
가우스 소거법을 직접 구현할 때, 부분 피벗이나 완전 피벗의 과정에서 다음과 같은 요소들을 세심하게 다뤄야 한다.
실제로 시스템 해 $\mathbf{x}$를 구한 뒤, 그 해가 옳게 계산되었는지를 확인하기 위해 $||\mathbf{A}\mathbf{x}-\mathbf{b}||$ 같은 검증을 수행할 수 있다. 부분 피벗과 완전 피벗을 각각 적용한 뒤, 동일한 문제에서 오차가 어느 쪽이 더 작게 나타나는지 비교해 보는 것도 좋은 실습이 된다.
행렬이 매우 클 때는, 열 교환이 추가되는 완전 피벗이 연산 비용 면에서 부담이 되므로, 대규모 문제에서는 보통 부분 피벗 이상을 적용하되 완전 피벗은 생략하는 경우가 많다. 하지만 중간 크기 정도의 문제나 수치 안정성이 절대적으로 중요한 상황에서는 완전 피벗이 유리할 수 있다.
더 나아간 피벗 선택 전략
앞서 살펴본 부분 피벗(partial pivoting)과 완전 피벗(complete pivoting) 외에도, 수치 안정성을 높이는 또 다른 피벗 전략들이 제안되어 왔다. 예컨대 **룩 피벗(rook pivoting)**이나 스케일 조정된 피벗(scaled pivoting) 등이 있는데, 이들은 부분 혹은 완전 피벗에 비해 좀 더 세분화된 방식으로 피벗을 선택한다. 다만, 대부분의 일반적 문제에서는 부분 피벗이나 완전 피벗이 이미 충분히 우수하며, 실무 환경에서 가장 널리 쓰인다.
룩 피벗의 개념을 간단히 언급하면, $k$단계에서 $k$행 이하, $k$열 이하 부분행렬을 모두 보되, 한 번에 최대값을 찾는 것(완전 피벗)과 달리 “현재 후보 피벗의 행과 열에서 절댓값이 가장 큰 위치를 반복적으로 교차 탐색”하는 방법이다. 이를 통해 최적의 피벗을 찾아내려 하며, 이론적으로 완전 피벗에 버금가거나 유사한 안정성을 기대할 수 있다. 그러나 구현이 더 복잡해지고, 연산 비용 또한 증가한다.
해석적 측면: 축소 연산과 메모리 접근
가우스 소거법 자체가 $O(n^3)$ 복잡도를 갖는 가운데, 부분 피벗은 각 단계마다 열 방향으로 최대값을 찾으므로 $O(n^2)$ 추가 연산, 완전 피벗은 부분행렬 전체에서 최대값을 찾으므로 $O(n^3)$에 가까운 비교 연산을 요구한다. 그뿐만 아니라 열 교환 시, 1단계에서 1열과 어떤 열을 바꿨다면, 2단계 이상에서도 바뀐 열 위치가 그대로 유지된 상태로 소거를 진행해야 한다. 이는 메모리 접근 관점에서 구현 난이도를 높일 수 있으며, 대형 행렬에서는 캐시 효율 관점도 고려해야 한다.
부분 피벗은 보통 다음과 같은 배열 구조로 구현한다. 행렬 $\mathbf{A}$의 내용을 2차원 배열에 저장하고, 피벗 배열(보통 길이가 $n$인 정수 배열)을 둬서 각 단계에서 어떤 행과 스왑(swap)할지 기록한다. 그러나 완전 피벗은 행 피벗 배열(행이 어떤 순서로 교환되었는지)뿐 아니라 열 피벗 배열(열이 어떤 순서로 교환되었는지)까지 추적해야 한다. 최종적으로 해 $\mathbf{x}$를 복원할 때, 열 피벗 배열의 정보를 사용해 $\mathbf{x}$의 순서를 다시 맞춰야 한다.
LU 분해에서의 피벗 배열 관리
수식으로, $P,\mathbf{A},Q = \mathbf{L},\mathbf{U}$ 형태의 완전 피벗을 예로 들면, $P$는 (행 교환을 기록한) 퍼뮤테이션 행렬, $Q$는 (열 교환을 기록한) 퍼뮤테이션 행렬이다. 실제 코드 레벨에서 $Q$는 어떤 정수 배열 $q$로 관리되는데, 가령 $q[k] = c_k$는 $k$단계에서 선택된 피벗 열이 $c_k$임을 의미한다. 최종 해를 구하고 나면, $\mathbf{x}$ 벡터 또한 해당 순서에 맞춰 재배열해야 한다. 부분 피벗만 적용한 경우라면 $Q=\mathbf{I}$이므로 이 과정이 생략 가능하다.
대규모 희소 행렬 문제에서의 고려
희소 행렬(sparse matrix)에서 직접 가우스 소거법을 쓰게 되면, 부분 피벗이나 완전 피벗으로 인해 행렬의 구조가 쉽게 무너져 “채움(fill-in)”이 크게 늘어날 수 있다. 이때는 희소 행렬 특화된 분해 알고리즘(예: 고성능 희소 LU 분해)에 피벗 선택 규칙을 포함시키거나, 대안적으로 직교화 기법(예: Householder QR 분해)을 고려하기도 한다.
부분 피벗은 행만 뒤섞으므로 비교적 희소 구조가 유지되기 쉽지만, 완전 피벗은 열까지 교환하므로 희소성 유지가 더 까다롭다. 이런 측면에서 희소 행렬 전용 알고리즘은 보통 “정규 부분 피벗(numerical partial pivoting)” 수준만 구현하고, 완전 피벗은 스킵하는 경우가 많다.
수치 안정성 평가 지표
가우스 소거법을 수행할 때, 단계별로 계산되는 $\mathbf{U}$의 대각 원소가 지나치게 작아지면(예: 부동소수점 범위에서 언더플로우 혹은 반올림 오차가 커질 만큼 작은 값), 후속 계산에서 곤란을 겪을 수 있다. 피벗 선택을 적절히 하는 것은 이 문제를 방지하는 핵심이다.
추가로, “pivot growth factor”라는 개념으로, $\mathbf{L}\mathbf{U}$ 분해를 진행하면서 행렬 원소가 얼마나 커지거나 작아지는지를 추적해 볼 수 있다. 완전 피벗이 pivot growth factor를 상대적으로 작게 유지한다는 사실이 알려져 있어, 안정성 면에서 완전 피벗이 우수하다고들 평가한다.
이론적 결과
행렬이 비특이(nonsingular)라고 가정할 때, 부분 피벗을 쓴 가우스 소거법은 일반적으로 $n$차 행렬에 대해 안정적인 해를 산출한다고 알려져 있다(실무에서 거의 표준으로 쓰이기도 한다). 완전 피벗은 그보다 더 안정적이지만, 같은 차수($n$)라면 확실히 더 많은 연산을 요구한다. 이론적으로 상당히 큰 $n$에 대해서는 연산 비용 절감 측면에서 부분 피벗이 선호된다.
학술적으로도, Wilkinson의 분석에 의하면 부분 피벗만으로도 대부분의 경우 안정적이라는 점이 많이 인용된다. 그러나 “대부분”이라는 것은 무작위(random) 성격의 행렬이나 일반적인(average) 행렬을 말할 때이고, 매우 특수하거나 극도로 ill-conditioned한 경우에는 완전 피벗 이상의 기법을 추가 도입하는 것이 안전하다.
예시: Hilbert 행렬
아주 유명한 ill-conditioned 행렬 예시로 **힐베르트 행렬(Hilbert matrix)**이 있다. $n\times n$ 힐베르트 행렬은
로 정의되는데, 이 행렬은 커질수록 대단히 ill-conditioned해진다. 부분 피벗을 해도 반올림 오차가 크게 누적되며, 완전 피벗을 적용해도 오차가 작아지긴 하지만 여전히 안정성 문제가 남는다. 그렇다 해도, 무피벗 가우스 소거법에 비하면 부분 피벗, 완전 피벗 순으로 훨씬 나은 결과를 보여 준다.
--- 관점
가우스 소거법에서 피벗 선택은 필수적인 단계이다. 부분 피벗과 완전 피벗의 개념적 차이는 “열 교환 유무”에 달려 있고, 완전 피벗이 더 안정적이라는 점은 이미 역사적으로도 수많은 연구 결과로 검증되었다. 다만 완전 피벗은 그만큼 구현이 복잡하고 연산량이 늘어난다는 점도 감안해야 하므로, 문제 규모나 행렬의 성질(희소성, ill-conditioned 여부 등)에 따라 적절한 타협이 필요하다.
피벗 선택의 역사적 배경과 표준 알고리즘
가우스 소거법이 정립된 뒤로, “피벗을 어떻게 고르는가?”라는 문제는 초기부터 큰 주목을 받았다. 가우스 이후 조르당(Jordan), 크라우트(Crout) 등 여러 수학자·공학자가 엇비슷한 절차를 연구·정리하면서, 실질적으로는 20세기에 들어서야 디지털 컴퓨터의 등장과 함께 반올림 오차 문제까지 중요해졌다. 1960년대부터 1970년대까지 Wilkinson을 비롯한 수치해석학자들이 이 분야에 대한 이론적 분석을 진행하면서, “부분 피벗은 실용적으로 거의 모든 문제에서 안정적이다”라는 관찰 결과가 널리 확산되었다.
컴퓨터 공학의 관점에서는, BLAS(Basic Linear Algebra Subprograms)나 LAPACK 등 표준 라이브러리들이 대부분 부분 피벗(혹은 스케일링을 적용한 부분 피벗)을 사용한다. 완전 피벗은 원소가 극단적으로 작은 행렬이나, 숫자 오차가 매우 치명적인 문제를 다룰 때 선택적으로 쓴다. LAPACK 코드 내부를 살펴보면, 부분 피벗에 대한 분해 루틴들이 가장 많이 쓰이며, 완전 피벗 루틴도 존재하지만 상대적으로 덜 사용된다는 점을 알 수 있다.
축차적 행렬 분해와 피벗
가우스 소거법 외에도, LU 분해를 점진적으로 구성해 나가는 다양한 방법이 제안되어 왔다. 예를 들어, “블록(block) 분해” 방식을 취하거나, “맞춤형 행렬 분할 전략”을 활용하여 병렬화(parallelization) 효율을 높이려는 시도도 있다. 이때도 피벗의 선택은 빠질 수 없는데, 부분 피벗을 블록 단위로 적용하는 방안을 “block partial pivoting”이라 부른다. 완전 피벗 역시 블록 단위로 확장할 수 있으나, 구현이 한층 복잡해지고 캐시 최적화나 통신량 문제도 고려해야 한다.
GPU 및 병렬 환경에서의 피벗 고려
현대는 CPU뿐 아니라 GPU(그래픽 처리 장치)를 이용해 대규모 선형대수 연산을 병렬 처리하는 경우가 많다. GPU 메모리로 데이터를 넘기고, 가우스 소거(혹은 LU 분해)를 수행하며, 피벗 교환을 자주 일으키는 것은 곧 메모리 접근 패턴을 복잡하게 만들어 성능을 떨어뜨릴 수 있다. 따라서 병렬 처리용 라이브러리(예: cuBLAS, MAGMA 등)는 “pivot-free” 방식의 LU 분해나, 제한된 부분 피벗 전략을 채택하기도 한다.
특히, “pivot-free” LU 분해 방식들은 특정 조건(예: 행렬이 대각 우세(diagonally dominant)하거나 양의 정부호(positive definite)인 경우)에서만 적용이 가능하다. 그 조건이 보장된다면, 실제 연산에서 피벗 교환 없이도 안정적으로 결과를 낼 수 있다고 알려져 있다. 그렇지 않은 일반 행렬에는 여전히 부분 피벗 이상이 필요하다.
반올림 오차 추정과 backward error analysis
수치해석에서 얻은 해의 정확성을 평가할 때, “forward error”와 “backward error”라는 개념을 쓴다. forward error는 해 $\mathbf{x}$와 실제 해 $\mathbf{x}^*$ 사이의 차이를 직접 측정하는 방식이고, backward error는 “계산 결과로 얻어진 $\hat{\mathbf{x}}$가 정확한 해가 되도록 하는 가상 문제 $\mathbf{A}+\Delta \mathbf{A},;\mathbf{b}+\Delta\mathbf{b}$가 과연 얼마나 원래 문제와 가까운가?”를 측정한다.
피벗 교환을 잘 했을 때는, $\Delta \mathbf{A}$와 $\Delta \mathbf{b}$가 작게 억제되어 backward error가 작아진다. 즉, 실제 계산에서 야기되는 수치 오차가 문제를 크게 변형하지 않았다는 뜻이므로, 결과 해석이 신뢰도가 높아진다. 반면 피벗 선택이 부적절하면, 작은 부동소수점 오차가 뒤로 갈수록 크게 증폭되어 large backward error가 발생할 수 있다.
분수 스텝에서의 불안정성
가우스 소거법이 “뒤에서부터 대입(back-substitution)”하기 전에 수행하는 전진 소거(forward elimination) 단계에서는, 피벗 원소로 나누는 연산이 빈번하다. 피벗이 매우 작으면 $m_{ik}=a_{ik}/a_{kk}$에서 분모가 거의 0에 가까워질 수 있으며, 그로 인해 $m_{ik}$가 매우 커져 후속 연산에서 소수점 아래 자릿수가 크게 손실될 우려가 있다. 이는 분모가 작을 때 전형적으로 일어나는 catastrohpic cancellation(대규모 취소)이나 오차 증폭을 유발한다.
타 분야와의 연계: PDE와 FEM
선형 시스템 $\mathbf{A}\mathbf{x} = \mathbf{b}$는 편미분방정식(PDE)을 유한요소법(FEM) 등으로 이산화(discretization)했을 때도 나타난다. 특히, 2차원·3차원 도메인의 세분(mesh)으로 인해 매우 큰 규모의 선형 시스템이 형성되며, 이 계수행렬은 보통 희소하고, 구조적 패턴을 가진다. 이런 FEM 행렬(특히 정상행렬, 좌표변환에 의해 대각 우세를 갖는 행렬 등)은 보통 부분 피벗만으로도 안정적인 경우가 많다. 그러나 어떤 PDE 문제에서는 특정 위치에 물리량이 급격히 변하거나(경계층 문제, 충격파 문제 등) 스케일 차이가 엄청날 경우, 완전 피벗을 적용하거나 다른 정규화 기법을 병행하는 편이 안전하다.
다른 해법과의 비교
가우스 소거법 말고도, QR 분해나 SVD(특잇값 분해) 기반 방법이 해를 구하는 데 활용되곤 한다. 이들 방법은 가우스 소거에 비해 수치적으로 더 안정적일 가능성이 있다(특히 SVD), 그러나 연산량이 상대적으로 많고, 구성요소가 더 복잡하다. 그럼에도 불구하고 매우 ill-conditioned한 문제에서는 SVD로 접근하기도 한다. 피벗 전략 자체가 가우스 소거법에 특유한 개념이긴 하지만, QR 분해에서는 하우스홀더 반사(Householder reflection) 과정에서의 반올림 오차 누적을 제어하기 위한 유사 개념의 과정이 존재한다.
알고리즘적 관점 요약
가우스 소거법(무피벗): 매우 빠르나, 반올림 오차 문제로 실제로는 권장되지 않음
부분 피벗: 열 단위 최대값만 교환. 대부분의 실무·실험에서 표준으로 쓰임
완전 피벗: 행과 열 모두 교환. 안정성 최고 수준. 연산량·구현 난이도 증가
블록 피벗·룩 피벗 등: 부분·완전 피벗의 중간 혹은 변형. 구체적 상황에 따라 채택
(스케일링 결합) scaled partial pivoting, scaled complete pivoting: 원소의 크기 차를 보정하며 피벗 선택
부동소수점 특성을 고려하면, 이미 부분 피벗만 잘 적용해도 대부분의 일반적 문제에서 꽤 높은 안정성을 얻는다. 다만 “모든 상황”을 안전하게 처리하려면 완전 피벗이나 다른 고급 기법을 도입할 필요가 있다.
병렬 및 대규모 계산에서의 추가 이슈
가우스 소거법을 대규모 문제(수만, 수십만 차원 이상의 행렬)에도 직접 적용할 때는, 실제로는 “직접법(direct method)”보다 “간접법(iterative method)”이 선호되는 경우가 많다. 예컨대, CG(Conjugate Gradient), GMRES(Generalized Minimal Residual), BiCGSTAB 등 반복법이 큰 문제에서 흔히 쓰인다. 그럼에도 불구하고, 구조나 분해 패턴(예: 희소 패턴)이 허용되면, 여전히 LU 분해 기반 해법을 쓰기도 하며, 이때도 피벗 선택 문제가 등장한다.
1) 정규화(대각 우세, 양의 정부호 행렬)와 피벗
행렬이 양의 정부호(positive definite)인 경우, 일반 LU 분해 대신 촐레스키(Cholesky) 분해를 적용할 수 있다. 촐레스키 분해는 $\mathbf{A}=\mathbf{L}\mathbf{L}^\mathrm{T}$ 형태로 삼각 행렬 한 개만 구하면 되므로, 일반 LU 분해보다 연산량이 절반가량 적고 구현이 단순하다. 또한 양의 정부호 행렬은 (수치오차를 배제하면) 피벗 없이도 안정적 분해가 가능하다는 이점이 있다.
실제로는 부동소수점 연산으로 인해, 완벽한 양의 정부호가 아니라면 부분 피벗 정도는 제한적으로라도 필요할 수 있다. 대규모 해석에서, 행렬이 “대각 우세(diagonally dominant) 형태를 갖는가?”, “스펙트럼이 모두 양수인가?” 등의 조건이 얼마나 잘 충족되느냐에 따라 피벗 교환 횟수가 크게 달라진다.
2) 분산 메모리 환경(MPI)에서의 피벗
MPI(Message Passing Interface) 기반으로 분산 메모리 다중 노드를 연결해 큰 행렬 연산을 진행할 경우, 가우스 소거법 상에서 행 혹은 열을 교환하는 동작은 네트워크 통신량 증가로 이어진다. 부분 피벗만으로도 이미 행 교환을 수행하려면 필요한 행 전체를 다른 프로세스와 교환해야 하고, 완전 피벗은 열 교환까지 고려하므로 훨씬 더 복잡하다.
이러한 이유로, 분산 메모리 환경에서는 “lookahead”이나 “2D/3D 블록 순환 배치(block-cyclic distribution)” 등을 통해, 피벗 교환이 자주 일어나지 않도록 행렬을 미리 잘 배치하거나, 교환 시 통신량을 최소화하는 알고리즘 설계를 적극적으로 활용한다. ScaLAPACK 라이브러리(병렬 선형대수 표준 라이브러리)도 내부적으로 부분 피벗을 기본으로 채택하며, 블록 크기를 조절해 통신량과 계산량의 균형을 맞추고 있다.
3) GPU 가속 환경에서의 피벗
앞서 언급했듯, GPU는 대량의 부동소수점 연산을 병렬화하기에 유리하지만, 임의의 스왑(swap) 연산은 효율이 떨어질 수 있다. 예를 들어, row-major 방식으로 메모리를 배치한 경우, 행 교환은 상대적으로 간단하지만 열 교환은 느리거나, column-major 방식인 경우 반대가 될 수 있다. 완전 피벗은 행+열 교환이 필연적이므로, GPU 가속에서도 그 구현이 복잡해진다.
일부 GPU 기반 LU 분해 루틴은 “partial pivoting only” 전략을 고정 탑재하거나, 심지어 “pivot-free LU”를 선택하여 행과 열의 교환 비용을 없애는 대신, 행렬이 어느 정도 조건이 잘 갖춰진 상태임을 가정하는 방식을 취한다. 이로 인해 최적화된 커널(Compute Unified Device Architecture, CUDA 등)을 작성할 수 있고, 행렬 전체를 GPU 메모리에 상주시켜 연산을 일괄적으로 처리하는 것이 가능해진다.
고급 해석: 피벗 교환과 난수 행렬 모델
수치해석 이론에서는, 행렬 원소들이 무작위 분포(예: 가우시안)로 주어졌다고 가정하면, 부분 피벗만으로도 대부분 안정적인 결과가 나온다는 실증적·이론적 결과가 많다. 이는 실제 공학이나 과학 계산에 등장하는 행렬도 (엄밀하게 무작위는 아니지만) 통계적으로 그와 비슷한 특성을 어느 정도 띠기 때문이다.
그러나 현실에는 특정 패턴(예: 거의 특이, 특수한 구조, 매우 비정상적인 스펙트럼)을 가진 행렬이 존재한다. 이럴 때 부분 피벗이 심각하게 부족할 수 있으며, 완전 피벗이라도 적절하지 못할 정도로 ill-conditioned인 경우가 드물지 않다. 그러므로, “피벗 선택 + 스케일링 + 반복적 개선(iterative refinement) + 필요 시 사후(後) 처리” 등의 전략을 종합적으로 구사해야 할 수도 있다.
성능 및 정확도 사이의 타협
부분 피벗:
장점: 구현 용이, 표준 알고리즘 라이브러리에 내장, 대부분의 행렬에서 충분히 안정적
단점: 특정 극단적 행렬에서 불충분할 수 있음 (피벗 후보가 같은 열 내에 작은 값들만 있을 경우 등)
완전 피벗:
장점: 절대값이 가장 큰 피벗을 선택해 오차 증폭을 최소화, 최대한 안정
단점: 연산량 증가($O(n^3)$ 규모의 비교), 열 교환 구현 복잡도, 대규모·병렬 환경에서 비효율
실험적으로, $n$이 큰 일반 문제에서는 부분 피벗만으로도 “사후(iterative) 개선” 단계를 한두 번 수행하는 편이 완전 피벗을 직접 도입하는 것보다 연산량 대비 효용성이 높다는 결론이 잘 알려져 있다. 반면, $n$이 상대적으로 작고(예: 수백~수천 정도), 문제 구조가 ill-conditioned하거나 실험 오차가 미미하게라도 허용 불가한 경우(예: 매우 민감한 물리 현상 시뮬레이션)에는 완전 피벗, 혹은 그 이상의 정교한 기법(SVD, 다양한 정규화 기법 등)이 각광받는다.
부분 피벗 vs. 완전 피벗 성능 예시 (Octave)
아래는 간단한 예시이긴 하지만, “힐베르트 행렬”에서 부분 피벗과 완전 피벗의 결과 정확도를 간단히 비교해 볼 수 있는 Octave 코드이다. 실제로 수행하면, 크기가 커질수록 부분 피벗만으로는 오차가 상대적으로 커지며, 완전 피벗으로 해석하면 그보다는 낫다는 것을 확인할 수 있다.
위 코드를 실행하면, $n=5, 8, 12$ 등에서 부분 피벗과 완전 피벗 방식의 오차 크기를 각각 확인할 수 있다. (힐베르트 행렬의 참해는 $\mathbf{x}=\mathbf{1}$이 되도록 $\mathbf{b}$를 설정한 예시.) 보통 $n$이 커질수록 부분 피벗 해의 오차가 조금 더 빨리 커지며, 완전 피벗은 그래도 부분 피벗보다는 오차가 작게 유지되는 편이다.
종합 정리
가우스 소거법을 더 안정적으로 수행하기 위해서는 피벗 선택이 필수적이며, 이때 “부분 피벗”과 “완전 피벗”이 대표적으로 쓰이는 기법이다. 부분 피벗은 구현이 비교적 단순하고 대부분의 실제 문제에서 충분히 잘 동작하여, 표준 라이브러리들이 대거 채택하고 있다. 완전 피벗은 연산량과 복잡도가 더 들지만, 이론적으로 가장 안정성 높은 해결책을 제시해 준다.
하드웨어, 행렬 구조, 문제 크기 등의 요인을 고려해, “어느 단계까지 피벗을 허용하고 관리할 것인가?”라는 선택은 실무적 판단 영역이기도 하다. 실제 계산에서, 부분 피벗과 적절한 스케일링, 필요시 반복적 개선 기법 등을 병행하면, 대다수 문제에서 안정적이고 효율적인 해를 얻을 수 있다.
Last updated