Разложение Дулмаге-Мендельсона
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 не должен быть квадратный или полный структурный ранг, находит разложение Дулмаге-Мендельсона AP и 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)блок th прекрасного разложения. (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 может также использоваться, чтобы найти связанные или строго связанные компоненты неориентированного или ориентированного графа. Для получения дополнительной информации смотрите Потэна и Фэна [1].
[1] Pothen, Алекс и Поклонник Чинджу “Вычисление Блока Треугольная Форма Разреженной матрицы” Транзакции ACM на Mathematical Software Vol 16, декабрь 1990 № 4, стр 303-324.