Столбец аппроксимация минимальной степени перестановки
p = colamd(S)
p = colamd(S) возвращает вектор аппроксимации минимальной степени перестановки для разреженной матрицы S. Для несимметричной матрицы S, S(:,p) имеет тенденцию иметь более скудные факторы логической единицы, чем S. Чолеская факторизация S(:,p)' * S(:,p) также имеет тенденцию быть скуднее, чем у S'*S.
knobs является двухэлементным вектором. Если S является mоколо-n, то строки с более чем (knobs(1))*n записи игнорируются. Столбцы с более чем (knobs(2))*m записи удаляются до упорядочения и упорядочиваются последними в выходной перестановке p. Если knobs параметр отсутствует, то knobs(1) = knobs(2) = spparms('wh_frac').
stats является необязательным вектором, который предоставляет данные о порядке и достоверности матрицы S.
| Количество плотных или пустых строк, игнорируемых |
| Количество плотных или пустых столбцов, игнорируемых |
| Количество сборщиков мусора, выполненных во внутренней структуре данных, используемой |
|
|
| Индекс крайнего правого столбца, который не отсортирован или содержит повторяющиеся записи, или |
| Последний раз индекс повторяющейся или неупорядоченной строки в индексе столбца, заданном |
| Количество повторяющихся и неупорядоченных индексов строк |
Хотя встроенные функции MATLAB ® генерируют допустимые разреженные матрицы, пользователь может создать недопустимую разреженную матрицу, используя API MATLAB C или Fortran, и передать ее colamd. По этой причине colamd проверяет, что S является действительным:
Если индекс строки отображается в одном столбце два или более раз, colamd игнорирует повторяющиеся записи, продолжает обработку и предоставляет информацию о повторяющихся записях в stats(4:7).
Если индексы строк в столбце не соответствуют порядку, colamd сортировка каждого столбца внутренней копии матрицы S (но не восстанавливает входную матрицу S), продолжает обработку и предоставляет информацию о неупорядоченных записях в stats(4:7).
Если S недействителен любым другим способом, colamd продолжение невозможно. Он распечатывает сообщение об ошибке и не возвращает выходные аргументы (p или stats) .
За упорядочением следует последующее упорядочение дерева исключения столбцов.
Коллекция разреженных матриц Harwell-Boeing и каталог демонстраций MATLAB ® включают тестовую матрицуwest0479. Это матрица порядка 479, полученная из модели, полученной по Вестербергу из восьмиступенчатой химической дистилляционной колонны. Шпионский сюжет показывает доказательства восьми этапов. 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)')
Сравнение шпионского графика факторизации логической единицы исходной матрицы с таковым переупорядоченной матрицы показывает, что минимальная степень уменьшает время и требования к хранению лучше, чем в 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 Стефан И. Ларимор и Тимоти А. Дэвис. Алгоритм был разработан в сотрудничестве с Джоном Гилбертом, Xerox PARC, и Эсмондом Нгом, Национальной лабораторией Оук-Ридж. Исследования алгоритмов разреженных матриц: https://people.engr.tamu.edu/davis/research.html