Когда я должен использовать "разреженный"?

Я просматривал документацию Matlab sparse, пытаясь найти, существуют ли какие-либо рекомендации, когда имеет смысл использовать разреженное представление, а не полное представление.

Например, у меня есть матрица data с около 30% ненулевыми элементами. Я могу проверить используемую память.

whos data
  Name             Size                 Bytes  Class     Attributes

  data      84143929x11            4394073488  double    sparse

data = full(data);
whos data
  Name             Size                 Bytes  Class     Attributes

  data      84143929x11            7404665752  double

Здесь я четко сохраняю память, но это будет верно для любой матрицы с 30% ненулевыми элементами? Что относительно 50% отличных от нуля записей? Есть ли правило большого пальца, на какой процент я должен переключиться на полную матрицу?

Как насчет вычислительного? Как правило, медленнее или быстрее выполнять матричное умножение с разреженной матрицей? Операции с разреженной матрицей говорит, что

Вычислительная сложность разреженных операций пропорциональна nnz, число ненулевых элементов в матрице. вычислительный сложность также линейно зависит от размера строки m и размера столбца n матрицы, но не зависит от произведения m * n, то общее число нулевых и ненулевых элементов.

Это трудно сравнить с полной матрицей, не зная подробностей.

Библиотека Scipy sparse matrix объясняет преимущества и недостатки каждого разреженного формата. Например, для csc_matrix

Преимущества формата CSC

эффективные арифметические операции CSC + CSC, CSC * CSC и т.д.

эффективная сортировка столбцов

быстрые матричные векторные продукты (CSR, BSR может быть быстрее)
Недостатки формата CSC

медленные операции резки строк (рассмотрим CSR)

изменения структуры разреженности дороги (рассмотрим LIL или DOK)

Существует ли подобная информация о реализации Matlab sparse? Если да, то где я могу его найти?

Ответ 1

Многие операции над полными матрицами используют вызовы библиотеки BLAS/LAPACK, которые безумно оптимизированы и жестко бить. На практике операции с разреженными матрицами будут только превосходить операции на полных матрицах в специализированных ситуациях, которые могут в достаточной степени использовать (i) разреженность и (ii) специальную матричную структуру.

Просто случайное использование разреженных вероятно сделает вас хуже. Пример: что быстрее, добавив полную матрицу 10000x10000 к полной матрице 10000x10000? Или добавление полной матрицы 10000x10000 к полностью разреженной (т.е. Все нулевой) матрице 10000x10000? попробуй! В моей системе полный + полный быстрее!

Какие примеры ситуаций, когда разреженные CRUSHES полны?

Пример 1: решение линейной системы A * x = b, где A - 5000x5000, но является блочной диагональной матрицей, построенной из 500 5x5 блоков. Код установки:

As = sparse(rand(5, 5));
for(i=1:999)
   As = blkdiag(As, sparse(rand(5,5))); 
end;                         %As is made up of 500 5x5 blocks along diagonal
Af = full(As); b = rand(5000, 1);

Затем вы можете проверить разницу в скорости:

As \ b % operation on sparse As takes .0012 seconds
Af \ b % solving with full Af takes about 2.3 seconds

В общем, линейная система с переменной величиной 5000 несколько сложна, но 1000 отдельных 5 переменных линейных систем тривиальны. Последнее, в основном, решается в разреженном случае.

Общая история заключается в том, что, если у вас есть специальная матричная структура и умело использовать разреженность, можно решить безумно большие проблемы, которые в противном случае были бы трудноразрешимыми. Если у вас есть достаточно большая специализированная проблема, у нас есть достаточно разреженная матрица и умная с линейной алгеброй (чтобы сохранить разреженность), разреженная типизированная матрица может быть чрезвычайно мощной.

С другой стороны, случайное бросание разреженных без глубокой осторожной мысли почти наверняка сделает ваш код медленнее.

Ответ 2

Я не эксперт в использовании матриц sparse, однако у Mathworks есть некоторая документация, относящаяся к эффективности работы и вычислению.

Описание сложности вычислений:

Вычислительная сложность разреженных операций пропорциональна nnz, число ненулевых элементов в матрице. вычислительный сложность также линейно зависит от размера строки m и размера столбца n матрицы, но не зависит от произведения m * n, то общее число нулевых и ненулевых элементов.

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

Не скучая по алгоритмическим данным, другой ответ предполагает, что вам не следует беспокоиться о разреженных массивах, которые являются всего лишь 25% не нулями. Они предлагают вам некоторый код для тестирования. Подробнее см. В их сообщении.

A = sprand(2000,2000,0.25);
tic,B = A*A;toc
Elapsed time is 1.771668 seconds.

Af = full(A);
tic,B = Af*Af;toc
Elapsed time is 0.499045 seconds.

Ответ 3

Если у вас есть матрица фиксированного измерения, то лучший способ установить надежный ответ - это просто пробная версия и ошибка. Однако, если вы не знаете размеры ваших матриц/векторов, тогда эмпирические правила:

Ваши разреженные векторы должны иметь эффективное количество ненулевых записей

которое для матриц будет означать

Редкая матрица N x N должна иметь <= c * N ненулевые записи, где c является константой "намного меньше", чем N.

Давайте дать псевдотеоретическое объяснение этому правилу. Будем рассматривать довольно легкую задачу создания скалярного (или точечного) произведения двух векторов с двойными координатами. Теперь, если у вас есть два плотных вектора одинаковой длины N, ваш код будет выглядеть как

//define vectors vector, wector as double arrays of length N 
double sum = 0;
for (int i = 0; i < N; i++)
{
    sum += vector[i] * wector[i];
}

это количество в дополнениях N, умножения N и N условные ветки (операции цикла). Самой дорогостоящей операцией здесь является условная ветвь, такая дорогостоящая, что мы можем пренебрегать умножениями и тем более добавлениями. Причина, по которой это так дорого, объясняется в ответе на этот вопрос.

UPD: Фактически, в цикле for вы рискуете выбрать неправильную ветвь только один раз, в конце вашего цикла, так как по определению выбранная по умолчанию ветка будет идти в цикле. Это составляет не более 1 перезапуска трубопровода для работы скалярного продукта.

Теперь рассмотрим, как разреженные векторы реализуются в BLAS. Там каждый вектор кодируется двумя массивами: одним из значений и одним из соответствующих индексов, что-то вроде

1.7    -0.8    3.6
171     83     215

(плюс одно целое число, указывающее предполагаемую длину N). В документации BLAS указывается, что порядок индексов здесь не играет роли, поэтому данные

-0.8    3.6    1.7
 83     215    171

кодирует один и тот же вектор. Это замечание дает достаточно информации для восстановления алгоритма для скалярного произведения. Учитывая два разреженных вектора, закодированных данными int[] indices, double[] values и int[] jndices, double[] walues, вычислить их скалярное произведение в строках этого "кода":

double sum = 0;
for (int i = 0; i < indices.length; i++)
{
    for (int j = 0; j < jndices.length; j++)
    {
        if(indices[i] == jndices[j])
        {
            sum += values[indices[i]] * walues[jndices[j]];
        }
    }
}

что дает нам общее количество условных ветвей indices.length * jndices.length * 2 + indices.length. Это означает, что для того, чтобы справиться с плотным алгоритмом, ваши векторы должны иметь не более sqrt(N) ненулевые записи. Дело здесь в том, что зависимость от N уже нелинейна, поэтому нет смысла спрашивать, нужно ли вам заполнять 1% или 10% или 25%. 10% идеально подходит для векторов длиной 10, все еще вроде ОК для длины 50 и уже общей руины для длины 100.

UPD. В этом фрагменте кода у вас есть ветвь if, а вероятность ошибочного пути - 50%. Таким образом, скалярное произведение двух разреженных векторов будет составлять примерно в 0,5-1 раза среднее число ненулевых записей на разреженный вектор), перезапуск в зависимости от того, насколько разрежены ваши векторы. Цифры должны быть скорректированы: в инструкции if без else сначала будет выполняться кратчайшая инструкция, которая "ничего не делает" , но все же.

Заметим, что наиболее эффективная операция представляет собой скалярное произведение разреженного и плотного вектора. Учитывая разреженный вектор indices и values и плотный вектор dense, ваш код будет выглядеть как

double sum = 0;
for (int i = 0; i < indices.length; i++)
{
    sum += values[indices[i]] * dense[indices[i]];
}

то есть. у вас будут indices.length условные ветки, что хорошо.

UPD. Еще раз, я уверен, у вас будет не более одного перезапуска для каждой операции. Обратите также внимание на то, что afaik в современных многоядерных процессорах обе альтернативы выполняются параллельно на двух разных ядрах, так что в альтернативных ветвях вам нужно только подождать, пока не будет завершен самый длинный.

Теперь, когда вы умножаете матрицу с вектором, вы в основном занимаете #rows скалярные произведения векторов. Умножая матрицу с матричными суммами при взятии # ((ненулевых) столбцов во второй матрице) матрицы посредством векторных умножений. Вы можете сами оценить сложность.

И вот здесь начинается всякая ~~черная магия~~ глубокая теория разного хранения матриц. Вы можете хранить свою разреженную матрицу как плотный массив разреженных строк, как разреженный массив плотных строк или разреженный массив разреженных строк. То же самое касается столбцов. Все смешные аббревиатуры от Scipy, упомянутые в вопросе, связаны с этим.

"У вас всегда будет преимущество в скорости, если вы умножаете матрицу, построенную из разреженных строк с плотной матрицей, или на матрицу из плотных столбцов. Возможно, вам захочется сохранить ваши разреженные данные матрицы как плотные векторы диагоналей, поэтому в случае свертки нейронных сетей - и тогда вам понадобится совершенно разные алгоритмы. Вы можете сделать свою матрицу блочной матрицей - так же, как и BLAS, и получить разумный импульс вычисления. Возможно, вам захочется сохранить ваши данные в виде двух матриц - например, диагональных и разреженных, что справедливо для метода конечных элементов. Вы можете использовать разреженность для общих нейронных сетей (например, ускоренную перемотку вперед, экстремальный учебный компьютер или сеть состояний эха), если вы всегда умножаете матрицу, сохраненную в строке, на вектор столбца, но избегайте умножения матриц. И вы будете" всегда" получать преимущество, используя разреженные матрицы, если будете следовать правилу большого пальца - оно выполняется для сетей конечных элементов и сверток, но не выполняется для коллективных вычислений.