6.153 대규모 행렬 연산의 계산량 분석
1. 행렬 연산의 계산 복잡도 기초
로봇공학에서 사용되는 행렬 연산의 효율성을 평가하려면 연산량(computational cost)을 체계적으로 분석하여야 한다. 계산량 분석에서는 부동소수점 연산(floating-point operation, FLOP) 횟수를 기본 단위로 사용하며, 행렬의 크기 n에 대한 점근적 복잡도(asymptotic complexity)를 빅오 표기법(Big-O notation)으로 표현한다.
하나의 부동소수점 덧셈 또는 곱셈을 1 FLOP으로 정의할 때, 곱셈과 덧셈이 쌍으로 나타나는 경우 이를 하나의 융합 곱셈-덧셈(fused multiply-add, FMA) 연산으로 취급하기도 한다. 현대 프로세서에서는 FMA가 단일 클럭 사이클에 처리되므로, FMA 기준으로 FLOP 수를 세는 것이 실제 성능 예측에 더 가깝다.
2. 기본 행렬 연산의 FLOP 분석
2.1 행렬-벡터 곱
m \times n 행렬 \mathbf{A}와 n차원 벡터 \mathbf{x}의 곱 \mathbf{y} = \mathbf{A}\mathbf{x}를 계산할 때, 결과 벡터의 각 성분은 다음과 같다.
y_i = \sum_{j=1}^{n} a_{ij} x_j, \quad i = 1, 2, \ldots, m
각 y_i의 계산에 n번의 곱셈과 (n-1)번의 덧셈이 필요하므로, 총 FLOP 수는 다음과 같다.
\text{FLOP}_{\text{matvec}} = m(2n - 1) \approx 2mn
정사각 행렬 n \times n에 대해서는 \mathcal{O}(n^2)이다.
2.2 행렬-행렬 곱
m \times p 행렬 \mathbf{A}와 p \times n 행렬 \mathbf{B}의 곱 \mathbf{C} = \mathbf{A}\mathbf{B}에서 결과 행렬의 각 원소는 다음과 같다.
c_{ij} = \sum_{k=1}^{p} a_{ik} b_{kj}
총 FLOP 수는 다음과 같다.
\text{FLOP}_{\text{matmul}} = mn(2p - 1) \approx 2mnp
정사각 행렬 n \times n의 경우 \mathcal{O}(n^3)이며, 이는 로봇공학에서 대규모 시스템을 다룰 때 가장 큰 계산 병목이 된다.
2.3 주요 행렬 연산의 계산량 요약
| 연산 | FLOP 수 (근사) | 점근 복잡도 |
|---|---|---|
| 행렬-벡터 곱 \mathbf{A}\mathbf{x} (n \times n) | 2n^2 | \mathcal{O}(n^2) |
| 행렬-행렬 곱 \mathbf{A}\mathbf{B} (n \times n) | 2n^3 | \mathcal{O}(n^3) |
| LU 분해 | \frac{2}{3}n^3 | \mathcal{O}(n^3) |
| Cholesky 분해 | \frac{1}{3}n^3 | \mathcal{O}(n^3) |
| QR 분해 (Householder) | \frac{4}{3}n^3 | \mathcal{O}(n^3) |
| 고유값 분해 (대칭) | \approx 9n^3 | \mathcal{O}(n^3) |
| 특이값 분해 (SVD) | \approx 22n^3 | \mathcal{O}(n^3) |
| 행렬 전치 | 0 (인덱싱) | \mathcal{O}(1) |
| 행렬 덧셈 \mathbf{A} + \mathbf{B} (n \times n) | n^2 | \mathcal{O}(n^2) |
3. 로봇 동역학에서의 행렬 연산 규모
3.1 관성 행렬의 계산
n자유도 로봇의 운동방정식은 다음과 같다.
\mathbf{M}(\mathbf{q})\ddot{\mathbf{q}} + \mathbf{C}(\mathbf{q}, \dot{\mathbf{q}})\dot{\mathbf{q}} + \mathbf{g}(\mathbf{q}) = \boldsymbol{\tau}
여기서 관성 행렬 \mathbf{M}(\mathbf{q}) \in \mathbb{R}^{n \times n}은 대칭 양의 정부호(symmetric positive definite) 행렬이다. Composite Rigid Body Algorithm(CRBA)을 사용하면 관성 행렬의 계산량은 \mathcal{O}(n^2)이다. 구체적으로, CRBA의 FLOP 수는 다음과 같이 추정된다.
\text{FLOP}_{\text{CRBA}} \approx 72n^2 + \alpha n
여기서 \alpha는 링크의 관성 텐서 연산에 따르는 상수이다.
3.2 순방향 동역학의 계산량
순방향 동역학(forward dynamics)에서는 관절 가속도 \ddot{\mathbf{q}}를 다음과 같이 계산한다.
\ddot{\mathbf{q}} = \mathbf{M}(\mathbf{q})^{-1}\left[\boldsymbol{\tau} - \mathbf{C}(\mathbf{q}, \dot{\mathbf{q}})\dot{\mathbf{q}} - \mathbf{g}(\mathbf{q})\right]
이 계산에서 관성 행렬의 역행렬 또는 선형 시스템의 풀이가 필요하며, 직접 역행렬을 구하는 대신 Cholesky 분해를 활용하면 효율적이다. \mathbf{M}이 대칭 양의 정부호이므로 Cholesky 분해 \mathbf{M} = \mathbf{L}\mathbf{L}^\top을 적용할 수 있으며, 분해와 전방/후방 대입(forward/backward substitution)의 총 계산량은 다음과 같다.
\text{FLOP}_{\text{Cholesky+solve}} = \frac{1}{3}n^3 + 2n^2
Articulated Body Algorithm(ABA)을 사용하면 순방향 동역학을 \mathcal{O}(n) 복잡도로 수행할 수 있어, 고자유도 로봇에서 큰 이점을 제공한다.
3.3 자코비안 관련 연산
6 \times n 자코비안 행렬 \mathbf{J}(\mathbf{q})와 관련된 연산들의 계산량은 다음과 같다.
| 연산 | FLOP 수 (근사) | 비고 |
|---|---|---|
| \mathbf{J}\dot{\mathbf{q}} | 12n | 말단 속도 계산 |
| \mathbf{J}^\top \mathbf{f} | 12n | 관절 토크 매핑 |
| \mathbf{J}\mathbf{J}^\top | 12n \cdot 6 = 72n | 작업 공간 관성 관련 |
| \mathbf{J}^\top\mathbf{J} | 6n^2 | 관절 공간 관련 |
| \mathbf{J}의 의사 역행렬 | \mathcal{O}(n^2) ~ \mathcal{O}(n^3) | SVD 또는 QR 기반 |
4. 희소성 활용과 계산량 절감
4.1 희소 행렬의 구조적 특성
로봇공학의 대규모 시스템에서 나타나는 행렬은 대부분 희소(sparse)하다. 다관절 로봇의 관성 행렬은 연쇄 구조(serial chain)의 경우 밴드 구조(banded structure)를 가지며, 트리 구조나 병렬 메커니즘의 경우에도 특정한 희소 패턴을 보인다.
n \times n 행렬에서 비영(non-zero) 원소의 수를 \text{nnz}라 하면, 희소도(sparsity)는 다음과 같이 정의된다.
\text{sparsity} = 1 - \frac{\text{nnz}}{n^2}
밴드 폭 b인 밴드 행렬(banded matrix)의 경우, \text{nnz} = \mathcal{O}(nb)이므로 b \ll n이면 매우 높은 희소도를 가진다.
밴드 행렬의 연산 효율
대칭 양의 정부호인 밴드 행렬에 대한 Cholesky 분해의 계산량은 다음과 같이 줄어든다.
\text{FLOP}_{\text{band-Cholesky}} \approx \frac{1}{2}nb^2
이는 밀집 행렬(dense matrix)의 \frac{1}{3}n^3에 비해 b \ll n일 때 극적인 절감 효과를 가져온다. 예를 들어, n = 100이고 b = 5인 경우, 밀집 Cholesky 분해는 약 333{,}333 FLOP이 필요하지만, 밴드 Cholesky 분해는 약 1{,}250 FLOP으로 약 267배 빠르다.
4.2 블록 대각 구조의 활용
다수의 독립적인 서브시스템으로 구성된 로봇 시스템(예: 다수의 협동 로봇)에서는 전체 관성 행렬이 블록 대각(block diagonal) 구조를 가질 수 있다.
\mathbf{M}_{\text{total}} = \begin{bmatrix} \mathbf{M}_1 & \mathbf{0} & \cdots & \mathbf{0} \\ \mathbf{0} & \mathbf{M}_2 & \cdots & \mathbf{0} \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{M}_k \end{bmatrix}
여기서 각 \mathbf{M}_i \in \mathbb{R}^{n_i \times n_i}이고 \sum_{i=1}^{k} n_i = N이다. 블록 대각 행렬의 분해는 각 블록을 독립적으로 처리할 수 있으므로, 총 계산량은 다음과 같다.
\text{FLOP}_{\text{block}} = \sum_{i=1}^{k} \frac{1}{3}n_i^3 \leq \frac{1}{3}N^3
등분할 n_i = N/k인 경우, \text{FLOP}_{\text{block}} = \frac{1}{3} \cdot k \cdot (N/k)^3 = \frac{N^3}{3k^2}이므로, k개의 블록으로 분할하면 계산량이 1/k^2로 감소한다.
5. 스트라센 알고리즘과 고속 행렬 곱셈
표준 행렬 곱셈의 \mathcal{O}(n^3) 복잡도를 줄이기 위한 이론적 알고리즘으로 스트라센(Strassen) 알고리즘이 있다. 스트라센 알고리즘은 2 \times 2 블록 분할을 통해 8번의 행렬 곱셈을 7번으로 줄이며, 재귀적으로 적용하면 복잡도가 다음과 같다.
\mathcal{O}(n^{\log_2 7}) \approx \mathcal{O}(n^{2.807})
두 n \times n 행렬 \mathbf{A}, \mathbf{B}를 2 \times 2 블록으로 분할한다.
\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{bmatrix}, \quad \mathbf{B} = \begin{bmatrix} \mathbf{B}_{11} & \mathbf{B}_{12} \\ \mathbf{B}_{21} & \mathbf{B}_{22} \end{bmatrix}
스트라센 알고리즘은 7개의 보조 행렬 곱을 정의한다.
\begin{aligned} \mathbf{P}_1 &= (\mathbf{A}_{11} + \mathbf{A}_{22})(\mathbf{B}_{11} + \mathbf{B}_{22}) \\ \mathbf{P}_2 &= (\mathbf{A}_{21} + \mathbf{A}_{22})\mathbf{B}_{11} \\ \mathbf{P}_3 &= \mathbf{A}_{11}(\mathbf{B}_{12} - \mathbf{B}_{22}) \\ \mathbf{P}_4 &= \mathbf{A}_{22}(\mathbf{B}_{21} - \mathbf{B}_{11}) \\ \mathbf{P}_5 &= (\mathbf{A}_{11} + \mathbf{A}_{12})\mathbf{B}_{22} \\ \mathbf{P}_6 &= (\mathbf{A}_{21} - \mathbf{A}_{11})(\mathbf{B}_{11} + \mathbf{B}_{12}) \\ \mathbf{P}_7 &= (\mathbf{A}_{12} - \mathbf{A}_{22})(\mathbf{B}_{21} + \mathbf{B}_{22}) \end{aligned}
결과 행렬은 다음과 같이 조합된다.
\begin{aligned} \mathbf{C}_{11} &= \mathbf{P}_1 + \mathbf{P}_4 - \mathbf{P}_5 + \mathbf{P}_7 \\ \mathbf{C}_{12} &= \mathbf{P}_3 + \mathbf{P}_5 \\ \mathbf{C}_{21} &= \mathbf{P}_2 + \mathbf{P}_4 \\ \mathbf{C}_{22} &= \mathbf{P}_1 - \mathbf{P}_2 + \mathbf{P}_3 + \mathbf{P}_6 \end{aligned}
그러나 실제 로봇공학 응용에서는 행렬 크기가 수십~수백 정도이므로, 스트라센 알고리즘의 이점이 나타나지 않는 경우가 많다. 캐시 효율성 저하와 수치 안정성 문제로 인해, 실무에서는 최적화된 \mathcal{O}(n^3) 구현이 더 선호된다.
6. 계산량과 메모리 대역폭의 균형
6.1 산술 강도
현대 프로세서에서 실제 성능은 FLOP 수만으로 결정되지 않는다. 메모리에서 데이터를 읽고 쓰는 시간이 연산 시간보다 긴 경우가 많으며, 이를 정량화하기 위해 산술 강도(arithmetic intensity)를 사용한다.
\text{AI} = \frac{\text{FLOP 수}}{\text{메모리 접근 바이트 수}}
행렬-벡터 곱의 경우 \text{AI} \approx 2n^2 / (8n^2 + 8n) \approx 1/4 FLOP/바이트(배정밀도 기준)이므로 메모리 대역폭 제한(memory-bandwidth bound)에 해당한다. 반면, 행렬-행렬 곱은 \text{AI} \approx 2n^3 / (3 \cdot 8n^2) = n/12 FLOP/바이트이므로 n이 충분히 크면 연산 제한(compute-bound)이 된다.
루프라인 모델
루프라인(roofline) 모델은 산술 강도를 기반으로 연산의 최대 성능을 예측하는 도구이다. 피크 연산 성능 \pi (FLOP/s)와 메모리 대역폭 \beta (바이트/s)가 주어졌을 때, 달성 가능한 최대 성능 P는 다음과 같다.
P = \min(\pi, \; \text{AI} \times \beta)
이 모델에 따르면, 행렬-벡터 곱은 대부분의 하드웨어에서 메모리 대역폭에 의해 제한되며, 행렬-행렬 곱은 충분히 큰 행렬에서 피크 연산 성능에 접근할 수 있다.
7. 로봇공학에서의 실제 계산량 사례
6자유도 산업용 매니퓰레이터의 주요 연산에 대한 실제 FLOP 수를 정리하면 다음과 같다.
| 연산 | 알고리즘 | FLOP 수 (근사) | 1 GHz에서 소요 시간 |
|---|---|---|---|
| 역동역학 | RNEA | \approx 800 | 0.8 \; \mu\text{s} |
| 관성 행렬 계산 | CRBA | \approx 2{,}600 | 2.6 \; \mu\text{s} |
| 순방향 동역학 | ABA | \approx 1{,}100 | 1.1 \; \mu\text{s} |
| 순방향 동역학 | CRBA + Cholesky | \approx 2{,}700 | 2.7 \; \mu\text{s} |
| 자코비안 계산 | 기하학적 방법 | \approx 400 | 0.4 \; \mu\text{s} |
| 순방향 기구학 | DH 변환 연쇄 | \approx 300 | 0.3 \; \mu\text{s} |
이러한 수치는 단일 연산에 대한 것이며, 1 kHz 실시간 제어 루프에서는 한 주기(1 ms)당 수백만 FLOP의 여유가 있으므로 6자유도 로봇의 동역학 연산은 충분히 실시간으로 처리 가능하다. 그러나 접촉이 있는 시뮬레이션, 경로 최적화, 다수 로봇의 동시 제어 등에서는 계산량이 급격히 증가하여 체계적인 최적화가 필요하다.
8. 점근 분석의 한계와 실제 성능
빅오 표기법은 점근적 행동만을 기술하므로, 실제 성능 평가에서는 상수 계수, 캐시 효과, 분기 예측 등 하드웨어 특성이 중요한 역할을 한다. 예를 들어, \mathcal{O}(n^3) 알고리즘이라 하더라도 BLAS Level 3로 최적화된 행렬 곱은 피크 성능의 90% 이상을 달성할 수 있는 반면, 최적화되지 않은 구현은 피크 성능의 1~5%에 그칠 수 있다.
따라서 로봇공학에서 대규모 행렬 연산을 다룰 때는 점근 복잡도와 함께 실제 하드웨어에서의 구현 효율을 반드시 고려하여야 한다.
참고문헌
- Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
- Featherstone, R. (2008). Rigid Body Dynamics Algorithms. Springer.
- Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
- Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
- Williams, S., Waterman, A., & Patterson, D. (2009). “Roofline: an insightful visual performance model for multicore architectures.” Communications of the ACM, 52(4), 65–76.
v 0.1