Если у вас есть матрица фиксированного размера, лучший способ получить надежный ответ - это просто метод проб и ошибок. Однако, если вы не знаете размеров своих матриц / векторов, то практические правила таковы:
Ваши разреженные векторы должны иметь эффективное постоянное количество ненулевых записей
что для матриц будет означать
Ваша 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 - и получить разумный прирост вычислений. Вы можете сохранить свои данные в виде двух матриц - скажем, диагональной и разреженной, как в случае метод конечных элементов. Вы можете использовать разреженность для общих нейронных сетей (например, ускоренную перемотку вперед, экстремальную обучающую машину или сеть состояний эха), если вы всегда умножаете сохраненную матрицу строки на вектор-столбец, но избегаете умножения матрицы. И вы «всегда» получите преимущество, используя разреженные матрицы, если будете следовать практическому правилу - оно справедливо для конечно-элементных и сверточных сетей, но не работает для резервуарных вычислений.
person
Kolya Ivankov
schedule
07.12.2017
