I'm working with sparse vectors represented as index (array of unsigned integers) and coefficient (array of floats with the same dimension).

Suppose I have many vectors of different length, and I want to add them all, summing the corresponding coefficients for each unique index.

I need to calculate it the fastest possible way, since the vector addition may be potentially called millions of times by unknown code using the library.

My starting point is an unique 1D array index_union containing all the vectors to be added, with indexes duplicated many times, and a parallel array of the same size, coefficient_union holding the coefficients.

The worst problem is finding an unique place in memory, for each index, to accumulate the coefficient sums for that index, and in the end reconstruct the sparse array.

I've considered several approaches:

  1. Sorting index_union and iterating to find duplicates: This might be slow due to the large number of comparisons, and would require different sorting algorithms for each size.
  2. Building a balanced binary tree with index_union as keys and accumulating coefficients at each node.
  3. Hashing index_union and accumulating coefficients in the hash table: This might be fast for lookups, but collisions could be problematic.

I suspect there are existing algorithms specifically designed for this type of operation. However, I'm struggling to find them due to ignorance of the relevant keywords.

Therefore, my question is: What are the names of efficient algorithms for combining sparse vectors with duplicate indices/collecting common factors?

  • $\begingroup$ @Inuyasha Yagami By sparse vector, I mean that I only represent the nonzero elements. index12 is a product, which produces many repeated indexes, that need to be collected/reduced, so the result has unique indexes. I'm not working with polynomials, but is analogous: if you multiply polynomials, you get the same variables repeated multiple times, and is necessary to collect the coefficients to reduce the polynomial to the minimum expression, like (x+y)²=x.x+x.y+y.x+y.y=x²+2xy+y² $\endgroup$
    – tutizeri
    Commented Dec 17, 2023 at 11:34
  • $\begingroup$ By dimension n, I mean n nonzero coefficients. $\endgroup$
    – tutizeri
    Commented Dec 17, 2023 at 11:36
  • $\begingroup$ I see. It seems like your problem can be reduced to polynomial multiplication. Is that right? For that, there is a standard $FFT$ algorithm. $\endgroup$ Commented Dec 17, 2023 at 11:44
  • $\begingroup$ What do you mean by the "product" of two vectors? Can you define what you are referring to? Why does the product have dimension $mn$? Why would indices occur multiple times? I think I am failing to understand something fundamental. $\endgroup$
    – D.W.
    Commented Dec 17, 2023 at 12:42
  • $\begingroup$ @Inuyasha Yagami. No. I'm not doing polynomial multiplication. I only shown polynomial multiplication as example of collecting coefficients. $\endgroup$
    – tutizeri
    Commented Dec 17, 2023 at 16:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.