colamd
Столбец аппроксимирует минимальную степень сочетания
Синтаксис
p = colamd(S)
Описание
p = colamd(S) возвращает столбец приблизительный вектор минимальной степени сочетания для разреженной матрицы S. Для несимметричной матрицы S, S(:,p) имеет тенденцию иметь более разреженные факторы LU, чем S. Область Факторизации Холесского S(:,p)' * S(:,p) также имеет тенденцию быть более разреженным, чем у S'*S.
knobs является двухэлементным вектором. Если S m-by- n, затем строки с более чем (knobs(1))*n записи игнорируются. Столбцы с более чем (knobs(2))*m записи удаляются до упорядоченного расположения и упорядочиваются последним в выход сочетания p. Если на knobs параметр отсутствует, тогда knobs(1) = knobs(2) = spparms('wh_frac').
stats является необязательным вектором, который предоставляет данные о упорядоченном расположении и валидности матрицы S.
| Количество плотных или пустых строк, проигнорированных |
| Количество плотных или пустых столбцов, проигнорированных |
| Количество наборов мусора, выполненных во внутренней структуре данных, используемой |
|
|
| Самый правый индекс столбца, который не сортирован или содержит повторяющиеся записи или |
| Последний просматриваемый повторяющийся или неупорядоченный индекс строки в индексе столбца, заданном |
| Количество повторяющихся и неупорядоченных индексов строк |
Хотя MATLAB® встроенные функции генерируют действительные разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью MATLAB C или Фортран APIs и передать ее в colamd. По этой причине, colamd проверяет, что S действителен:
Если индекс строки появляется в одном столбце два или более раз,
colamdигнорирует повторяющиеся записи, продолжает обработку и предоставляет информацию о повторяющихся записях вstats(4:7).Если индексы строк в столбце находятся вне порядка,
colamdсортирует каждый столбец своей внутренней копии матрицыS(но не восстанавливает входную матрицуS), продолжает обработку и предоставляет информацию о неупорядоченных записях вstats(4:7).Если
Sявляется недействительным любым другим способом,colamdневозможно продолжить. Оно печатает сообщение об ошибке и не возвращает выходных аргументов (pилиstats) .
За упорядоченное расположение следует дерево удаления столбцов после поступорядоченного расположения.
Примеры
Сравнение разреженной матрицы и LU-факторизации
Набор разреженных матриц Harwell-Boeing и директория демонстраций MATLAB ® включают тестовую матрицу west0479. Это матрица порядка 479, полученная из модели из-за Вестерберга восьмистадийного химического дистилляционного столбца. Шпионский график показывает доказательства восьми этапов. The colamd упорядочивание скремблирует эту структуру.
load west0479 A = west0479; p = colamd(A); figure() subplot(1,2,1), spy(A,4), title('A') subplot(1,2,2), spy(A(:,p),4), title('A(:,p)')
Сравнение шпионского графика LU-факторизации исходной матрицы с таковым у переупорядоченной матрицы показывает, что минимальная степень уменьшает время и требования к хранению лучше, чем коэффициент 2,8. Ненулевые счетчики 15918 и 5920 соответственно.
figure() subplot(1,2,1), spy(lu(A),4), title('lu(A)') subplot(1,2,2), spy(lu(A(:,p)),4), title('lu(A(:,p))')
Ссылки
[1] Авторы кода для colamd Стефан И. Ларимор и Тимоти А. Дэвис. Алгоритм был разработан в сотрудничестве с John Gilbert, Xerox PARC, и Esmond Ng, Oak Ridge National Laboratory. Разреженные матрицы: https://people.engr.tamu.edu/davis/research.html