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
가 반드시 정사각 행렬이거나 그 구조적 랭크가 완전 랭크일 필요는 없습니다. p
와 q
는 각각 행 치환 벡터 및 열 치환 벡터로, A(p,q)
는 블록 상부 삼각 형식이 됩니다. r
과 s
는 미세 분해(fine decomposition)의 블록 경계를 나타내는 인덱스 벡터입니다. cc
와 rr
은 성긴 분해(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
를 치환한 다음 블록 역대입을 수행하여 문제를 풀 수 있습니다. 치환된 행렬의 대각선 블록만 분해가 필요하며, 따라서 대각선 위쪽 블록에서 채우기 및 대수적 연산을 수행할 필요가 없어집니다.그래프 이론의 관점에서 볼 때,
dmperm
은A
의 이분 그래프에서 최대 크기의 매칭을 구하며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 이전에 개발됨