LU 분해로 DETERMINANT 구하기

행렬연산에서 표준적으로 쓰이는 라이브러리는 BLAS와 LAPACK입니다. BLAS는 행렬의 덧셈, 곱셈 등 기본적인 연산에 관한 라이브러리이고, LAPACK은 행렬의 분해나 역행렬 등을 구하는 좀 더 상위의 연산에 대한 라이브러리 입니다. 하지만 LAPACK에는 DETERMINANT 를 구해주는 함수가 없어서 유저가 만들어 주거나 다른 라이브러리를 참고해서 만들어야 합니다. 이 글에서는 LAPACK을 이용하여 DETERMINANT 를 구하는 방법을 다룹니다. 먼저 행렬 A를 LU 분해를 하면 다음과 같이 분해됩니다.


A = P * L * U

여기에서 L 은 하삼각행렬이며, 대각성분은 모두 1입니다. U는 상삼각행렬을 나타내며, P 는 PERMUTATION 행렬입니다. PERMUTATION 행렬은 곱해줬을때, 행을 바꿔주는 작용을 해줍니다. 그러므로 I 행렬에서 바꿔주고 싶은 행들에 맞게 행들을 바꿔준 모양입니다. DETERMINANT 성질에 의해서 PERMUTATION 행렬은 1 또는 -1 입니다. 짝수번을 바꿔줬다면 1 홀수번을 바꿔줬다면 -1 입니다. 이점을 고려하면 A의 DETERMINANT 는 다음과 같습니다.

det(A) = det(P) * det(U) = sign(P) * det(U)

위 사실을 이용해서 LU분해로 DETERMINANT 를 구할 수 있습니다. 먼저 LAPACK포트란에서 LU 분해는 다음과 같습니다.

    ! LU decomposition
    M = DIM
    N = DIM
    LDA = DIM
    ALLOCATE(IPIV(DIM))
    CALL DGETRF(M, N, A, LDA, IPIV, INFO)

A는 입력과 동시에 출력값을 주는데, 대각선을 기준으로 위쪽은 U 행렬을 아래쪽은 L 행렬을 나타냅니다. 당연히 대각선 부분은 U 의 원소를 나타냅니다. 또한 IPIV에 PERMUTATION 행렬의 정보가 저장되어 있는데요. LU 분해를 하는 동안 바뀌어진 행을 나타냅니다. 그러므로 PERMUTATION 횟수는 다음과 같습니다.

  {PERMUTATION 횟수} = {IPIV[i] /= i 횟수}

그러므로 P 행렬의 DETERMINANT 는 다음과 같이 구해줄 수 있습니다.

 detP = 1.0d0
 do i=1, DIM
        if (IPIV[i] /=i) then
            detP = detP * -1d0
        end if
  end do

여기에 U는 상삼각행렬이므로 U의 대각성분들을 곱해주면 DETERMINANT 를 구해줄 수 있습니다. 이 방법 이외에도 QR 분해나 SVD를 이용하여서도 구할 수 있습니다. 속도는 LU가 가장 빠릅니다. 마지막으로 LU분해를 이용하여 행렬방정식을 풀어주는 DGESV도 동일한 방식으로 DETERMINANT 를 구할 수 있습니다.