Main Content

dmperm

덜메이지-멘델슨 분해(Dulmage-Mendelsohn Decomposition)

구문

p = dmperm(A)
[p,q,r,s,cc,rr] = dmperm(A)

설명

p = dmperm(A)j열이 i행과 짝이 되면 p(j) = i이고 j열이 짝이 되지 않으면 p(j)=0인 벡터 p를 찾습니다. A가 정사각 행렬이고 그 구조적 랭크가 완전 랭크이면 p는 최대 매칭 행 치환이 되며 A(p,:)의 대각선에는 0이 없습니다. A의 구조적 랭크는 sprank(A) = sum(p>0)입니다.

[p,q,r,s,cc,rr] = dmperm(A)A의 덜메이지-멘델슨 분해(Dulmage-Mendelsohn Decomposition)를 구합니다. 여기서 A가 반드시 정사각 행렬이거나 그 구조적 랭크가 완전 랭크일 필요는 없습니다. pq는 각각 행 치환 벡터 및 열 치환 벡터로, A(p,q)는 블록 상부 삼각 형식이 됩니다. rs는 미세 분해(fine decomposition)의 블록 경계를 나타내는 인덱스 벡터입니다. ccrr은 성긴 분해(coarse decomposition)의 블록 경계를 나타내는, 길이가 5인 벡터입니다.

C = A(p,q)는 성긴 블록들로 구성된 4×4 집합으로 분할됩니다.

A11 A12 A13 A14
0    0  A23 A24
0    0   0  A34
0    0   0  A44
여기서 A12, A23, A34는 0이 없는 대각선을 가진 정사각 행렬입니다. A11의 열은 짝이 없는 열이고 A44의 행은 짝이 없는 행입니다. 이러한 블록은 어느 것이든 빈 행렬일 수 있습니다. 성긴 분해에서 (i,j)th 블록은 C(rr(i):rr(i+1)-1,cc(j):cc(j+1)-1)입니다. A가 정사각 행렬이고 구조적으로 정칙 행렬이면 A23 = C입니다. 즉, 다른 모든 성긴 블록은 0×0입니다.

선형 시스템의 경우 다음이 성립합니다.

  • [A11 A12]는 시스템의 부족 결정(underdetermined) 부분으로, 항상 행보다 열이 많은 직사각 행렬이거나 0×0 행렬입니다.

  • A23은 시스템의 적정 결정(well-determined) 부분으로, 항상 정사각 행렬입니다. A23 부분행렬은 미세 분해를 통해 블록 상부 삼각 형식(A23의 강한 연결성분)으로 더 나누어집니다.

  • [A34; A44]는 시스템의 과결정(overdetermined) 부분으로, 항상 열보다 행이 많은 직사각 행렬이거나 0×0 행렬입니다.

A의 구조적 랭크는 sprank(A) = rr(4)-1이며, 이는 A의 수치적 랭크 상한입니다. 산술적으로 엄밀하게는 확률 1의 sprank(A) = rank(full(sprand(A)))입니다.

C(r(i):r(i+1)-1,s(j):s(j+1)-1)은 미세 분해의 (i,j)번째 블록입니다. (1,1) 블록은 그 블록이 0×0이 아닌 경우 직사각형 블록 [A11 A12]가 됩니다. (b,b) 블록은 그 블록이 0×0이 아닌 경우 직사각형 블록 [A34 ; A44]가 됩니다. 여기서 b = length(r)-1입니다. C(r(i):r(i+1)-1,s(i):s(i+1)-1) 형식의 다른 블록은 모두 A23의 대각선 블록이고 정사각 행렬이며 0이 없는 대각선을 갖습니다.

  • A가 가약 행렬인 경우 선형 시스템 Ax = b를 풀 때는 기약 대각선 블록을 사용해 블록 상부 삼각 형식으로 A를 치환한 다음 블록 역대입을 수행하여 문제를 풀 수 있습니다. 치환된 행렬의 대각선 블록만 분해가 필요하며, 따라서 대각선 위쪽 블록에서 채우기 및 대수적 연산을 수행할 필요가 없어집니다.

  • 그래프 이론의 관점에서 볼 때, dmpermA의 이분 그래프에서 최대 크기의 매칭을 구하며 A(p,q)의 대각선 블록은 해당 그래프의 강한 Hall 성분에 대응됩니다. dmperm의 출력값은 유방향 그래프나 무방향 그래프에서 연결성분 또는 강한 연결성분을 찾을 때에도 사용할 수 있습니다. 자세한 내용은 Pothen and Fan [1]을 참조하십시오.

참고 문헌

[1] Pothen, Alex and Chin-Ju Fan “Computing the Block Triangular Form of a Sparse Matrix” ACM Transactions on Mathematical Software Vol 16, No. 4 Dec. 1990, pp. 303-324.

[2] Davis, Timothy A. Direct Methods for Sparse Linear Systems. SIAM Series on the Fundamentals of Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2006.

확장 기능

버전 내역

R2006a 이전에 개발됨

참고 항목

|