Разложение Дулмаге-Мендельсона
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 является хорошо определенной частью системы — это является всегда квадратным. Субматрица 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) 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 на Mathematical Software Vol 16, декабрь 1990 № 4, стр 303-324.