|
При решении многих прикладных задач приходится иметь дело с разреженными матрицами, то есть с матрицами, имеющими много нулевых элементов. К числу таких задач в первую очередь следует отнести граничные задачи для систем дифференциальных уравнений в частных производных. Возникающие при этом модели - это, как правило, квадратные матрицы высокого порядка с конечным числом ненулевых диагоналей.
Известно, что матрица порядка n требует для своего хранения n2 байт оперативной памяти, а время вычислений пропорционально n3. Поэтому, когда количество неизвестных переменных достигает нескольких сотен, вычисления с полными матрицами становятся неэффективными и необходимо принимать во внимание степень разреженности матрицы, то есть отношение количества ненулевых элементов к общему количеству элементов матрицы.
Для разреженной матрицы 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 - симметрическая упорядоченность
Операции над деревьями
Вспомогательные операции
- SPPARMS - установка параметров для алгоритмов упорядочения и прямого решения линейных уравнений для разреженных матриц
- SYMBFACT - характеристики разложения Холецкого
- SPAUGMENT - формирование расширенной матрицы для метода наименьших квадратов
  
|
