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.

stats(1)

Количество плотных или пустых строк проигнорировано colamd

stats(2)

Количество плотных или пустых столбцов проигнорировано colamd

stats(3)

Количество сборок мусора, выполняемых на внутренней структуре данных, используется colamd (примерно размера 2.2*nnz(S) + 4*m + 7*n целые числа

stats(4)

0 если матрица допустима, или 1 если недопустимый

stats(5)

Индекс крайнего правого столбца, который не отсортирован или содержит дублирующиеся записи или 0 если никакой такой столбец не существует

stats(6)

В последний раз замеченная дублирующаяся или неисправная строка индексирует в индексе столбца, данном stats(5), или 0 если никакой такой индекс строки не существует

stats(7)

Количество дублирующихся и неисправных индексов строки

Несмотря на то, что MATLAB® встроенные функции генерируют допустимые разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью MATLAB C или API Фортрана и передать его colamd. Поэтому colamd проверяет тот S isvalid:

  • Если индекс строки появляется два или больше раза в том же столбце, colamd игнорирует дублирующиеся записи, продолжает обрабатывать и предоставляет информацию о дублирующихся записях в stats(4:7).

  • Если индексы строки в столбце не работают, colamd виды каждый столбец его внутренней копии матричного S (но не восстанавливает входную матрицу S), продолжает обрабатывать и предоставляет информацию о неисправных записях в stats(4:7).

  • Если S недопустимо любым другим способом, colamd не может продолжиться. Это распечатывает сообщение об ошибке и не возвращает выходных аргументов (p или stats) .

Упорядоченное расположение сопровождается поступорядоченным расположением дерева устранения столбца.

Примеры

свернуть все

Набор Харуэлла-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)')

Figure contains 2 axes objects. Axes object 1 with title A contains an object of type line. Axes object 2 with title A(:,p) contains an object of type line.

Сравнение графика шпиона 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))')

Figure contains 2 axes objects. Axes object 1 with title lu(A) contains an object of type line. Axes object 2 with title lu(A(:,p)) contains an object of type line.

Ссылки

[1] Авторы кода для colamd Стефан Ай. Лэримор и Тимоти А. Дэвис. Алгоритм был разработан в сотрудничестве с Джоном Гильбертом, Xerox PARC, и Эсмондом Ыном, Окриджской национальной лабораторией. Исследование Алгоритмов Разреженной матрицы: https://people.engr.tamu.edu/davis/research.html

Расширенные возможности

Смотрите также

| | | |

Представлено до R2006a