MATLAB.Exponenta
–Û·Ë͇ Matlab&Toolboxes

MATLAB\MATLAB

В.Г.Потемкин "Справочник по MATLAB"
Работа с разреженными матрицами

  В оглавление книги \ К следующему разделу \ К предыдущему разделу

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

Известно, что матрица порядка 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 - симметрическая упорядоченность

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

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

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

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

  В оглавление книги \ К следующему разделу \ К предыдущему разделу

 


Поиск по сайту:

Система Orphus

Яндекс.Метрика