Декомпозиция Дюльмага-Мендельсона
p = dmperm(A)
[p,q,r,s,cc,rr] = dmperm(A)
p = dmperm(A) находит вектор p таким образом p(j) = i если столбец j соответствует строке i, или нуль, если столбец j не соответствует друг другу. Если A - квадратная матрица с полным структурным рангом, p является максимально совпадающим сочетанием строки и A(p,:) имеет нулевую диагональ. Структурный ранг A является sprank(A) = sum(p>0).
[p,q,r,s,cc,rr] = dmperm(A) где A не должен быть квадратным или полным структурным рангом, находит декомпозиция Дюльмага-Мендельсона A. p и q являются векторами сочетания строка и столбец, соответственно, такими, что A(p,q) имеет блок верхней треугольной формы. r и s являются векторами индекса, указывающими контуры блоков для мелкого разложения. cc и rr - векторы длины пять, указывающие контуры блоков грубого разложения.
C = A(p,q) разделяется на 4-by- 4 набор грубых блоков:
A11 A12 A13 A14 0 0 A23 A24 0 0 0 A34 0 0 0 A44
A12, A23, и A34 являются квадратными с безнулевыми диагоналями. Столбцы A11 являются несопоставленными столбцами и строками A44 являются несопоставленными строками. Любой из этих блоков может быть пустым. При грубом разложении (i,j)th блок C(rr(i):rr(i+1)-1,cc(j):cc(j+1)-1). Если A квадратная и структурно несингулярная, затем A23 = C. То есть все другие грубые блоки 0-by- 0.Для линейной системы:
[A11 A12] является недоопределенной частью системы - она всегда прямоугольная и с большим количеством столбцов, чем строки, или 0-by- 0.
A23 является четко определенной частью системы - она всегда квадратная. The A23 подматрица далее подразделяется на блок верхней треугольной формы посредством мелкого разложения (сильно соединенные компоненты A23).
[A34; A44] является переопределенной частью системы - она всегда прямоугольная с большим количеством строк, чем столбцы, или 0-by- 0.
Структурный ранг A является sprank(A) = rr(4)-1, которая является верхней границей численного ранга A. sprank(A) = rank(full(sprand(A))) с вероятностью 1 в точной арифметике.
C(r(i):r(i+1)-1,s(j):s(j+1)-1) является (i,j)I блок мелкого разложения. The (1,1) блок является прямоугольным блоком [A11 A12], если этот блок не 0-by- 0. The (b,b) блок является прямоугольным блоком [A34 ; A44], если этот блок не 0-by- 0, где b = length(r)-1. Все другие блоки формы C(r(i):r(i+1)-1,s(i):s(i+1)-1) являются диагональными блоками A23, и являются квадратными с безнулевой диагональю.
Если A является редуцируемой матрицей, линейная система Ax = b может быть решена путем перестановки A в верхнюю треугольную форму блока, с неприводимыми диагональными блоками, и затем выполняет обратную замену блока. Только диагональные блоки перестановочной матрицы должны быть фактурированы, сохраняя заливку и арифметику в блоках выше диагонали.
В теоретических терминах графа dmperm находит совпадение максимального размера в двудольном графике A, и диагональные блоки A(p,q) соответствуют сильным компонентам Холла этого графика. Область выхода dmperm может также использоваться, чтобы найти связанные или сильно связанные компоненты неориентированного или ориентированного графа. Для получения дополнительной информации смотрите Pothen and Fan [1].
[1] Pothen, Alex and Chin-Ju Fan «Вычисление Блока треугольная форма разреженной матрицы» ACM Transactions on Mathematical Software Vol 16, No4 Dec. 1990, pp. 303-324.