Каков наилучший способ определения числа ненулевых элементов при умножении на разреженные матрицы?

17

Мне было интересно, существует ли быстрый и эффективный способ заранее определить количество ненулевых элементов для операции умножения разреженных матриц при условии, что обе матрицы находятся в формате CSC или CSR.

Я знаю, что есть один в пакете smmp, но мне нужно что-то, что уже реализовано в C или C ++.

Любая помощь будет оценена. Заранее спасибо.

Recker
источник
у ваших матриц есть какая-либо симметрия или структура с расположением их ненулевых записей?
Годрик Провидец
@GodricSeer ... нет, я просто говорю об общих разреженных матрицах. У Matlab есть nnz (A), где A - метод разреженных матриц, чтобы узнать число ненулевых. Мне было интересно, существует ли такой метод.
Рекер
Лично я не могу придумать способ вычислить это число, которое было бы более низким порядком, чем просто умножение матрицы, без использования какой-либо симметрии или структуры. Я предполагаю, что вы хотите это для выделения памяти до выполнения умножения?
Годрик Провидец
Кроме того, я нашел эту статью, в которой описывается, как оценивать число на булевом матричном произведении (что идентично подсчету элементов в любом матричном произведении).
Годрик Провидец
@ GodricSeer .. Да, вы правы, мне нужно точное число только для распределения памяти в результирующей матрице. Хотя, спасибо за ссылку на бумагу. Это может заставить меня начать работать в каком-то направлении на некоторое время.
Рекер

Ответы:

14

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

Вольфганг Бангерт
источник
6
Это называется символическим умножением. Это не обязательно дешевле, чем числовое умножение, особенно в параллельном режиме, но это нужно делать только один раз в расчете на разреженность. Многие алгоритмы выполняют операцию несколько раз с разными числовыми значениями, но с одинаковым шаблоном разреженности, и в этом случае символическое умножение можно использовать повторно.
Джед Браун
Это хорошая идея, но, учитывая миллионы транзисторов, которые делают поплавок * плавающим параллельно, мы говорим только об экономии скорости на 50% или около этого здесь.
Евгений Сергеев
1
@ EvgeniSergeev - дело не в экономии вычислений, а в передаче памяти. Поскольку сегодня вы тратите 80% или больше времени на передачу памяти для умножения разреженных матриц, вы, вероятно, значительно выиграете, если вам не придется читать / записывать данные с плавающей запятой из / в память.
Вольфганг Бангерт
СмКО(мК)
О(мК)пмзнак равноКО(мпжурналп)О(м2)
13

Я фактически написал оригинальный код в Matlab для A * B, как A, так и B разреженный. Предварительное выделение места для результата было действительно интересной частью. Мы наблюдали, на что указывает Годрик - что знание числа ненулевых в AB столь же затратно, как и вычисление AB.

Первоначальную реализацию разреженного Matlab мы выполнили примерно в 1990 году, до публикации статьи Эдит Коэн, в которой был дан первый практичный и быстрый способ точной оценки размера AB. Мы собрали оценку меньшего размера, и если нам не хватило места в середине вычисления, удвоили распределение и скопировали частично вычисленный результат.

Я не знаю, что сейчас в Matlab.

Другая возможность - вычислять AB по одному столбцу за раз. Каждый столбец может быть временно сохранен в разреженном аккумуляторе (см. Разреженную статью Matlab для их объяснения), и место, выделенное для хранения точно известного размера столбца результата. Результат будет представлен в виде разбросанных сжатых разреженных столбцов - каждый столбец в CSC, но без смежности между столбцами - с использованием 2 векторов длинных чисел (начало столбца, длина столбца), а не один, в качестве метаданных. Это форма хранения, которая может стоить посмотреть; у него есть другая сила - вы можете увеличить столбец, не перераспределяя всю матрицу.

Роб Шрайбер
источник
Хорошо для моей реализации GPU, я в конечном итоге нашел ненулевую структуру, а затем нашел фактическую матрицу. Производительность была ужасной, как и ожидалось. Я думаю, что они используют метод, описанный в этой книге, для эффективного умножения двух разреженных матриц в MATLAB.
Рекер
2
Действительно круто, спасибо за историческую перспективу, и добро пожаловать в scicomp :)
Арон Ахмадиа
4

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

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

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

Годрик Провидец
источник
0

Для CSR или CSC, вы гарантируете, что ваш массив матричных элементов уже не имеет нулей? В этом случае просто выяснить, сколько ненулевых элементов существует, используя что-то похожее на:

int nnz = sizeof(My_Array)/sizeof(long int);

Однако, если это не так (кажется, это слишком просто), то вы можете попробовать уменьшить . Если ваш массив матричных элементов очень большой, это может быть наиболее эффективным способом для вычисления количества ненулевых элементов. Многие параллельные библиотеки C / C ++, такие как Thrust (библиотека CUDA) или OpenCL (для которых вам не нужен графический процессор) поддерживают условные сокращения - для каждого элемента добавьте результат Condition(Element). Если вы установите условие, Element != 0то вы сложите количество ненулевых элементов. Вы также можете удалить элементы с нулевым значением из вашего массива элементов, массива индексов строк / столбцов и настроить указатели столбцов / строк.

рампа
источник
спасибо за ваш ответ ... но я имел в виду ненулевые значения в A * B, где A и B - разреженные матрицы. Мне нужно заранее количество ненулевых значений, чтобы я мог выделить точное количество памяти для хранения результирующей матрицы.
Рекер
0

Самый простой способ реализации КСО - это попробовать

std::vector< std::map<int, complex<float>> > 

представлять вашу матрицу. В этом случае вы не будете беспокоиться о количестве ненулевых элементов, все доступно через

std::map< int, complex<float> >::iterator

на каждом ряду. Лучший ..


источник
2
STL, когда вы думали, что ваши подпрограммы разреженной матрицы не могут быть сделаны медленнее.
Джед Браун