EvalSum on a vector with 4000+ values

Hi everyone,

im trying to use the EvalSum() operation on a vector with 4000+ values. Since this operation is based on several vector rotations, I have created rotation keys for all indices accordingly. The problem, however, is that the operation EvalRotateKeyGen() consumes so much memory that the program is killed with exit code 137.

What i want to achieve is going from this vector:

vector<double> v1 = {51.2271, 6.61748e-13, 3.24305e-13, -1.57976e-13, -5.11591e-13, 9.34338e-13, 5.28346e-13, -9.16319e-14, ...}; // 4000+ values

to this vector:

vector<double> v2 = {51.2271, 51.2271, 51.2271, 51.2271, 51.2271, 51.2271, 51.2271, ...};

I’m able to achieve that for vector with size 128. But with size 256 EvalRotateKeyGen() for an index list with 256 indices it rans out of memory. My pseudo code looks like this so far:

vector<double> mask(values.size(), 0);
mask[0] = 1;
auto ct = cc->EvalMult(cc->MakeCKKSPackedPlaintext(mask, 1, 0, nullptr, slots), v1);
auto ct2 = cc->EvalSum(ct, slots); // v2

This works for a value vector size of 128. Everything above is killed with code 137.

Is there a more efficient method to get from v1 to v2 ??

Thanks in advance! =)

You should use EvalSumKeyGen, which generates a logarithmic number of rotation keys rather than one key for every index, or generate those keys yourself. EvalSum takes a logarithmic approach for efficiency reasons. Specifically, instead of computing ct2 = \sum_{i=0}^{n-1} Rot(ct, i), it performs
ct2 = ct;\\ For (i=0; i< ceil(\log_2(n)); ++i) \\ \quad ct2~ += ~Rot(ct2, 2^i)

Note that with this approach, you require only ceil(\log_2(n))-1 instead of n-1 rotation keys.

Yeah i used this before but the error says: EvalKey for index [625] is not found.
Somehow it does not use the EvalSumKeys. Can you tell me how to use EvalSum() correctly with the generated keys of EvalSumKeyGen()?

auto evalSumKeys = cc->GetEvalSumKeyMap(kp.secretKey->GetKeyTag());
auto ct2 = cc->EvalSum(ct, slots, evalSumKeys); 
// Function has 2 parameters, but is called with 3 arguments
// only 2 arguments are accepted here?? The doc says i can add the key map as 3rd argument

It is hard to comment on it w/o seeing a minimal working example. EvalSumKeyGen uses the batchSize parameter. If it is set to 0 (default), then all keys should be generated (for maximum number of slots). If it is set to a smaller number, then not all keys will be generated.

Either way, it is hard to tell what is wrong w/o looking at a working example.

Maybe this example here will help you Is there any example about how to use EvalSumRows/EvalSumCols? - #2 by Caesar.

Thanks! I didn’t know that EvalSumKeyGen uses the batchsize parameter. That solved my problem =)