Ответ 1
Наиболее распространенными являются хранилище CSC или CSR. Они эффективны для умножения матричных векторов. Также очень легко закодировать эти процедуры умножения, если вам нужно сделать это самостоятельно.
Тем не менее, хранение Йельского университета также дает очень эффективный множитель матрицы-вектора. Если вы выполняете поиск элементов матрицы, вы неправильно поняли, как использовать формат. Я предлагаю вам изучить некоторые из стандартных разреженных библиотек, чтобы узнать, как реализовано преобразование матриц-векторов.
Даже с вашим текущим хранилищем вы можете выполнять умножение матрицы в O (n) сложности. Все разреженные алгоритмы умножения матрицы-вектора, которые я когда-либо видел, сводятся к тем же самым шагам. Например, рассмотрим y = Ax.
- Zeroise вектор результата, y.
- Инициализировать итератор для ненулевых элементов матрицы, A.
- Получить следующий ненулевой элемент матрицы, A [i, j]. Заметим, что шаблон i, j не соответствует регулярному шаблону. Он просто отражает порядок, в котором хранятся ненулевые элементы A.
- y [i] + = A [i, j] * x [j]
- Если есть больше элементов из A, goto 3.
Я подозреваю, что вы пишете классический двойной код для плотного кода цикла:
for (i=0; i<N; i++)
for (j=0; j<N; j++)
y[i] += A[i,j]*x[j]
и что побуждает вас выполнять поиск.
Но я не предлагаю, чтобы вы придерживались своего хранилища std::map. Это не будет суперэффективно. Я бы рекомендовал CSC главным образом потому, что он наиболее широко используется.