Разложение Дулмаге-Мендельсона
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). Для линейной системы,
[A11 A12] является недоопределенной частью системы — это является всегда прямоугольным и с большим количеством столбцов и строк или 0-by-0,
A23 является хорошо определенной частью системы — это является всегда квадратным, и
[A34 ; A44] является сверхрешительной частью системы — это является всегда прямоугольным с большим количеством строк, чем столбцы или 0-by-0.
Структурным рангом A является sprank(A) = rr(4)-1, который является верхней границей на числовом ранге A. sprank(A) = rank(full(sprand(A))) с вероятностью 1 в точной арифметике.
Субматрица A23 далее подразделена на блок верхняя треугольная форма через прекрасное разложение (строго связанные компоненты A23). Если A является квадратным и структурно несингулярным, A23 является целой матрицей.
C(r(i):r(i+1)-1,s(j):s(j+1)-1) является (i,j) th блок прекрасного разложения. Блок (1,1) является прямоугольным блоком [A11 A12], если этим блоком не является 0-by-0. Блок (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 к блоку верхняя треугольная форма с неприводимыми диагональными блоками, и затем выполнения блока backsubstitution. Только диагональные блоки переставленной матричной потребности, которая будет учтена, сохраняя заливку и арифметику в блоках выше диагонали.
В графике теоретические условия dmperm находит максимальный размер, соответствующий в биграфе A, и диагональные блоки A(p,q) соответствуют сильным компонентам Холла того графика. Вывод dmperm может также использоваться, чтобы найти связанные или строго связанные компоненты неориентированного или ориентированного графа. Для получения дополнительной информации смотрите Потэна и Фэна [1].
[1] Pothen, Алекс и Поклонник Чинджу “Вычисление Блока Треугольная Форма Разреженной матрицы” Транзакции ACM на Математическом программном обеспечении Vol 16, декабрь 1990 № 4, стр 303-324.