Матрицы

Матрица представляет собой прямоугольный массив чисел.

`A=((1,2,3),(4,5,6))`

является матрицей размера `2 xx 3`. Элемент на пересечении `i`-й строки и `j`-ro столбца матрицы – `a_{ij}`.

Нулевая матрица – это матрица, все элементы которой равны 0.

1. Многомерный массив: double A[2][3]={{0}};
2. Одномерный массив: double A[6]={0}; // A[i*3+j]
3. Массив указателей на строки: double** A=new double*[2];
for(int i=0;i<2;++i) A[i]=new double[3]();
4. Вектор из векторов: vector<vector<double>> A(2,vector<double>(3,0));

Разрежённая матрица – матрица с преимущественно нулевыми элементами. В противном случае, если большая часть элементов матрицы ненулевая, матрица считается плотной.

Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако в разрежённых матрицах можно хранить и обрабатывать только ненулевые элементов, что снижает требования к памяти и позволяет использовать более эффективные алгоритмы.

1. Словарь по ключам: map<pair<int,int>, double> A;
2. Список списков: vector<list<pair<int,double>>> A;
3. Список координат: list<tuple<int,int,double>> A;
4. Сжатое хранение строкой (столбцом):

• массив значений vector<double> Anz, в котором хранятся ненулевые значения, из первой строки, затем из следующей и т. д.
• массив индексов столбцов vector<int> Acol, который хранит номера столбцов соответствующих элементов из массива значений.
• массив индексации строк vector<int> Arow(n+1), который хранит начальные индексы элементов строк в Anz и Acol.

Рекомендуется упорядочивать элементы в списках по возрастанию индексов, тогда операции над разрежёнными матрицами будут выполняться более эффективно по следующим причинам: 1) можно применить слияние двух упорядоченных последовательностей, работающее за линейное время; 2) результат слияния также упорядочен, поэтому можно добавлять значения в конец списка значений результирующей матрицы.