2.5 Matrix Factorization

Factorization(인수분해)

* Matrix Factorization은 Matrix를 두 개 이상의 Marix들의 곱으로 나타내는 것을 뜻한다.

* 예를 들어 Matrix A=BC로 표현하는 것 등을 뜻한다.

LU Factorization

* LU Factorization은 특정 matrix를 LU로 분해하는 것을 뜻한다. 여기서 L은 A unit lower triangular marix이고, U는 ehelon form(reduced가 아니라는 것을 주의)인 matrix이다.

* 위 자료를 보면 더 이해하기 쉬울 것이다. matrix L을 보면 lower trangular는 diagonal 위의 값들이 모두 0인 형태를 뜻한다는 것을 알 수 있다. 단, 우리가 살펴볼 문제에서는 L의 diagonal이 1인 경우만 다룰 것이다. diagonal이 1이 아닌 경우까지 살펴보려면 더 많은 내용을 다뤄야 한다.

* 첫 번째로는 row interchange와 scaling과정이 없는 LU factorization 살펴볼 것이다. 만약 row interchange와 scaling이 허용되면 더 많은 경우를 살펴봐야 하기 때문이다.

About Usefulness

* 그렇다면 이렇게 행렬 A를 LU로 분해하는 과정은 무엇을 위한 것일까? 바로 Ax=b의 방정식의 해 x를 구하기 위함이다. 아래 과정을 살펴보자.

$Ax=b$ 에서 $A를 LU라고 한다면$

$LUx = b$로 쓸 수 있다. 여기서 $Ux$를 $y$라고 한다면,

$Ly=b$가 된다. 이 방정식 $Ly=b$를 풀어 $y$를 먼저 구한다.

$U, y$를 알기 때문에 $Ux=y$를 풀 수 있게 되었다. 즉, 최초 $Ax=b$의 해 $x$를 구하게 된 것이다.

example)

* 한 가지 의문점이 생길 수 있다. A가 invertible하다면 A의 역행렬을 구해 해를 구하는 것이 더 간단하지 않은가? 굳이 LU로 분해해 방정식을 두 개를 풀어 x를 구한다는게 비효율적으로 느껴질 수도 있다.

* 하지만, L과 U의 형태를 보면 이 의문점이 해소될 것이다. L은 lower triangular form이고, U는 echelon form이기 때문에 upper trianglular form은 아니지만 유사한 형태를 띤다. 이는 계산량의 감소로 이어지는데, 컴퓨터로 계산시 다음과 같은 시간복잡도가 소요된다.

1) A의 역행렬을 통해 해 구하기

- $A^{-1}$를 구하는데 드는 시간 : $2n^3$

- $A^{-1} b$를 구하는데 드는 시간 : $2n^2$

2) LU factorization을 활용해 해 구하기

- $LU$ 로 분해하는데 드는 시간 : $2n^3 / 3$

- $Ly=b, Ux=y$ 방정식 푸는 시간 : $2n^2$

* 물론 시간복잡도가 매우 줄어드는 것은 아니다. 하지만, 경우에 따라 이 시간복잡도는 차이가 발생하는데, 만약 A가 sparse하여 LU가 높은 확률로 sparse하고, 반면 $A^{-1}$는 dense일 때 매우 유용하다. 실제로 A가 sparse한데, A의 역행렬이 dense한 경우도 종종 있다.

LU Factorization Algorithm

Low Interchange, Scaling 없는 Case

* 자 그럼, LU factorization이 어떤 용도로 사용되는지 배웠으니 알고리즘에 대해 배워보자. 먼저 A를 LU로 분해하는 법이다.

* E는 Elementary matrix를 의미한다. Elementary matrix E를 A에 계속 곱해서 row reduction의 forward phase와 같이 echelon form U를 생성한다. 단, 이 때 row replacement를 통해서만 elementary matrix를 구성한다. scaling이나 row interchange는 안된다.

* Elementary matrix는 invertible하고, Elementary matrix들의 곱 $(E_p ... E_1)$ 또한 invertible하다. 때문에 역행렬 $(E_p ... E_1)^{-1}$를 양변에 곱한다. 이 때 역행렬 $(E_p ... E_1)^{-1}$는 L에 해당한다.

* row replacement를 통해서만 elementary matrix를 구성하면, elementary matrix들은 lower triangular form이 된다. lower triangular form들의 곱은 lower triangular form이고, inverse matrix $E_p^{-1}$의 곱들도 lower triangular form이다.

example)

* 먼저 A의 echelon form을 생성해보자.

* A에 취해줬던 연산을 반대로 Identity matrix에 취해서 L을 생성하면 다음과 같다.

* 여기서 재미있는 성질이 하나 있는데, A를 echelon form으로 만드는 과정에서 각 row의 pivot poistion 아래의 entry들의 값을 파랑색으로 표시해 놓았는데, 이를 모아 matrix로 구성하면 아래와 같다.

* 4x4 matrix이고 빈 값은 모두 0이라고 생각해보자. 만약 pivot position의 값들을 모두 1로 scaling해주면 아래와 같은 결과가 나온다.

* 이 matrix는 우리가 앞서 구했던 matrix L과 동일한 matrix이다. 실제로 이 과정을 통해 L matrix를 손쉽게 구해낼 수 있다.

General Case

* 지금까지 우리가 봤던 LU factorization은 row reduction과정을 통해 U를 도출할 때 scaling과 interchange가 필요 없었다(정확히 말하면 필요 없는 case만 배웠다). 하지만, 일반적으로는 scaling과 interchange가 필요한 경우가 더 많다. 아래 예제를 살펴보자.

 

$ A = \begin{bmatrix} 0 & 0 & 1 & -3 & 2 \\ 2 & -1 & 4 & 2 & 1 \\ 4 & -1 & 9 & 1 & 4 \\ 2 & -1 & 5 & -1 & 5 \end{bmatrix}$

 

* 첫 번째 row의 첫 번째 entry를 pivot position으로 만들기 위해 interchange를 해야 한다.

* 이렇게 interchange와 같은 소요가 있을 때 식은 LU factorization 식은 다음과 같이 쓸 수 있다.

 

$PA=LU$

 

* P는 permutation matrix로 필요에 의해 I matrix에서 행이 뒤바뀐 상태인 matrix이다. permutation matrix의 inverse matrix는 transpose로 간단하게 구할 수 있다.