Декомпозиция Дульмажа - Мендельсона
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около-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около-0.Для линейной системы:
[A11 A12] является неопределенной частью системы - она всегда прямоугольная и содержит больше столбцов, чем строк, или 0около-0.
A23 является хорошо определенной частью системы - она всегда квадратная. A23 субматрица далее подразделяется на блок верхней треугольной формы через тонкое разложение (сильно связанные компоненты A23).
[A34; A44] является переопределенной частью системы - она всегда прямоугольная с большим количеством строк, чем столбцы, или 0около-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)третий блок мелкого разложения. (1,1) блок - прямоугольный блок [A11 A12], если этот блок не является 0около-0. (b,b) блок - прямоугольный блок [A34 ; A44], если этот блок не является 0около-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] Потен, Алекс и Чин-Джу Фан «Вычисление блочной треугольной формы разреженной матрицы» Транзакции ACM по математическому программному обеспечению Том 16, № 4 декабря 1990, стр. 303-324.