Известно, что матрица порядка n требует для своего хранения n² байт оперативной памяти, а время вычислений пропорционально n³. Поэтому, когда количество неизвестных переменных достигает нескольких сотен, вычисления с полными матрицами становятся неэффективными и необходимо принимать во внимание степень разреженности матрицы, то есть отношение количества ненулевых элементов к общему количеству элементов матрицы.

Для разреженной матрицы S порядка m х n с количеством ненулевых элементов nnz(S) требования к объему оперативной памяти пропорциональны nnz. Вычислительная сложность операций над элементами массива также пропорциональна nnz, линейно зависит от m и n и не зависит от произведения m х n. Сложность такой операции как решение системы линейных уравнений с разреженной матрицей зависит от упорядочения элементов и заполненности матрицы, что обсуждается позднее в этой главе.

При работе с разреженными матрицами соблюдается фундаментальный принцип вычислительной сложности: время, необходимое для выполнения матричных операций над разреженной матрицей, пропорционально количеству арифметических операций над ненулевыми элементами. Это подтверждает широко распространенное правило: время вычислений пропорционально количеству операций с плавающей точкой.

В этой главе описан новый класс операций, реализованных в системе MATLAB, для работы с разреженными матрицами. Это операции хранения, преобразования, упорядочения, графического представления и решения систем линейных уравнений.

Элементарные разреженные матрицы

• SPARSE - формирование разреженной матрицы
• SPDIAGS - формирование диагоналей разреженной матрицы
• SPEYE - единичная разреженная матрица
• SPRANDN - случайная разреженная матрица
• SPRANDSYM - случайная разреженная симметрическая матрица

Преобразование разреженных матриц

• FIND - определение индексов ненулевых элементов
• FULL - преобразование разреженной матрицы в полную
• SPCONVERT - преобразование данных в ASCII-формате в массив разреженной структуры

Работа с ненулевыми элементами

• ISSPARSE - проверка на принадлежность к классу разреженных матриц
• NNZ - количество ненулевых элементов
• NONZEROS - формирование вектора ненулевых элементов
• NZMAX - количество ячеек памяти для размещения ненулевых элементов
• SPALLOC - выделить пространство памяти для разреженной матрицы
• SPFUN - вычисление функции только для ненулевых элементов
• SPONES - формирование матрицы связности

Характеристики разреженной системы

• NORMEST - оценка 2-нормы разреженной матрицы
• CONDEST - оценка числа обусловленности матрицы по 1-норме
• SPRANK - структурный ранг разреженной матрицы

Визуализация разреженных матриц

• GPLOT - построение графа
• SPY - визуализировать структуру разреженной матрицы

Алгоритмы упорядочения

• RANDPERM - формирование случайных перестановок
• COLPERM - упорядочение столбцов с учетом их разреженности
• DMPERM - DM-декомпозиция разреженной матрицы
• SYMRCM - RCM-упорядоченность
• COLMMD - упорядочение по разреженности столбцов
• SYMMMD - симметрическая упорядоченность

Операции над деревьями

• ETREE - дерево матрицы
• ETREEPLOT - построение дерева матрицы
• TREELAYOUT - разметить дерево
• TREEPLOT - пострение дерева матрицы

Вспомогательные операции

• SPPARMS - установка параметров для алгоритмов упорядочения и прямого решения линейных уравнений для разреженных матриц
• SYMBFACT - характеристики разложения Холецкого
• SPAUGMENT - формирование расширенной матрицы для метода наименьших квадратов