colamd
Столбец аппроксимированное минимальное сочетание степени
Синтаксис
p = colamd(S)
Описание
p = colamd(S) возвращается столбец аппроксимируют минимальный вектор сочетания степени для разреженной матрицы S. Для несимметрической матрицы S, S(:,p) имеет тенденцию иметь более разреженные факторы LU, чем 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.
| Количество плотных или пустых строк проигнорировано |
| Количество плотных или пустых столбцов проигнорировано |
| Количество сборок мусора, выполняемых на внутренней структуре данных, используется |
| 0 |
| Индекс крайнего правого столбца, который не отсортирован или содержит дублирующиеся записи или |
| В последний раз замеченная дублирующаяся или неисправная строка индексирует в индексе столбца, данном |
| Количество дублирующихся и неисправных индексов строки |
Несмотря на то, что встроенные функции MATLAB® генерируют допустимые разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью API MATLAB C или Фортрана и передать ее colamd. Поэтому colamd проверяет тот S isvalid:
Если индекс строки появляется два или больше раза в том же столбце,
colamdигнорирует дублирующиеся записи, продолжает обрабатывать и предоставляет информацию о дублирующихся записях вstats(4:7).Если индексы строки в столбце не работают,
colamdвиды каждый столбец его внутренней копии матричногоS(но не восстанавливает входную матрицуS), продолжает обрабатывать и предоставляет информацию о неисправных записях вstats(4:7).Если
Sнедопустимо любым другим способом,colamdне может продолжиться. Это распечатывает сообщение об ошибке и не возвращает выходных аргументов (pилиstats) .
Упорядоченное расположение сопровождается поступорядоченным расположением дерева устранения столбца.
Примеры
Сравнение разреженной матрицы и LU-факторизации
Набор Харуэлла-Boeing разреженных матриц и директории демонстраций MATLAB® включает тестовую матрицу west0479. Это - матрица порядка 479, следующего из модели из-за Westerberg восьмиэтапного химического столбца дистилляции. График шпиона приводит доказательство восьми этапов. 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 Стефан Ай. Лэримор и Тимоти А. Дэвис. Алгоритм был разработан в сотрудничестве с Джоном Гильбертом, Xerox PARC, и Эсмондом Ыном, Окриджской национальной лабораторией. Исследование Алгоритмов Разреженной матрицы: http://faculty.cse.tamu.edu/davis/research.html