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® генерируют допустимые разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью API MATLAB C или Фортрана и передать ее colamd. Поэтому colamd проверяет, что S допустим:
Если индекс строки появляется два или больше раза в том же столбце,
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