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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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